MathGroup Archive 2005

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

Search the Archive

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/


  • Prev by Date: Re: poly question
  • Next by Date: Re: Can't assign value to symbols
  • Previous by thread: Re: Sudoku puzzle
  • Next by thread: Re: Sudoku puzzle