Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: John R Jones on 18 Aug 2005 08:31 r.e.s. wrote: > "John R Jones" <a1jrj(a)hotmail.com> wrote ... > > I then wrote a macro to copy the musts to the puzzle cells, > > re-apply the algorithms and iterate until there are no more > > musts. > > The idea was that I would then only have to guess some values > > and backtrack manually. > > However, I have yet to find a puzzle that isnt automatically > > filled in by the blessed thing :-(. > > Any really tough ones out there? > > Try it on this one: > > . . . | . 7 . | 3 . . > 5 . . | . 1 . | . . 6 > . 9 . | . . 2 | . . . > ---------------------- > 8 . . | . . 5 | . 9 . > . . . | . 4 . | . . . > . 2 . | 1 . . | . . 7 > ---------------------- > . . . | 9 . . | . 8 . > 4 . . | . 6 . | . . 3 > . . 7 | . 3 . | . . . > > --r.e.s. 1 4 8 5 7 6 3 2 9 5 3 2 4 1 9 8 7 6 7 9 6 3 8 2 1 4 5 8 1 3 7 2 5 6 9 4 9 7 5 6 4 3 2 1 8 6 2 4 1 9 8 5 3 7 3 6 1 9 5 7 4 8 2 4 8 9 2 6 1 7 5 3 2 5 7 8 3 4 9 6 1 That was tough - I went to eight levels of backtracking. JJ
From: on 18 Aug 2005 12:15 In article <1124368315.034376.107930(a)g49g2000cwa.googlegroups.com>, "John R Jones" <a1jrj(a)hotmail.com> writes: > >r.e.s. wrote: >> "John R Jones" <a1jrj(a)hotmail.com> wrote ... >> > I then wrote a macro to copy the musts to the puzzle cells, >> > re-apply the algorithms and iterate until there are no more >> > musts. >> > The idea was that I would then only have to guess some values >> > and backtrack manually. >> > However, I have yet to find a puzzle that isnt automatically >> > filled in by the blessed thing :-(. >> > Any really tough ones out there? >> >> Try it on this one: >> >> . . . | . 7 . | 3 . . >> 5 . . | . 1 . | . . 6 >> . 9 . | . . 2 | . . . >> ---------------------- >> 8 . . | . . 5 | . 9 . >> . . . | . 4 . | . . . >> . 2 . | 1 . . | . . 7 >> ---------------------- >> . . . | 9 . . | . 8 . >> 4 . . | . 6 . | . . 3 >> . . 7 | . 3 . | . . . >> >> --r.e.s. >1 4 8 5 7 6 3 2 9 >5 3 2 4 1 9 8 7 6 >7 9 6 3 8 2 1 4 5 >8 1 3 7 2 5 6 9 4 >9 7 5 6 4 3 2 1 8 >6 2 4 1 9 8 5 3 7 >3 6 1 9 5 7 4 8 2 >4 8 9 2 6 1 7 5 3 >2 5 7 8 3 4 9 6 1 >That was tough - I went to eight levels of backtracking. According to my understanding of the rules of Sudoku, you are not supposed to use backtracking at all when solving them. That is one of the rules or conventions that makes it interesting. Of course, it is possible that some puzzles, and maybe this one (I have not tried very hard), cannot be solved without backtracking. If so, that would mean that they would not be legitimate Sudoku puzzles. I have not yet come across a printed puzzle in the press that I have been unable to solve without using backtracking. Derek Holt.
From: Torkel Franzen on 18 Aug 2005 12:17 mareg(a)mimosa.csv.warwick.ac.uk () writes: > According to my understanding of the rules of Sudoku, you are not > supposed to use backtracking at all when solving them. I very much doubt that the rules specify which kinds of search algorithms are allowed.
From: Jim Gillogly on 18 Aug 2005 12:20 On Thu, 18 Aug 2005 18:17:02 +0200, Torkel Franzen wrote: > mareg(a)mimosa.csv.warwick.ac.uk () writes: > >> According to my understanding of the rules of Sudoku, you are not >> supposed to use backtracking at all when solving them. > > I very much doubt that the rules specify which kinds of search > algorithms are allowed. Agreed. They do say that the solution must be unique, however. I occasionally come to one where I need to guess a number, ripple it through, and come back to that point if I rippled it the wrong way. -- Jim Gillogly
From: Volker on 18 Aug 2005 08:49
Hi, > I very much doubt that the rules specify which kinds of search > algorithms are allowed. not a rule, but a convention of many 'suppliers' is like that. Look e.g. at http://www.dailysudoku.co.uk/sudoku/faq.shtml There, it says: in Q4: > SuDokus from the Daily SuDoku are always solvable using > logic alone. You should never have to employ trial and > error tactics. Again, we can't speak for puzzles from > other sources. I think, that points out the situation. Best regards Volker |