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

Re: Sudoku puzzle

• To: mathgroup at smc.vnet.net
• Subject: [mg58378] Re: Sudoku puzzle
• From: Paul Abbott <paul at physics.uwa.edu.au>
• Date: Wed, 29 Jun 2005 01:38:01 -0400 (EDT)
• Organization: The University of Western Australia
• References: <d9r4vd$560$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

In article <d9r4vd$560$1 at smc.vnet.net>,
 Mike Honeychurch <M.honeychurNOSPAMch at uq.edu.au> wrote:

> Many readers would be aware that Sudoku is a puzzle (craze) that has
> recently appeared in many major newspapers around the world as a regular
> puzzle.
> 
> (See http://www.sudoku.com and http://www.sudokufun.com/

See also:

  http://www.economist.com/business/displayStory.cfm?story_id=3992476

An example of solving a (simple) Sudoku (not using back-tracking of 
checking for contradictions) by Bobby Treat appeared in The Mathematica 
Journal 9(3): 528-531.

> An open source sudoku project exists with a Java applet available at
> sourceforge: http://sudoku.sourceforge.net/)

Perhaps a J/Link solution is available then?
 
> Mathematica in Education and Research would like to issue a challenge to the
> Mathematica community to create a Mathematica version of Sudoku: a package
> that both creates Sudoku puzzles and solves them (either totally within a
> notebook or via the GUI interface).
> 
> Please submit your Sudoku version as an article for Mathematica in Education
> and Research describing the code and the (presumed?) challenges faced and
> overcome in writing the code.

A search at The Weekend Australian website gives links to a sudoku solver

  http://rightside.fissure.org/sudoku.cgi

and to the wikipedia entry

  http://en.wikipedia.org/wiki/Sudoku

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.

Another case is where you three "related" entries (same row, column, or 
sub-square), two of the entries have only two possibilities, say

  4 or 5

and the third one has, say, three possibilities,

  4 or 5 or 6

Then it is clear that this last entry must be 6.

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?

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/