Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

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