Hexodoku is a logic puzzle similar to the popular Sudoku puzzle. Hexodoku consists of a 16 x 16 grid, further divided into 4 x 4 sections. Each row, column, and section contains the (hexadecimal) numbers 0 through F:
A Hexodoku board can be described by this simple XML schema. There is a single Sudoku element. It has an attribute order which is the square root of the number of symbols used in the puzzle (e.g., normal sudoku has an order of 3, while hexodoku has an order of 4).
The Sudoku element contains 0 to order^2 Cell elements. Each Cell has row and column attributes which have valid values in the range [0..order^2]. The value of the Cell element is the value to be placed in the Cell at the designated row and column. For instance:
<Sudoku order="2">
<Cell row="0" column="0">0</Cell>
<Cell row="0" column="1">1</Cell>
<Cell row="0" column="2">2</Cell>
<Cell row="0" column="3">3</Cell>
<Cell row="1" column="0">2</Cell>
<Cell row="1" column="1">3</Cell>
<Cell row="1" column="2">0</Cell>
<Cell row="1" column="3">1</Cell>
<Cell row="2" column="0">1</Cell>
<Cell row="2" column="1">2</Cell>
<Cell row="2" column="2">3</Cell>
<Cell row="2" column="3">0</Cell>
<Cell row="3" column="0">3</Cell>
<Cell row="3" column="1">0</Cell>
<Cell row="3" column="2">1</Cell>
<Cell row="3" column="3">2</Cell>
</Sudoku>
represents this grid:
A Sudoku is a "puzzle" if there is at least 1 unfilled cell in every row, column, and section. Further, a "puzzle" must always have at least one non-ambiguous empty cell (as long as there are empty cells). Generally, the higher the average ambiguity, the harder the puzzle. Format-wise, a puzzle is just a <Sudoku> element with less than a complete list of cells: <Sudoko order="4"></Sudoku> is an example of the format (albeit one that would fail the "non-ambiguous" test rather quickly).
The Hexodoku programming challenge is to write a program that quickly generates valid, unique, order 4 Sudoku puzzles. Submissions will be accepted until May 1st, 2006.The submission must include a program that can be run from a DOS prompt (well, a Windows XP Professional command prompt) and writes a compliant XML document to the console / standard output. The program must have an option to generate completely solved grids.
Once programs are validated as generating valid, unique puzzles, they will be timed. The fastest generator wins, except that programming quality -- unit-tests, code readability, etc. -- may be given as much as a 20% time bonus, so a well-written generator that can produce a puzzle in 12 seconds could beat a sloppy one with a 10 second time. Programs will be timed on a XP Pro Virtual PC image running on a 2.6GHz Pentium with 1GB RAM available to the system. (I'd love to do something multicore, but I don't have the hardware yet!)
The prize is a collection of the books that were finalists in the 2005 Jolt Awards "General Books" category:
I'll pay for shipping at the cheapest rate available. If you want to get the books faster, we can talk.
Big O Tie Breaker: If two or more programs consistently generate order 4 puzzles in under a second, the winner will be the program that exhibits the best performance characteristics as the puzzle order is increased.
No Puzzle Pre-Generation : No file IO will be permitted and generators must be reasonably sized.
If I have less than four valid contenders submitted by midnight on May 1, 2006, I will leave the contest open until I either receive four contenders or until June 1st, whichever comes first.
All source code must be dedicated to the Public Domain.
To submit a program, send a ZIP or RAR file to "hexodoku@knowing.net" containing:
This challenge is my personal offer.