sudoku

A Golang terminal based sudoku solver, utilizing Dancing Links (Algorithm X) as described by Donald Knuth. Forked from zanicar/sudoku

The implementation is terminal based and it will find all solutions in the given search space (provided sufficient computing resources are available).

Usage

> sudoku 9 .6.3..8.4537.9.....4...63.7.9..51238.........71362..4.3.64...1.....6.5231.2..9.8.

• The first parameter denotes the board size and must be one of the following: 2, 4, 9, 16, 25, 36;
• The second parameter is the initialization string and it must be of length size^2;
• Each rune / string position denotes a single board cell and is indexed from left to right, starting at the top left corner;
• The values use the alphabet "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0" to support different variants up to 36x36. This is unlike the original zanicar/sudoku which uses the zero-based alphabet "0123456789ABCDEFGHIJKLMNO" (and only supports up to 25x25). This change is to make the program use the same notation for 9x9 puzzles as is commonly used on the Internet while supporting puzzles up to 36x36;
• '.' represents an empty cell;

Output

Initial Solution:

   6   | 3     | 8   4
 5 3 7 |   9   |
   4   |     6 | 3   7
 - - - + - - - + - - -
   9   |   5 1 | 2 3 8
       |       |
 7 1 3 | 6 2   |   4
 - - - + - - - + - - -
 3   6 | 4     |   1
       |   6   | 5 2 3
 1   2 |     9 |   8

Solution 1:

 2 6 1 | 3 7 5 | 8 9 4
 5 3 7 | 8 9 4 | 1 6 2
 9 4 8 | 2 1 6 | 3 5 7
 - - - + - - - + - - -
 6 9 4 | 7 5 1 | 2 3 8
 8 2 5 | 9 4 3 | 6 7 1
 7 1 3 | 6 2 8 | 9 4 5
 - - - + - - - + - - -
 3 5 6 | 4 8 2 | 7 1 9
 4 8 9 | 1 6 7 | 5 2 3
 1 7 2 | 5 3 9 | 4 8 6

Found 1 solutions in 0.000000 seconds.

Examples

Single Solutions (9x9)

• .6.3..8.4537.9.....4...63.7.9..51238.........71362..4.3.64...1.....6.5231.2..9.8.
• ..75....9.1..4..8.9....71..3....52...6..9..3...91....5..34....6.5..1..7.8....29..
• 8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..
• .5..1...6..7..6.2.8..2.7.593.8...69..1.....4..95...2.858.1.9..2.7.8..9..6...7..8.
• .....82.9.5.74..1.6.9..2.....4.7.63....4.......6...5......1....5.......331.8....2

Multiple Solutions (9x9)

• .8...9743.5...8.1..1.......8....5......8.4......3....6.......7..3.5...8.9724...5.
• 1...9...4.2.....3...3...2.....4.1...4...5...6...9.6.....8...7...7.....8.6...1...9

Single Solution - (16x16)

• ....64.....1G.FE..E.DG7.38..6C..98.....567....122..1...A..D.....5.7.1..3...6.....D...A...92...65.....6..C...F2.G.....8...A.7.......G...E.26..1...3......8....7.9.A.52.1G..3F.4..F684....7.....C.C........F7...5BE5B3..8..G....4A....3...E.....7.AG...5D.9B.3....

Performance

Performance test from my laptop (Core i7-4720HQ with 8GB Memory) for some of the examples above:

• 9x9 multiple solutions, example 1: Average 0.001s for 8 solutions;
• 9x9 multiple solutions, example 2: Average 0.045s for 812 solutions;
• 16x16 single solution: Average 0.002s;

Performance tests do not include time taken for transforming, converting or printing of solutions.