7
$\begingroup$

Currently I have a sudoku puzzle solver program and I've tried all the puzzles I can find that are labeled the "hardest" on various sudoku video games and puzzle books. My solver has solved them all. It currently uses the following 4 polynomial time rules (i.e. polynomial time if the board was $N^2 \times N^2$ instead of $9 \times 9$).

1) Check each cell to see if only one value is possible for the cell

2) Check to see for each row/column/block whether there is a value that only one cell can have

3) Check to see for each row/column/block whether there are 2 cells that can only have the same 2 values. (Then no other squares in the same group can have those values)

4) For each row/column and block that intersects it, see if there is a value that can only appear in the intersection 3 cells either for the row/column or for the block. Then no other squares in the row/column or block can have that value.

After these rules are applied repeatedly, if the puzzle is not solved, then the program guesses a value for a cell and sees if this leads to a solution or contradiction when the above four rules are applied repeatedly. If a contradiction is found, then the value is removed from the possible values for the cell. This guessing is applied separately for each cell+possible value if the number of possible values for the cell is 3 or less. There is no simultaneous guessing for multiple cells. If at least one possible value is removed for some cell, then the above 4 rules are again applied repeatedly until guessing is required again. And repeat. If it ever happens that the 4 rules and guessing don't provide any additional information, then the program gives up and prints out the partial solution it found.

Now, there are about 10 or 20 different polynomial time rules that have been devised to rule out possibilities and infer cells' values in sudoku, and I only implemented 4. Furthermore, the guessing only guesses one cell's value at a time and merely removes the value from the possible values for the cell if a contradiction is found. So it's weird to me that this solves all the hardest puzzles I can find. Can someone produce a puzzle hard enough that my program can't solve it?

$\endgroup$
3
  • 1
    $\begingroup$ Peter Norvig's lovely essay here - norvig.com/sudoku.html - discusses the design and {Python) implementation of his sudoku solver. Whether or not it answers your question about backtracking recursion depth its worth a read. $\endgroup$ – Ethan Bolker Jun 19 '15 at 19:03
  • $\begingroup$ @EthanBolker thanks for the link. Norvig definitely allows guessing at a "depth" (number of guesses made simultaneously) greater than 1. But it seems he only uses 2 very basic polynomial time deduction rules, whereas I use 4. He did mention a few of his hardest puzzles, although some of them have multiple solutions and some of them have none. In my paradigm (and most Sudoku player enthusiasts' paradigm), we assume that a puzzle has exactly 1 solution. Some of his "hardest" puzzles had this property. I'll try them out and see what happens. Thanks again for the info. +1. $\endgroup$ – user2566092 Jun 19 '15 at 19:34
  • $\begingroup$ @EthanBolker If you post this as an answer, I'll accept and award the bounty because the one puzzles out of Norvig's 95 "difficult" he posted that took the longest time for his solver to solve was not able to be solved by my solver. Also he provided a link to "hardest Sudoku" that led to a puzzle by Inkala that my solver also failed on. $\endgroup$ – user2566092 Jun 25 '15 at 15:43
1
+100
$\begingroup$

In response to the OP's request I'm posting this as an answer - although all I did was happen to know of a place where he found a puzzle that defeated his algorithm.

Peter Norvig's lovely essay here - norvig.com/sudoku.html - discusses the design and (Python) implementation of his sudoku solver. Whether or not it answers your question about backtracking recursion depth its worth a read. – Ethan Bolker Jun 19 at 19:03

@EthanBolker thanks for the link. Norvig definitely allows guessing at a "depth" (number of guesses made simultaneously) greater than 1. But it seems he only uses 2 very basic polynomial time deduction rules, whereas I use 4. He did mention a few of his hardest puzzles, although some of them have multiple solutions and some of them have none. In my paradigm (and most Sudoku player enthusiasts' paradigm), we assume that a puzzle has exactly 1 solution. Some of his "hardest" puzzles had this property. I'll try them out and see what happens. Thanks again for the info. +1. – user2566092 Jun 19 at 19:34

@EthanBolker If you post this as an answer, I'll accept and award the bounty because the one puzzles out of Norvig's 95 "difficult" he posted that took the longest time for his solver to solve was not able to be solved by my solver. Also he provided a link to "hardest Sudoku" that led to a puzzle by Inkala that my solver also failed on. – user2566092 2 hours ago

$\endgroup$
2
$\begingroup$

There is no puzzle that cannot be solved by just guessing one cell at a time and backtracking. This method is simply called depth-first search, and clearly will always succeed, because it will try every possibility. This method is also an exponential time algorithm, which is the slowest you will see for a real-world problems. The only reason why it appears to be fast for Sudoku is that there are so few cells in the first place. A reasonable method of guessing should allow you to solve any (9 times 9) Sudoku in a split-second. Here are two examples you can try:

Puzzle 1

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

Puzzle 2

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

Puzzle 1 cannot be solved by most simple Sudoku techniques. Puzzle 2 is the one that my solver needs to check the most number of states, out of about 100 randomly generated puzzles with this kind of pattern. But as I said, any lousy backtracking algorithm should solve them in a split-second. To really test if your solver is efficient, extend your solver to 16 times 16 Sudoku and try to solve the following (the amount of time my solver takes on a single Intel i5 processor is in brackets):

Puzzle 3 [3s] (from this random webpage)

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

Puzzle 4 [26s] (from another random webpage)

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

My solver uses no strategies at all but only guessing, and so the code is extremely short. There are plenty more that you can try from the second link, but you'll have to copy down the puzzles yourself.

$\endgroup$
5
  • $\begingroup$ Thanks for the answer. I understand DFS can always solve if a solution exists, but the depth of the search tree might be > 1, so my question is whether (for solvable 9x9 with a unique solution) it is possible to always solve with depth = 1, i.e. guess each number for each cell individually, and then rule out some possibilities using standard (not guessing) rules, and then make progress if all guesses for a single cell lead to some shared deductions, or if standard deduction rules lead to a solution. I.e. I wonder if there is a set of "standard" deduction rules rich enough for that, for 9x9. $\endgroup$ – user2566092 Jun 15 '15 at 17:03
  • $\begingroup$ @user2566092: Did you try the examples I gave? Did your solver manage to solve it using only depth 1 recursion? $\endgroup$ – user21820 Jun 16 '15 at 4:44
  • $\begingroup$ I need to refactor my code to handle boards larger than 9x9, but I tried the two 9x9 boards you gave and yes, my solver solved them basically instantly, and moreover, my solver estimates difficulty based on how many of each type of "rule" it uses (so if guessing to just eliminate one value is required, difficulty goes up a lot), and my random puzzle generator has created puzzles that are approximately 30 times harder according to this metric, compared to the estimated difficulty for the puzzles you provided. However the reported difficulty for your 9x9 puzzles was still pretty high. $\endgroup$ – user2566092 Jun 17 '15 at 18:17
  • $\begingroup$ And so I should clarify, the reported difficulty for your 9x9 puzzles was high enough that a decent amount of depth=1 guessing must have been required. But it never used depth > 1 guessing. $\endgroup$ – user2566092 Jun 17 '15 at 18:22
  • $\begingroup$ @user2566092: Nice. The reason my generated puzzles were not hard is basically because it used the solver which cannot even identify some singles (only one possible place for a number in a row/column/square). I was lazy to program that in, but I can see that it would make it much faster. Let me know what you get with the larger puzzles; I expect your solver to beat mine if the recursion was implemented correctly. =) $\endgroup$ – user21820 Jun 18 '15 at 4:27
0
$\begingroup$

Start with a simple puzzle, and then I made this harder and harder by the removing the known field values. The main hardness of a sudoku puzzle is at the beginning.

$\endgroup$
1
  • 1
    $\begingroup$ can you post an example of such a puzzle you've created that you think might be the "hardest" you've found? $\endgroup$ – user2566092 Aug 19 '14 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.