# SUDOKU Solve a Sudoku Puzzle

SUDOKU is a MATLAB library which handles Sudoku puzzles.

The most interesting routine is sudoku_solve.m, which accepts a partially worked-out Sudoku, and returns a solution. It does this by using an exhaustive search. That is, it finds the first empty spot in the grid, and then tries, in turn, putting in each of the digits in that spot. Once it puts in the trial digit, it calls itself again with the slightly more filled-in puzzle. If the routine fills in the whole puzzle, it returns to the user. Otherwise, it backs up to the most recent trial digit, and increases it by one. And if that's not possible, because we got to "9", it sets that cell back to blank, and backs up to the previous trial digit.

If there is a solution, this procedure should find it. However, I don't know what the routine will do if there is no solution. I don't know what the routine will do if there are multiple solutions (I assume it just comes back with one solution.) And the routine does not check that your partially filled input puzzle is consistent (doesn't have a 12 in one cell, or two 5's in one row.)

A Sudoku has a lot of symmetry. You can permute the digits. You can swap two rows if they are in the same row of boxes. You can swap two columns if they are in the same column of boxes. You can swap two columns of boxes, or two rows of boxes. Each of these operations preserves the underlying structure of the Sudoku.

### Related Data and Programs:

COMBO, a MATLAB library which includes several examples of backtracking routines used to solve problems such as the placement of Queens on a chessboard.

GRAPH_PAPER, is a FORTRAN90 library which includes a routine which can print out a partial or complete Sudoku puzzle.

LADDERS, a C program which seeks to transform one five letter word into another, by changing one letter at a time, using only legitimate English words. This puzzle was invented by Lewis Carroll, who called it "Doublets", but it is also known as "Word Ladders" or "Word Gold". The program is by Donald Knuth.

SUBSET, a MATLAB library which includes several examples of backtracking routines used to solve problems such as the number of derangements (complete scramblings) of a set.

### Author:

GM Boynton wrote sudoku_solve.m.

### Reference:

1. Brian Hayes,
Unwed Numbers,
American Scientist,
Volume 94, pages 12-15, January-February 2006.
2. Robin Wilson,
The Sudoku Epidemic,
Focus,
pages 5-7, January 2006.

### Examples and Tests:

You can go up one level to the MATLAB source codes.

Last revised on 22 October 2007..