Re: Sudoku puzzle

*To*: mathgroup at smc.vnet.net*Subject*: [mg58397] Re: Sudoku puzzle*From*: "Jon McLoone" <jonm at wolfram.co.uk>*Date*: Thu, 30 Jun 2005 05:10:30 -0400 (EDT)*References*: <d9r4vd$560$1@smc.vnet.net><d9tco2$388$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

> The wikipedia article shows that the code presented in TMJ 9-3 is > deficient in that there are situations in which no unique solution at > each stage is found even though there exist squares for which a unique > value is determined. Here is a simple example: > > . . . | 1 . . | . . . > . . . | . . . | . . . > . . . | . . . | . . . > --------------------- > . . . | . 7 . | . . . > . . . | . . . | . . . > . . . | . 9 . | . . . > --------------------- > . . . | . . . | . . . > . . . | . . . | . . . > . . . | . . 1 | . . . > > Just given this much information it is clear that there must be a 1 in > the {5,5} square. A short solution, which I placed on Mathsource last week, applies two basic rules before resorting to backtracking. The rules are sufficient to find the 1 at {5,5} in this example. http://library.wolfram.com/infocenter/MathSource/5690/ > The solutions by Fred Simons and Andrzej Kozlowski (previously posted to > MathGroup) involving backtracking work fine (I did not select their > solutions for TMJ because it did not show progress towards the solution) > -- but I wonder if for the sudoku puzzles whether backtracking is ever > required? I think that any general solver must implement backtracking to deal with under-specified problems, where there are multiple solutions, such as the one shown above. There is insufficent information to proceed once the {5,5} position is found, so a guess must be made for one of the remaining positions. You can only know whether that guess is consistant with solution by atempting to solve it and back tracking on a contradiction. If that wasn't true then you would have been able to proceed. I would guess that puzzles with a single unique solution can all be solved without backtracking, but the two rules that I implemented are insufficent on the more difficult problems. Jon McLoone