ECOO '13 R1 P3 - Hexudoku

View as PDF

Points: 7 (partial)
Time limit: 13.0s
Memory limit: 256M

Problem type

Hexudoku is a game of logic in which the goal is to fill in a grid with hexadecimal digits from 0 to F. The grid has rows, columns, and quadrants. The game starts with a partially filled in board, like the one shown below. The goal is to fill up the rest of the board with hexadecimal digits from 0 to F so that no row, column, or quadrant contains a repeated digit.

For reference, the hexadecimal digits (in order from least to greatest) are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E and F.

Lazy Larry almost never completes a Hexudoku game, but his simple strategy does make quite a bit of progress. He starts in the top left corner and scans to the right until he finds a blank cell. Then he looks for the smallest hexadecimal digit that can go there without creating a conflict in its row, column, or quadrant. If he finds one, he fills it in. Then he moves to the right until he finds another blank cell and fills it in the same way. He continues until the first row is finished, then moves to the first cell in the next row down and continues until he reaches the bottom right corner. Then he gives up.

D15- --0- -8-- ---3
---- 7-C- -4EB ----
6--B -E-2 --9- ----
--C- --48 7--0 ----

A--8 5--6 4--- B--0
-3D- ---E ---- -7--
---- ---- ---4 1---
-7-- --D- ---- ----

C--- ---- B--- ----
---E 3--- ---- -4--
---9 ---- --A- --0-
-5-- ---1 ---- ----

---- ---C ---- 9---
B--- ---- 0--A 3---
---- 4--- ---- ----
-D-- 8--- -C-- 5---
D152 690A C8F- 4B73
083A 71C5 24EB 69DF
647B DE32 159- 08AC
9ECF B-48 7360 215-

A218 5376 49CD BEF0
43D0 128E 56BF A79-
569C 0ABF 3274 1D8-
E7B- 94D- 801- C235

C021 A564 B738 DFE9
7A6E 3029 D15C 84B-
3B49 C7ED 6FA2 -501
85FD -B-1 9E0- 7326

1F03 265C EB47 9A-8
B984 ED17 0-2A 36C-
2CA5 4F90 -D81 E--7
-DE6 8-A3 FC-9 5012

Applying this strategy to the board above, the first cell Larry can fill in is the from the left in the top row. Digits 0 and 1 both create conflicts but 2 is safe. In the next cell over 0 through 5 are no good, but 6 works. Eventually, he ends up with the board on the right.

The input contains Hexudoku boards. Each board consists of lines of characters each. A blank cell is represented with a - character (ASCII code 45). Your job is to report the progress Lazy Larry will make by following the simple strategy described above. The output should be one line for each test case reporting the number of blanks Larry manages to fill in.

The sample input contains only test cases.

Sample Input

--A---------5---
-CF--B-9--------
----------5----0
--------------9-
---7---3-----BF-
-B------0-7-----
-F-----C-----D--
---------4-D----
-----------4----
--7-------------
---E---------5--
----D-2-8---A---
-------------F--
---------A-9----
------------6---
------70--8-----
D15---0--8-----3
----7-C--4EB----
6--B-E-2--9-----
--C---487--0----
A--85--64---B--0
-3D----E-----7--
-----------41---
-7----D---------
C-------B-------
---E3--------4--
---9------A---0-
-5-----1--------
-------C----9---
B-------0--A3---
----4-----------
-D--8----C--5---
----B-----C1F--8
---C--4-F-5-D---
--E----1----4--9
-0--172--D------
----4---3----A--
--7----------8--
-------C53------
-D--0-----------
---A62---4---3--
--0F-9-----B---D
----7--8A--6----
E----8------3-9-
4------EB-F-----
7-2-81------A---
--9---8--13-E---
--------1---C---

Sample Output

189
176
164

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

Input is from stdio like all other problems (ignore the parts of the statement that say to read from a file). We have two testcases (DATA1.txt and DATA2.txt).