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