ECOO '13 R1 P3 - Hexudoku

View as PDF

Submit solution

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 16 rows, 16 columns, and 16 4 \times 4 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 4^{th} 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 10 Hexudoku boards. Each board consists of 16 lines of 16 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 3 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


Comments


  • 1
    d  commented on Aug. 9, 2015, 11:56 a.m. edited

    Where can I find the problem statement?


  • 0
    moladan123  commented on June 14, 2015, 12:03 p.m.

    I can't read it...


    • 1
      Xyene  commented on June 14, 2015, 12:14 p.m.

      That is because ECOO has updated their site, and the links to the problems here are currently broken.


  • 0
    BMP  commented on Feb. 13, 2015, 11:32 p.m.

    How many test cases are there exactly and how does the input work


    • 0
      Xyene  commented on Feb. 13, 2015, 11:34 p.m.

      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).


      • 0
        BMP  commented on Feb. 13, 2015, 11:36 p.m.

        Note, that you must scan for input 10 times! For each test case there are 10 sudoku inputs.


  • 1
    kobortor  commented on Feb. 13, 2015, 11:23 p.m.

    For anyone that can't read this formatting

    http://ecoocs.org/contests/ecoo_2013.pdf


    • 0
      Xyene  commented on Feb. 13, 2015, 11:33 p.m.

      Oh man, that formatting was glorious. I've linked the PDF now.