Sudoku solving algorithms
The class of Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions or zones each of size N cells, to be filled in using a prescribed set of N distinct symbols (typically the numbers {1, ..., N}), so that each row, column and region contains exactly one of each element of the set. The puzzle can be solved using a variety of algorithms. This page provides algorithms and implementations, when appropriate.
Solving sudokus by backtracking
The basic backtracking algorithm can be adapted to solve jigsaw sudokus. This is straightforward. Say a zone is a subset of N boxes of an N x N grid, which must contain the numbers from 1 to N. A standard sudoku contains 27 zones, namely 9 rows, 9 columns and 9 squares that are 3 x 3. In a jigsaw sudoku, the square zones are replaced by zones having irregular boundaries, like a jigsaw piece.
On possible algorithm that uses backtracking to solve such sudokus constructs a graph on vertices, one vertex for each box of the grid. Two vertices are connected by an edge if there exists a zone containing the two boxes. The problem is then equivalent to coloring this graph with N colors, where adjacent vertices may not have the same color. This is done by starting with an empty assignment of colors (for jigsaw sudokus) and assigning colors to vertices one after another, using some fixed order of the vertices. Whenever a color is being assigned, we check whether it is compatible with the existing assignments, i.e. whether the new color occurs among the neighbors of that vertex. If it doesn't, then we may assign it to the vertex and try to process another vertex. We backtrack once all N colors have been tried for a given vertex. If all vertices have been assigned a color, then we have found a solution. There are of course much more sophisticated algorithms to solve graph coloring. If the sudoku contains initial data, i.e. some boxes have already been filled, then these go into the color assignment before backtracking begins and the vertex sequence includes only the empty boxes.
A Perl implementation in just 86 lines of the above algorithm, which is easily translated into other programming languages, is shown below. It solves a 10x10 jigsaw sudoku that was proposed on Les-Mathematiques.net A link to the proposal may be found in the section for external links. The first section of the program defines the 10 jigsaw pieces (zones), the second the row and column zones. Thereafter the graph is constructed as an adjacency list. The search procedure prints completed solutions (when all 100 boxes have been assigned). Otherwise it computes the set of colors present among the neighbors of the next vertex to be processed, and recursively tries those assignments that do not conflict with this set. The search starts with an empty assignment.
#! /usr/bin/perl -w
#
$| = 1;
my $zones =
[[qw(00 10 11 12 20 21 22 30 31 40)],
[qw(01 02 03 04 13 23 33 34 43 44)],
[qw(05 06 14 15 16 24 25 26 35 36)],
[qw(07 08 09 17 18 19 27 28 29 37)],
[qw(32 41 42 51 52 53 61 62 63 72)],
[qw(45 54 55 56 64 65 66 74 75 84)],
[qw(38 39 46 47 48 49 57 58 67 68)],
[qw(50 60 70 71 80 81 82 90 91 92)],
[qw(73 83 93 94 85 86 95 96 97 98)],
[qw(59 69 76 77 78 79 87 88 89 99)]];
foreach my $a (0..9){
my $z = [ map {
"$a" . $_
} (0..9) ];
push @$zones, $z;
$z = [ map {
$_ . "$a"
} (0..9) ];
push @$zones, $z;
}
my $adj;
foreach my $z (@$zones){
foreach my $a (0..9){
foreach my $b (0..9){
push @{$adj->{$z->[$a]}}, $z->[$b]
if $a != $b;
}
}
}
|
sub search {
my ($n, $sol) = @_;
if($n==100){
foreach my $a (0..9){
print $sol->{$a . '0'};
foreach my $b (1..9){
print ' ' . $sol->{$a . $b};
}
print "\n";
}
print '-' x 19; print "\n";
return;
}
my ($a, $b);
$b = $n % 10; $a = ($n - $b)/10;
my $box = "$a$b";
my %set;
my $nbs = $adj->{$box};
foreach my $nb (@$nbs){
if(defined($sol->{$nb})){
my $val = $sol->{$nb};
$set{$val} = 1;
}
}
foreach my $val (0..9){
if(not(defined($set{$val}))){
$sol->{$box} = $val;
search($n+1, $sol);
undef($sol->{$box});
}
}
}
search(0, {});
|