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/