A Sudoku is a matrix of cells, typically 9x9, but it can be any number. In this post, we consider N x N Sudoku (where N is a perfect square, i.e. 1x1, 4x4, 9x9, 16x16). Now for such a Sudoku, we first construct a groups of cells called as blocks. We get N row blocks, N column blocks and N sub-grid blocks. All the blocks contain N cells each. A cell can have a value from 1 to N, such that, if a cell is assigned a value, then no other cell in the same block can be assigned that value. To check if a Sudoku is solved, all the blocks must sum to N*(N+1)/2. Another check is one where number uniqueness constraints are satisfied per block and each cell is assigned a value from 1 to N.

To simplify a Sudoku by hand, I typically use the following techniques:

- A number is assigned to a cell,

- If a cell can hold only that number.
- If that number can be held by only that cell (in at least one block).

- Two numbers are assigned to two cells if those two cells share at least one block (Note: two cells can share maximum of two blocks),

- The two numbers are referred exclusively by these two cells in a given block. In this case other hints of the two numbers are pruned.
- The two cells refer to those two numbers only. In this case the two numbers are removed from the hints of other cells in their shared block.

- To finally solve it, simplify Sudoku by applying (1) and (2) until further simplification is not possible. Then pick a cell with least number of hints. Assign it one of those hints and repeat this brute-force method. If failed, then try another hint. If all hints fail then Sudoku is not solvable.

The program is oriented to be event driven, where a cell is asked to remove its hint based on the logic of (1,2,3). In this process if a cell has only one hint remaining, it triggers a fix event. When the fix event is called, this cell is assigned the value and that value is removed from the hint of cells that share block with it. If at anytime any inconsistencies are found, the events return a “false”, indicating that Sudoku is not solvable. This is a fail fast technique and it quickly helps in determining if a Sudoku is non-solvable or not. Otherwise, we would wait for all cells to get filled and then realize that it failed (wasting precious time). A simple brute-force strategy is very easy to code, however the possibilities to check are huge. For e.g., we might end up checking O(9^81) possibilities (which can be prohibitive). The simplification algorithms (1) and (2) come to the rescue by drastically simplifying the Sudoku. For most of the easy problems - the recursive step (3) is not even triggered.

I searched online for Sudoku problems and found that Peter Norvig has a blog about it. He used algo(1,3) but not (2) and has shared a set of easy, hard, and hardest Sudoku puzzles. It amazes me to say that for most hard problem, I take at least 8-10 minutes (and sometimes a hint) but a computer can solve it in order of ~0.1 ms. If you are interested in the maths of Sudoku (e.g. number of possible solutions), please check out the wikipedia page: maths of sudoku.

In the first analysis below, we see how many cells different algorithms are able to solve.

Input | (1) | (2a) | (2b) | (2) | (1+2a) | (1+2b) | (*) | |

Easy | 35% | 89% | 54% | 68% | 70% | 96% | 94% | 96% |

Hard | 25% | 31% | 26% | 26% | 26% | 41% | 31% | 41% |

Hardest | 30% | 45% | 35% | 35% | 36% | 50% | 45% | 50% |

Here we see that algorithm (1) itself can solve 89% of the cells for easy problems. However, the joint application of (1+2) is able to solve 96% of the easy cells and 41% of the hard cells (and roughly provide a 10-15% improvement. This is a great simplification, especially for easy Sudoku problems. Amongst (2a) and (2b), I find (2a) to be a better strategy to run in conjunction with (1) as (1+2a) has same result as (*).

In the next analysis, we see how many hints are left after application of different algorithms

Input | (1) | (2a) | (2b) | (2) | (1+2a) | (1+2b) | (*) | |

Easy | 474 | 29 | 126 | 89 | 82 | 10 | 16 | 10 |

Hard | 544 | 230 | 252 | 260 | 250 | 184 | 228 | 181 |

Hardest | 508 | 161 | 191 | 193 | 189 | 141 | 158 | 141 |

Similar analysis as above. 2a appears better than 2b. But (*) must better than (1) or (2). So combining these strategies is much more effective. We see that clearly (1+2a) as good as (*) so we can simply drop algorithm 2b. To see how much (if at all) there is a penalty of running the (2b) algo, we turn to time taken.

For measuring time, I use Java's System.NanoTime() function, which gives very precise timing. Experiments are run on my MacBook Pro with 2.6Ghz intel I7 processor. To get the timings, I solve a puzzle 500 times and take the average solving time. We get the following timings.

Brute Force | (1) | (1+2a) | (1+2b) | (*) | |

Easy | 0.14 ms | 0.04 ms | 0.03 ms | 0.03 ms | 0.03 ms |

Hard | 21 ms | 1.16 ms | 0.44 ms | 0.55 ms | 0.42 ms |

Hardest | 0.61 ms | 0.17 ms | 0.20 ms | 0.19 ms | 0.22 ms |

Clearly brute force without simplification is a bad idea. (*) improves timing over (1) for hard problems at least. For other problems, numbers are very close to conclude. My experience over other random problems that I tried, suggests that (*) leads to fastest simplification (i.e. reduced iterations) and hence better.

I also tried the problem that Peter mentions taking most time and noted its timing through my Java implementation. It took 6134 ms for algo (1), but only 10ms for (*). A clear evidence of the joint algorithms' usefulness. This improved timing comes from the fact that Sudoku gets drastically simplified before entering the brute-force stage and even for each choice of brute-force, it further gets simplified eliminating possible hints.

The Sudoku program is generic in the sense that it can solve 1x1, 4x4, 9x9, 16x16, … problems. A quick run of the program is as follows:

Solving a Sudoku puzzle of size 1 ...

===

| * |

===

[status] solved=0 hints=1

===

| 1 |

===

[status] SOLVED

Time taken=0.022 ms

Solving a Sudoku puzzle of size 4 ...

===== =====

| 4 * | 2 * |

| * * | 4 1 |

===== =====

| 1 * | * * |

| * * | 1 4 |

===== =====

[status] solved=7 hints=36

===== =====

| 4 1 | 2 3 |

| 2 3 | 4 1 |

===== =====

| 1 4 | 3 2 |

| 3 2 | 1 4 |

===== =====

[status] SOLVED

Time taken=0.132 ms

Solving a Sudoku puzzle of size 9 ...

======= ======= =======

| * * * | 7 * * | 6 * 3 |

| 7 * 3 | 9 * * | * 1 2 |

| * * * | 5 3 * | * * * |

======= ======= =======

| 1 * * | * * * | * * 7 |

| 9 * * | * * * | * * * |

| * 4 5 | * * * | * 9 6 |

======= ======= =======

| 3 * * | * * * | 9 * * |

| * * * | * * 1 | * 6 5 |

| * 1 * | 3 6 * | * 7 4 |

======= ======= =======

[status] solved=27 hints=486

======= ======= =======

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

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

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

======= ======= =======

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

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

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

======= ======= =======

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

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

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

======= ======= =======

[status] SOLVED

Time taken=2.198 ms

Solving a Sudoku puzzle of size 16 ...

============= ============= ============= =============

| 8 7 * * | * * * * | * 3 * * | 13 * 4 * |

| * 5 14 * | * * 3 10 | 15 9 1 * | * 6 * * |

| 16 * * * | 5 8 7 * | * 14 * * | 9 * 11 12 |

| * * 4 * | * 14 6 13 | * 11 10 12 | * 7 * 3 |

============= ============= ============= =============

| 14 * * 8 | * * 1 * | * * * 3 | 7 4 12 * |

| 9 * * * | * 6 15 12 | * * 13 14 | * 3 1 * |

| 11 * 10 3 | * * 13 * | * 8 * 1 | * * 6 * |

| 6 * * 1 | 14 * 4 * | * 5 * 9 | 11 * * 13 |

============= ============= ============= =============

| * * * * | 15 * * * | * * 9 * | 5 * 2 10 |

| 10 1 * * | 6 * 5 * | 13 15 7 16 | * * * * |

| * * 16 11 | * 4 * 8 | 2 * * * | * 13 * 7 |

| * 9 * 7 | 1 3 * 2 | 6 * 8 10 | 16 15 14 4 |

============= ============= ============= =============

| 7 * 13 * | 9 16 * 5 | * * 14 4 | 3 8 * 2 |

| * * 3 * | 10 * * * | * * * * | * 16 15 * |

| 1 * 9 * | * * 14 4 | * * * * | * * 7 * |

| * 6 8 * | 3 * * * | 10 7 * * | * * * * |

============= ============= ============= =============

[status] solved=116 hints=2240

============= ============= ============= =============

| 8 7 11 10 | 2 12 9 1 | 5 3 16 6 | 13 14 4 15 |

| 12 5 14 13 | 4 11 3 10 | 15 9 1 7 | 2 6 16 8 |

| 16 3 1 6 | 5 8 7 15 | 4 14 2 13 | 9 10 11 12 |

| 2 15 4 9 | 16 14 6 13 | 8 11 10 12 | 1 7 5 3 |

============= ============= ============= =============

| 14 13 15 8 | 11 2 1 9 | 16 10 6 3 | 7 4 12 5 |

| 9 4 7 5 | 8 6 15 12 | 11 2 13 14 | 10 3 1 16 |

| 11 2 10 3 | 7 5 13 16 | 12 8 4 1 | 15 9 6 14 |

| 6 16 12 1 | 14 10 4 3 | 7 5 15 9 | 11 2 8 13 |

============= ============= ============= =============

| 3 8 6 12 | 15 13 16 7 | 14 4 9 11 | 5 1 2 10 |

| 10 1 2 4 | 6 9 5 14 | 13 15 7 16 | 8 12 3 11 |

| 15 14 16 11 | 12 4 10 8 | 2 1 3 5 | 6 13 9 7 |

| 13 9 5 7 | 1 3 11 2 | 6 12 8 10 | 16 15 14 4 |

============= ============= ============= =============

| 7 11 13 15 | 9 16 12 5 | 1 6 14 4 | 3 8 10 2 |

| 5 12 3 14 | 10 7 8 6 | 9 13 11 2 | 4 16 15 1 |

| 1 10 9 2 | 13 15 14 4 | 3 16 5 8 | 12 11 7 6 |

| 4 6 8 16 | 3 1 2 11 | 10 7 12 15 | 14 5 13 9 |

============= ============= ============= =============

[status] SOLVED

Time taken=1.346 ms

Solving all puzzles from: ./src/sudoku/hardest.txt

Solved : 11/11

Solved Cells : 270(input) 891(finally) 891(expected)

Cell Hints : 5589(input) 0(finally)

Time Taken : 2.59014144 milli-seconds

Avg time : 0.23546740363636365 milli-seconds

Solving all puzzles from: ./src/sudoku/hard.txt

Solved : 95/95

Solved Cells : 1953(input) 7695(finally) 7695(expected)

Cell Hints : 51678(input) 0(finally)

Time Taken : 41.772783616 milli-seconds

Avg time : 0.4397135117473684 milli-seconds

Solving all puzzles from: ./src/sudoku/easy.txt

Solved : 50/50

Solved Cells : 1418(input) 4050(finally) 4050(expected)

Cell Hints : 23688(input) 0(finally)

Time Taken : 1.868110848 milli-seconds

Avg time : 0.03736221696 milli-seconds

===

| * |

===

[status] solved=0 hints=1

===

| 1 |

===

[status] SOLVED

Time taken=0.022 ms

===== =====

| 4 * | 2 * |

| * * | 4 1 |

===== =====

| 1 * | * * |

| * * | 1 4 |

===== =====

[status] solved=7 hints=36

===== =====

| 4 1 | 2 3 |

| 2 3 | 4 1 |

===== =====

| 1 4 | 3 2 |

| 3 2 | 1 4 |

===== =====

[status] SOLVED

Time taken=0.132 ms

======= ======= =======

| * * * | 7 * * | 6 * 3 |

| 7 * 3 | 9 * * | * 1 2 |

| * * * | 5 3 * | * * * |

======= ======= =======

| 1 * * | * * * | * * 7 |

| 9 * * | * * * | * * * |

| * 4 5 | * * * | * 9 6 |

======= ======= =======

| 3 * * | * * * | 9 * * |

| * * * | * * 1 | * 6 5 |

| * 1 * | 3 6 * | * 7 4 |

======= ======= =======

[status] solved=27 hints=486

======= ======= =======

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

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

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

======= ======= =======

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

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

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

======= ======= =======

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

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

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

======= ======= =======

[status] SOLVED

Time taken=2.198 ms

============= ============= ============= =============

| 8 7 * * | * * * * | * 3 * * | 13 * 4 * |

| * 5 14 * | * * 3 10 | 15 9 1 * | * 6 * * |

| 16 * * * | 5 8 7 * | * 14 * * | 9 * 11 12 |

| * * 4 * | * 14 6 13 | * 11 10 12 | * 7 * 3 |

============= ============= ============= =============

| 14 * * 8 | * * 1 * | * * * 3 | 7 4 12 * |

| 9 * * * | * 6 15 12 | * * 13 14 | * 3 1 * |

| 11 * 10 3 | * * 13 * | * 8 * 1 | * * 6 * |

| 6 * * 1 | 14 * 4 * | * 5 * 9 | 11 * * 13 |

============= ============= ============= =============

| * * * * | 15 * * * | * * 9 * | 5 * 2 10 |

| 10 1 * * | 6 * 5 * | 13 15 7 16 | * * * * |

| * * 16 11 | * 4 * 8 | 2 * * * | * 13 * 7 |

| * 9 * 7 | 1 3 * 2 | 6 * 8 10 | 16 15 14 4 |

============= ============= ============= =============

| 7 * 13 * | 9 16 * 5 | * * 14 4 | 3 8 * 2 |

| * * 3 * | 10 * * * | * * * * | * 16 15 * |

| 1 * 9 * | * * 14 4 | * * * * | * * 7 * |

| * 6 8 * | 3 * * * | 10 7 * * | * * * * |

============= ============= ============= =============

[status] solved=116 hints=2240

============= ============= ============= =============

| 8 7 11 10 | 2 12 9 1 | 5 3 16 6 | 13 14 4 15 |

| 12 5 14 13 | 4 11 3 10 | 15 9 1 7 | 2 6 16 8 |

| 16 3 1 6 | 5 8 7 15 | 4 14 2 13 | 9 10 11 12 |

| 2 15 4 9 | 16 14 6 13 | 8 11 10 12 | 1 7 5 3 |

============= ============= ============= =============

| 14 13 15 8 | 11 2 1 9 | 16 10 6 3 | 7 4 12 5 |

| 9 4 7 5 | 8 6 15 12 | 11 2 13 14 | 10 3 1 16 |

| 11 2 10 3 | 7 5 13 16 | 12 8 4 1 | 15 9 6 14 |

| 6 16 12 1 | 14 10 4 3 | 7 5 15 9 | 11 2 8 13 |

============= ============= ============= =============

| 3 8 6 12 | 15 13 16 7 | 14 4 9 11 | 5 1 2 10 |

| 10 1 2 4 | 6 9 5 14 | 13 15 7 16 | 8 12 3 11 |

| 15 14 16 11 | 12 4 10 8 | 2 1 3 5 | 6 13 9 7 |

| 13 9 5 7 | 1 3 11 2 | 6 12 8 10 | 16 15 14 4 |

============= ============= ============= =============

| 7 11 13 15 | 9 16 12 5 | 1 6 14 4 | 3 8 10 2 |

| 5 12 3 14 | 10 7 8 6 | 9 13 11 2 | 4 16 15 1 |

| 1 10 9 2 | 13 15 14 4 | 3 16 5 8 | 12 11 7 6 |

| 4 6 8 16 | 3 1 2 11 | 10 7 12 15 | 14 5 13 9 |

============= ============= ============= =============

[status] SOLVED

Time taken=1.346 ms

Solved : 11/11

Solved Cells : 270(input) 891(finally) 891(expected)

Cell Hints : 5589(input) 0(finally)

Time Taken : 2.59014144 milli-seconds

Avg time : 0.23546740363636365 milli-seconds

Solved : 95/95

Solved Cells : 1953(input) 7695(finally) 7695(expected)

Cell Hints : 51678(input) 0(finally)

Time Taken : 41.772783616 milli-seconds

Avg time : 0.4397135117473684 milli-seconds

Solved : 50/50

Solved Cells : 1418(input) 4050(finally) 4050(expected)

Cell Hints : 23688(input) 0(finally)

Time Taken : 1.868110848 milli-seconds

Avg time : 0.03736221696 milli-seconds

- bytes is more expensive that int. So use int.
- int check (e.g. i==0) is very-very slightly faster than boolean check. But don't use it if it compromises readability.
- Exception handling (even if exception is never thrown) is expensive.
- Java doesn't do tail call optimization. So don't worry too must about trying formatting your recursive routine.
- keyword final has no effect on performance in Java. So if you think a one liner function is inlined, its not.
- Avoid using array list and use fixed array. Even if array list is of size say k and array of n where k < n, its faster to use array. UNLESS k <<< n.
- Hashmap, Hashsets would easily hog performance. It can easily double the running time. So if you can avoid it, its better.
- 1-d array is cheaper than 2-d array.
- Using objects is extremely cheap. I find next to nil penalty on using objects. So use them to simplify code.
- Caching can be useful. for example instead of referring A[i] several times, its faster to set x =A[i] and refer to x.
- private, public, and other qualifies only increase space of byte code but has no performance impact. So use them for good design principles and not for performance improvements.

## No comments:

## Post a Comment