sudoku

sudoku, an Octave code 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 may swap two rows if they are in the same row of boxes. You may swap two columns if they are in the same column of boxes. You may swap two columns of boxes, or two rows of boxes. Each of these operations preserves the underlying structure of the Sudoku.

Licensing:

The information on this web page is distributed under the MIT license.

Languages:

sudoku is available in a MATLAB version and an Octave version.

Related Data and Programs:

sudoku_test

combo, an Octave code which includes several examples of backtracking routines used to solve problems such as the placement of Queens on a chessboard.

exm, an Octave code which contains scripts and data discussed in the electronic textbook "Experiments with Matlab", by Cleve Moler, including easter, Fast Fourier Transforms, Fibonacci numbers, the fractal fern, the game of Life, magic matrices, the Mandelbrot set, Morse code, Music, Ordinary Differential Equations, the page rank algorithm, planetary orbits, predator prey equations, the shallow water equations, Sudoku puzzles.

puzzles, an Octave code which solves various puzzles.

subset, an Octave code which includes several examples of backtracking routines used to solve problems such as the number of derangements (complete scramblings) of a set.

Author:

The original MATLAB version of sudoku_solve() was written by GM Boynton. This version by John Burkardt.

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.

Source Code:

• sudoku_box_column_swap.m, swaps two columns of boxes in a Sudoku puzzle.
• sudoku_box_invert.m, "inverts" all the Sudoku boxes through the center box.
• sudoku_box_row_swap.m, swaps two rows of boxes in a Sudoku puzzle.
• sudoku_check.m, examines a partially filled-in Sudoku, and checks that it is legal (digits are 0, or between 1 and 9, no repeats in rows, columns or boxes).
• sudoku_choice.m, determines the number of remaining choices in a Sudoku puzzle based just on row, column and box checks.
• sudoku_choice_prints.m, prints the choices available in each box.
• sudoku_digit_permute.m, permutes the digits in a Sudoku puzzle.
• sudoku_line_column_swap.m, swaps two columns that share the same box column in a Sudoku puzzle.
• sudoku_line_row_swap.m, swaps two rows that share the same box row in a Sudoku puzzle.
• sudoku.m, prints a partial or complete Sudoku puzzle.
• sudoku_reflect.m, reflects a Sudoku puzzle across the 0, 45, 90 or 135 degree lines.
• sudoku_rotate.m, rotates a Sudoku puzzle by 90 degrees.
• sudoku_solve.m, solves a Sudoku puzzle.