ECOO '13 R1 P3 - Hexudoku
View as PDFHexudoku 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
164Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org
Comments
the third sudoku of the sample input in quadrant (0,1) contains a repeated 1; am I misunderstanding something?
Larry's strategy is still well-defined when starting with a grid that already contains conflicts, so this doesn't really matter.
How many test cases are there exactly and how does the input work
Input is from
stdiolike 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).Note, that you must scan for input 10 times! For each test case there are 10 sudoku inputs.