Re: Sudoku puzzle

*To*: mathgroup at smc.vnet.net*Subject*: [mg58414] Re: Sudoku puzzle*From*: Paul Abbott <paul at physics.uwa.edu.au>*Date*: Fri, 1 Jul 2005 02:02:11 -0400 (EDT)*Organization*: The University of Western Australia*References*: <d9r4vd$560$1@smc.vnet.net> <da0fn3$j2a$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

In article <da0fn3$j2a$1 at smc.vnet.net>, "Jon McLoone" <jonm at wolfram.co.uk> wrote: > 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/ Very nice. One thing that would make it more visual is to have an option to show progress towards the solution (as was done in the TMJ article). Showing the solution a step at a time would be particularly useful if you are solving the puzzle by hand, get stuck, and want a hint. Since there are many people out there solving Sudoku puzzles, perhaps a webMathematica page using your solver would be a nice hook for webMathematica and Mathematica? > > 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. That is essentially my question. All the puzzles published in newspapers, even the "Very Hard" ones, have a unique solution and, rejecting full enumeration as a way to avoid backtracking, I suspect as you do that backtracking is not required, and that at each stage of the solution, at least one entry can be filled in. Indeed, for all the newspaper examples I've tried with your package, setting ShowSteps -> True generates no intermediate output. Cheers, Paul -- Paul Abbott Phone: +61 8 6488 2734 School of Physics, M013 Fax: +61 8 6488 1014 The University of Western Australia (CRICOS Provider No 00126G) AUSTRALIA http://physics.uwa.edu.au/~paul http://InternationalMathematicaSymposium.org/IMS2005/