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

```

• Prev by Date: Re: Re: ListInterpolation
• Next by Date: Re: Sudoku puzzle
• Previous by thread: Re: Sudoku puzzle
• Next by thread: Re: Sudoku puzzle