The New Sudoku Players' Forum

[sb1920alk]

...that are very difficult for computers to solve? Particularly, ones that require guessing such that no matter how the solver guesses, there is an example on the list that takes a very long time because it keeps guessing wrong.

I search for awhile and skimmed a bunch of posts, but I couldn't find anything quite like this. I remember seeing one that had an empty top row that was 987654321 in the solution, implying that each of those values had to be guessed and if the solver started guessing at 1, it would take the maximum amount of time to solve.

Links to exiting examples or just examples will be greatly appreciated.

[Adak]

Wikipedia has an example of a very tough sudoku puzzle for brute force guessing programs.

Most programs will use a moderate level of logic first, (at least), before calling the brute force function to finish it off.

In my programs case, that very tough puzzle gets solved in 0.22 seconds on a slow laptop. There is a small amount of guessing done at the end, but the moderate level of logic I have in the program doesn't leave much guessing for that puzzle.

The hardest puzzles for my program are the one's like #11 in Gordon's list of Sudoku 17's puzzles: 1) There are very few givens 2) Moderate logic functions are unable to remove many of the candidate digits. (Swordfish is needed in this case, which my program has no code for yet).

That leaves a very large search space to be gone through, before finding the right answer. Same slow laptop, that takes about 14 seconds, now.

[Draco]

Hi SB,

There is no valid Sudoku (one which has only 1 solution) that computers cannot solve by "guessing" (aka Trial & Error, Ariadne’s Thread, Recursion...). The constraints on each house (row, column or box) having exactly one of the values 1 - 9 cause the solution space to collapse rapidly after relatively few "guesses" by the computer.

As puzzles get larger (e.g. 64 x 64) then the time required to solve by guessing increases rapidly and the exact implementation of the guessing algorithm begins to play a more important role in how much time will be required. However, for 9x9 puzzles, a recursive solver gets to the solution very quickly. On modern PC's, it is so fast that it is as good as instantaneous.

Some CS students at CMU posted a presentation discussing some of the methods they used for solving larger Sudoku puzzles in "reasonable" spans of time. Knuth's Dancing Links (search on that if you want to know more) can also tackle larger puzzles.

Ironically, even for many invalid Sudokus (e.g. those with more than one solution), the recursive solvers will find ONE of the solutions pretty quickly.

[sb1920alk]

... On modern PC's, it is so fast that it is as good as instantaneous.

I guess that's what I needed to know. Interesting stuff. Thanks for the replies.

[Pat]

Is there a still of sudokus that are very difficult for computers to solve?
Particularly, ones that require guessing such that no matter how the solver guesses, there is an example on the list that takes a very long time because it keeps guessing wrong.

I remember seeing one that had an empty top row that was 987654321 in the solution, implying that each of those values had to be guessed and if the solver started guessing at 1, it would take the maximum amount of time to solve.

hi sb1920alk,

i suppose this is the example you were thinking of --

Code: Select all

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



[hobiwan]

On modern PC's, it is so fast that it is as good as instantaneous.

I used to think the same thing until daj95376 posted his Contrary "17" puzzles, some of which caused my backtracking function to run amok. I won't post times for my own code (too humiliating) but times for my java port of gsf's backtracking algorithm (I lost the url).

Wikipedia "nearly worst case":

Code: Select all

..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9
2ms

"17" puzzle #42341:

Code: Select all

..15............32...............2.9.5...3......7..8..27.....4.3...9.......6..5..
73ms

"17" puzzle #46556:

Code: Select all

.1.....2....8..6.......3........43....2.1....8......9.4...7.5.3...2...........4..
95ms

As you can see the ratio between Wikipedias "nearly worst case" and #46556 is over 1:47 (although 95ms is probably still fast enough for most applications).

[gsf]

On modern PC's, it is so fast that it is as good as instantaneous.

I used to think the same thing until daj95376 posted his Contrary "17" puzzles, some of which caused my backtracking function to run amok. I won't post times for my own code (too humiliating) but times for my java port of gsf's backtracking algorithm (I lost the url).

Wikipedia "nearly worst case":

Code: Select all

..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9
2ms

"17" puzzle #42341:

Code: Select all

..15............32...............2.9.5...3......7..8..27.....4.3...9.......6..5..
73ms

"17" puzzle #46556:

Code: Select all

.1.....2....8..6.......3........43....2.1....8......9.4...7.5.3...2...........4..
95ms

As you can see the ratio between Wikipedias "nearly worst case" and #46556 is over 1:47 (although 95ms is probably still fast enough for most applications).

that backtrack implementation only propagates naked singles
if you throw in hidden singles the times for the last 2 go down into the noise
~1000 puz/sec/Ghz for the first, ~60000 puz/sec/Ghz for the last 2
this is a bit strange because the first one is singles constrained (solves with singles only)
so it looks like there is a crossover for a hybrid singles/backtrack alg

[Draco]

On modern PC's, it is so fast that it is as good as instantaneous.

I used to think the same thing until daj95376 posted his Contrary "17" puzzles, some of which caused my backtracking function to run amok. I won't post times for my own code (too humiliating) but times for my java port of gsf's backtracking algorithm (I lost the url).

Wikipedia "nearly worst case":

Code: Select all

..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9
2ms

"17" puzzle #42341:

Code: Select all

..15............32...............2.9.5...3......7..8..27.....4.3...9.......6..5..
73ms

"17" puzzle #46556:

Code: Select all

.1.....2....8..6.......3........43....2.1....8......9.4...7.5.3...2...........4..
95ms

As you can see the ratio between Wikipedias "nearly worst case" and #46556 is over 1:47 (although 95ms is probably still fast enough for most applications).

100Ms or less is essentially instantaneous from a human perspective. I tried these 3 puzzles after adding a millisecond timer to my solver code. All tests run on a 2 Ghz Core Duo laptop. Solver is in C# (C++ would yield faster code) compiled with VS 2005.

#1 and #3 = 15.63Ms, #2 = 234.38Ms. So not instantaneous, but still pretty darned quick. Clearly some of these are much harder for the recursive solver to nail. I doubt a human could match these times though . Also clear that there are/will be diff's between recursive implementations and what they find faster or slower. For those that care about technical details, at one point I tried unwinding the recursion and turning it into a loop. The amount of state I had to put onto my own "stack" for this meant that there was little speed difference (and the unwound version was a lot harder to read!)

I could look for puzzles that exploit the weak spots in my solver, but the end result is it produces answers very quickly for every puzzle I've tried; far more quickly than if I tried to apply logic techniques (the code to find color chain cancellations, for instance, takes a huge amount of CPU time vs. just solving the puzzle recursively. < 300 Ms to solve a 17-spot puzzle... while relatively slow it is still, as I said, pretty darned fast.

[sb1920alk]

I think the Wikipedia example is probably the one I remember seeing. Thanks for all these examples.

A followup question: do you think it's possible that there are non-T&E techniques that can be developed that can solve the "hardest" puzzles or will there always exist a puzzle that cannot be solved without guessing?

I don't post very often on this forum, but I have to say that everyone here is very pleasant and helpful.

[eleven]

Draco, these 3 puzzles are easy. So its not the case, that harder puzzles also need more time for programs ?

A followup question: do you think it's possible that there are non-T&E techniques that can be developed that can solve the "hardest" puzzles or will there always exist a puzzle that cannot be solved without guessing?

This only depends on what you call a non-T&E technique. But for me it is neither interesting to solve such a puzzle nor to read a solution.

[gsf]

As you can see the ratio between Wikipedias "nearly worst case" and #46556 is over 1:47 (although 95ms is probably still fast enough for most applications).

the wiki worst case makes some bad assumptions on backtracking algorithm implementatiions
namely that the grid is examined by something like
for r in 1..9 for c in 1..9 for v in 1..9
and always in the same order
the forgot the most basic backtracking optimization: take the branch(es) with the least amount of choices

#1 and #3 = 15.63Ms, #2 = 234.38Ms. So not instantaneous, but still pretty darned quick. Clearly some of these are much harder for the recursive solver to nail. I doubt a human could match these times though . Also clear that there are/will be diff's between recursive implementations and what they find faster or slower. For those that care about technical details, at one point I tried unwinding the recursion and turning it into a loop. The amount of state I had to put onto my own "stack" for this meant that there was little speed difference (and the unwound version was a lot harder to read!)

a big part of the efficiency of a backtracking implementation is the amount of state that must be copied for the next ply and/or unwound on error

also, to measure timings in the noise, do the timing on say 1000 copies of the same puzzle
15 vs. 234 may not be much for one puzzle, but its an order of magnitude, and that could make
a big differences on a collection of 100s or 1Ms or puzzles
or e.g. when searching for puzzles with particular properties, like 17 clues or with clues matching a pattern template

[hobiwan]

Draco, these 3 puzzles are easy. So its not the case, that harder puzzles also need more time for programs ?

It's probably true for a logic solver but not necessarily for a backtracking solver. The easter monster for example takes about 12.000 iterations till all possible paths are tried. Puzzle #42341 takes over 760.000.

15 vs. 234 may not be much for one puzzle, but its an order of magnitude, and that could make
a big differences on a collection of 100s or 1Ms or puzzles

And of course the question remains, whether #42341 marks the upper end or whether another magnitude is still waiting (and whether using hidden singles reduces the possible paths as drastically as it does with the above puzzles).

[Draco]

A backtracking or recursive solver, as Hobiwan notes, cares for nothing other than how many possible moves there are. Exactly how many/how long it takes depends on the method the solver implements, and where it starts "guessing" vs. where the solution lies. For 9x9 puzzles it just goes pretty darn fast as long as the code is clean.

Friends with much more math knowledge than me tell ms that Sudoku is an NP-hard problem, meaning that the iterations required to solve it increase exponentially as the # of squares increase. In some sense I get that, but I also know that the solution space starts to collapse very rapidly as you try out values, so perhaps it is really just polynomial and not exponential... in either case, though, it means T&E / backtracking / recursive solvers start slowing down quickly as the # of squares goes up (see that CMU presentation noted in my prior post).

The crazy thing is that, insofar as I can tell, logic solvers on 9x9 puzzles will on the whole be slower than recursive solvers. On larger puzzles you may be able to make that up, but that isn't clear to me. Logic solvers still need to examine many, many patterns and the number of patters to be searched will increase at the same rate as the solution space for a recursive solver (I can't prove that but I would assert that). But I suppose that if all you are seeking is a logic step, it is ok to spend a few seconds searching vs. spending many dozens of seconds looking for the entire solution.

Since I have found enough interesting problems in the 9x9 puzzle space, this is all intellectually interesting, but nothing I would plan to tackle in the foreseeable future

Cheers...

- drac

[Pat]

re: oysterkite's 17-clue puzzle
in my earlier post,
i quoted the puzzle as posted by Jo88 (2006.Mar.28)

that was not smart --
i should've gone back to the previous page of that Topic
where oysterkite (2006.Mar.7) tells us how he created that specific 17-clue puzzle !!

when the puzzle is used in "Solving sudokus by a brute-force algorithm"
( in the WikiPedia article on "Algorithmics of sudoku" ),
it is interesting to note that Lithiumflash (2007.May.13) states --

I created this sudoku puzzle,
and created the jpg image of it.

[Draco]

also, to measure timings in the noise, do the timing on say 1000 copies of the same puzzle
15 vs. 234 may not be much for one puzzle, but its an order of magnitude, and that could make
a big differences on a collection of 100s or 1Ms or puzzles
or e.g. when searching for puzzles with particular properties, like 17 clues or with clues matching a pattern template

Excellent point about noise; to be really clean one should defrag and reboot between runs, let nothing else run (what if your iTunes updater decides to download the latest version in the middle of your test?) and pre-load the EXEs and DLLs (honestly - virtual memory and the page layout can have huge impacts on timings) then run many, many iterations as you say.

I did none of that and I should know better. Thanks for reminding me

Also agree with your points regarding backtracking implementation.

Cheers...

- drac