# 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.

• 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://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://hodoku.sourceforge.net/en/docs_play.php#filters
• http://hodoku.sourceforge.net/en/tech_intersections.php#lc1
• 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://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