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/