sudoku

sudoku

Sudoku Toolbox

Purpose

The goal of this toolbox is to provide algorithms to manage sudoku.

We provide algorithms to solve sudokus:

  • solving Sudoku Using Recursive Backtracking.
  • solving sudoku with a combination of necessary entries, single candidates and recursive guesses.

We provide 2 specific algorithms to fill a sudoku:

  • fill it by necessary entries,
  • fill single candidates.

We provide 3 algorithms to generate sudokus. The toolbox allows to randomly permute the rows of a sudoku or to order it into a canonical form. We provide an algorithm to fill a random sudoku and to delete random entries inside it. We can see if a sudoku is solved and compute candidates for each entry.

Features

Algorithms

  • sudoku_candidatefind — Find a candidate in the sudoku.
  • sudoku_candidateprint — Find and print a candidate in the sudoku.
  • sudoku_candidateremove — Remove a candidate.
  • sudoku_candidates — Returns candidates for a sudoku X.
  • sudoku_candidatescell — Returns candidates for a cell in a sudoku.
  • sudoku_candidatesmerge — Merge candidates in the row, column or block.
  • sudoku_cellcandidates — Returns candidates for a cell in a sudoku.
  • sudoku_confirmcell — Confirm the value of a cell.
  • sudoku_findhiddensubset — Find naked subsets of given length.
  • sudoku_findlocked — Search for locked candidates.
  • sudoku_findnakedsubset — Find naked subsets of given length.
  • sudoku_findtwocolors — Search for pairs.
  • sudoku_findxcycle — Search for pairs.
  • sudoku_findxwing — Find X-Wings.
  • sudoku_iscandsingle — See if a candidate is single.
  • sudoku_islatin — Check if a matrix is a Latin Square.
  • sudoku_issolved — See if the sudoku is solved.
  • sudoku_locatenakedsubset — Find naked subsets of given length and returns the associated rows and columns.
  • sudoku_visiblefrom — Compute the cells visible from cell a.
  • sudoku_visiblefrom2 — Compute the cells visible from both cell a and b.

Generate

  • sudoku_create — Generate a puzzle and its solution.
  • sudoku_delrandom — Deletes entries at random in a sudoku.
  • sudoku_fillrandom — Generate a random sudoku.
  • sudoku_generate — Generate a puzzle and its solution.
  • sudoku_generate2 — Generate a puzzle and its solution.
  • sudoku_generate3 — Generate a puzzle and its solution.
  • sudoku_rootsolution — Returns the root solution.

Read/Write

  • sudoku_print — Print a sudoku.
  • sudoku_readgivens — Read a sudoku from a string of 81 givens.
  • sudoku_readsdk — Read a sudoku in a .sdk file.
  • sudoku_readsdm — Read a sudoku in a .sdm file.
  • sudoku_readsdmnb — Returns the number of sudoku in a .sdm file.
  • sudoku_readss — Read a sudoku in a .ss file.
  • sudoku_writegivens — Returns the given sudoku as a string of 81 givens.
  • sudoku_writesdk — Returns the given sudoku as a sdk string.
  • sudoku_writess — Returns the given sudoku as a Simple Sudoku format.

Solve

  • sudoku_solve — Solves Sudoku.
  • sudoku_solveai — Solves Sudoku.
  • sudoku_solvebylogic — Solves Sudoku.
  • sudoku_solverecursive — Solves Sudoku using naked singles and recursive backtracking.
  • sudoku_solvesa — Solves Sudoku.

Utilities

  • sudoku_latinsquare — Create Latin Squares of order n.
  • sudoku_order — Order a sudoku.
  • sudoku_permute — Permute a sudoku.
  • sudoku_getpath — Returns the path to the current module.

Dependencies

  • When updating the help pages, this module requires the helptbx module.
  • This module requires the assert module (for the unit tests).

TODO

  • http://www.sadmansoftware.com/sudoku/blockcolumnrow.htm
  • http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4666791%2F4667925%2F04667974.pdf%3Farnumber%3D4667974&authDecision=-203
  • http://www2.research.att.com/~gsf/

Authors

  • Stefan Bleeck, 2005
  • Cleve Moler, 2009
  • Michael Baudin, 2010

Bibliography

  • http://magictour.free.fr/top1465
  • http://www.mathworks.com/matlabcentral/fileexchange/14073
  • http://www.stolaf.edu/people/hansonr/sudoku/
  • http://units.maths.uwa.edu.au/~gordon/sudokumin.php, Royle Gordon
  • http://www.sadmansoftware.com/sudoku/faq19.htm
  • http://hodoku.sourceforge.net/en/docs_play.php#filters
  • http://hodoku.sourceforge.net/en/tech_intersections.php#lc1
  • http://www.sudocue.net/dancinglinks.htm
  • http://sourceforge.net/projects/dancinglinks/
  • http://www.setbb.com/phpbb/viewforum.php?f=3&sid=2ef5000efb13f8513ff669aec7cdccf2&mforum=sudoku
  • http://www.sudoku.com/boards/viewtopic.php?t=4212
  • http://www.sudopedia.org/wiki/Main_Page
  • http://sudokublog.typepad.com/sudokublog/sudoku_tips/
  • http://sudokublog.typepad.com/sudokublog/2005/08/two_and_three_i.html
  • http://sudokublog.typepad.com/sudokublog/2005/08/xwings.html
  • http://www.sudocue.net/guide.php
  • http://www.sudokuwiki.org/sudoku.htm
  • http://www.setbb.com/phpbb/?mforum=sudoku

Books

  • "Programming Sudoku", Wei-Meng Lee, 2006
  • "Enumerating possible Sudoku grids", Bertram Felgenhauer, Frazer Jarvis, June 2005
  • "The mathematics of Sudoku", Tom Davis, 2008
  • "A Z of Sudoku", Narendra Jussien
  • "Précis Sudoku", Narendra Jussien
  • "Y a-t-il des mathématiques Derrière Les Grilles de Sudoku", Hiriart - Urruty, Quadrature
  • "A Sudoku Solver", Schermerhorn
  • "Sudokus et algorithmes de recuit", Syrdey, 2006
  • "Sudo-Lyndon", Richomme, 2007
  • "Solving_Sudoku", Michael Mepham, 2005
  • "A search based Sudoku solver", Cazenave
  • "AI examples", Arto Inkala
  • "A Sudoku program in Fortran 95", Metcalf, 2006
  • "Metaheuristics can solve sudoku puzzles", Rhyd Lewis, J Heuristics (2007) 13: 387?401
  • "On the Combination of Constraint Programming and Stochastic Search", Lewis, 2007

Licence

This toolbox is released under the CeCILL_V2 licence :

http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt

Development Team
Admins
Allan Cornet
Michael Baudin

Powered by InDefero,
a Céondo Ltd initiative.