/Todoku

A sudoku solver for larger NxN x NxN puzzles - not just the standard N = 3 case.

Primary LanguageC++GNU General Public License v3.0GPL-3.0

Todoku

Todoku is a general Sudoku solver for NxN x NxN puzzles (with an eternal 'TODO' list...)

There are limits placed on N by the implementation. The current range for N is : 1 to 6
Character encodings are as follows:

N = 1 : '0' or '.' denote an unsolved cell. The trivial solution is: '1'

N = 2 : '0' or '.' denote an unsolved cell. Solution values are: '1' .. '4' - (4 x 4 Primer for kids) (16 cells)

N = 3 : '0' or '.' denote an unsolved cell. Solution values are: '1' .. '9' - (Standard Sudoku) (81 cells)

N = 4 : '.' denotes an unsolved cell. Solution values are: '0 .. '9', 'A' .. 'F' - (16 x 16 Hexadoku) (256 cells)

N = 5 : '0' or '.' denote an unsolved cell. Solution values are: 'A' .. 'Y' - (25 x 25 Alphadoku) (625 cells)

N = 6 : '.' denotes an unsolved cell. Solution values are: '0 .. '9', 'A' .. 'Z' - (36 x 36 Alphanumeric) (1296 cells)


Implementation notes:

Todoku is distributed as a single C++ source file: todoku.cc. It has been an exercise in using various C++11 language features (requiring a C++11 compiler), concise formatting, and pertinent commentary. It is also an experiment in trying to achieve a balance between recursive algorithms and heuristic strategies.

The test vectors (datasets) are not mine. I've preserved commentary in these files where practical, but cannot - in general - vouch for their public domain status. I'm happy to amend, replace, (or even remove) datasets at the request of their original owners. On the subject of test vectors, I feel that much of the todoku project code could be adapted to generate puzzles. This would require considerable re-factoring, as well as making the Game class somewhat more robust to prevent illegal states, etc. I have not investigated efficient methods of puzzle generation that guarantee unique solutions.

Hard limits for 'N' outside the I/O functionality (i.e., character <-> value mapping) can obviously be much higher. The unsigned int type is used extensively. This has a mandated minimum of 16 bits; but is a 32 bit type on almost all relevant ABIs for general purpose computing at this time. I have not performed anything approaching a formal verification on a maximum 'N' size, but I'm confident that N = 15 (a staggering 50625 cells!) can be implemented safely - ignoring the I/O code.

Of course, Sudoku is a known NP-complete problem, so N can always be increased to defeat any amount of (classical) computing power... regardless of the various algorithms and strategies applied.