<< sudoku_solvebylogic Solve sudoku_solvesa >>

Sudoku Toolbox >> Solve > sudoku_solverecursive

sudoku_solverecursive

Solves Sudoku using naked singles and recursive backtracking.

Calling Sequence

Y = sudoku_solverecursive ( X )
Y = sudoku_solverecursive ( X , verbose )
Y = sudoku_solverecursive ( X , verbose , level )
[Y,maxlevel] = sudoku_solverecursive ( ... )

Parameters

X:

a 9-by-9 matrix, with 0 for unknown entries

verbose:

a boolean. Set to %t to display the state of the matrix. (default = %f)

level :

the current level of recursive backtracking

maxlevel:

the maximum level of the call tree in the nested recursive search used in the guess-based strategy

Description

Using Recursive Backtracking. From an algorithm published in The Mathworks News and Notes, 2009.

There are several main improvements over the original algorithm. The matrix of candidates used in the logic process searching for naked singles is updated instead of being re-computed each time. When guessing is necessary, we do not take the first empty cell, but chose the cell with the lowest number of candidates. When we browse the candidates, we permute randomly the candidates so that the routine can be used to generate random grids.

Examples

X = [
0 0 0   0 0 0   0 0 0
0 0 0   0 0 0   5 3 0
9 0 0   0 3 7   0 0 0
0 0 2   3 0 1   0 9 6
0 4 7   6 9 0   1 8 0
0 0 6   7 8 5   0 0 0
0 5 0   0 2 0   9 0 3
0 3 0   9 0 0   6 0 8
8 0 0   0 1 0   4 7 0
]
sudoku_solverecursive(X)

X = [
0 0 0   0 0 0   0 0 0
9 0 0   0 0 4   0 3 6
0 0 0   0 7 2   0 0 9
3 0 0   0 0 0   0 0 5
0 1 4   0 0 0   8 0 0
0 2 5   0 1 0   0 0 0
0 0 6   1 0 0   0 0 3
0 0 0   0 0 6   0 4 0
0 0 2   4 8 9   0 0 0
]
sudoku_solverecursive(X)

X = [
1 2 0    0 3 0    0 4 0
6 0 0    0 0 0    0 0 3
3 0 4    0 0 0    5 0 0
2 0 0    8 0 6    0 0 0
8 0 0    0 1 0    0 0 6
0 0 0    7 0 5    0 0 0
0 0 7    0 0 0    6 0 0
4 0 0    0 0 0    0 0 8
0 3 0    0 4 0    0 2 0
]
sudoku_solverecursive(X)

X = [
0 2 0   0 3 0   0 4 0
6 0 0   0 0 0   0 0 3
0 0 4   0 0 0   5 0 0
0 0 0   8 0 6   0 0 0
8 0 0   0 1 0   0 0 6
0 0 0   7 0 5   0 0 0
0 0 7   0 0 0   6 0 0
4 0 0   0 0 0   0 0 8
0 3 0   0 4 0   0 2 0
]
sudoku_solverecursive(X)

Authors


<< sudoku_solvebylogic Solve sudoku_solvesa >>