NAME

DLX - Dancing Links Algorithm for Exact Cover Problems Extended to Solve Sudoku Puzzles (and generalizations of Sudoku)

SYNOPSIS

my $puzzle = [
    [0, 2, 0, 0, 7, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 8, 4, 0],
    [0, 0, 0, 5, 0, 0, 1, 0, 0],
    [9, 0, 0, 0, 1, 0, 7, 6, 4],
    [5, 0, 0, 0, 6, 0, 0, 0, 0],
    [4, 0, 0, 0, 9, 0, 0, 3, 0],
    [0, 0, 7, 9, 0, 0, 0, 0, 0],
    [0, 3, 0, 4, 0, 0, 0, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 8],
];

my $solutions = solve_sudoku(
    puzzle  => $puzzle,
    regions => [ [1,9], [9,1], [3,3] ],
);

print "No solutions found\n" unless @$solutions;

my $solution_count = 0;
for my $solution (@$solutions) {
    $solution_count++;
    print "\n" unless $solution_count == 1;
    print "Solution $solution_count:\n";
    my $puzzle_solution = [];
    for my $cell (@$solution) {
        my ($r, $c, $n) = $cell =~ /(\d) (\d) (\d)/;
        $puzzle_solution->[$r][$c] = $n;
    }
    for my $row (@$puzzle_solution) {
        print join(" ", @$row), "\n";
    }
}

DESCRIPTION

This module implements the Dancing Links (DLX) algorithm for solving exact cover problems and extends it to solve generalizations Sudoku. These puzzles include Sudoku Pair Latin Squares as well as Factor Pair Latin Squares

METHODS

solve_sudoku

takes a puzzle and a list of regions and returns a list of solutions.

puzzle

A reference to a 2D array representing the puzzle. Each cell should contain a number between 0 and the size of the puzzle.

regions

A reference to a list of regions. Each region is a reference to a 2-element array representing the dimensions of the region. The product of the dimensions of each region should be equal to the size of the puzzle.

AUTHOR

James Hammer <james.hammer3@gmail.com>

LICENSE

This module is licensed under the same terms as Perl itself.