Games::Pentominos - solving the pentominos paving puzzle |
Games::Pentominos - solving the pentominos paving puzzle
use Games::Pentominos;
my $board = "xxxxxxxxxx\n" x 6; my $solution_printer = sub { my ($placed, $n_solutions, $t_solution, $t_tot) = @_; printf "Solution %d\n%s\n", $n_solutions, $placed; return 1; # continue searching }
Games::Pentominos->solve($board, $solution_printer);
A pentomino is a surface formed from 5 adjacent squares; there are exactly 12 such pieces, named by letters [FILPSTUVWXYZ] because their shape is similar to those letters. The puzzle is to fit them all in a board of 60 cells; the most common board is a rectangle of 6x10 cells.
This module contains the solving algorithm, while the companion program the pentominos manpage contains the command-line interface to launch the solver.
Games::Pentominos->solve($board, $solution_callback);
The $board
argument should contain a string
representing the board on which to place pentominos. The string must
be a concatenation of rows of equal length, each with a final
"\n"
. Empty cells are represented by an 'x'
. Cells outside the
paving surface -- if any -- are represented by a dot. So for
exemple the U-shaped board is represented as :
xxxx....xxxx xxxx....xxxx xxxx....xxxx xxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxx
The $solution_callback
is called whenever a solution is found, as follows
$should_continue = $callback->($placed, $n_solutions, $t_solution, $t_tot);
where
$placed
is a string representing the board, in which every cell 'x'
has been replaced by the letter name of the pentomino filling that cell.
As in the input board, cells outside the
paving surface -- if any -- are represented by a dot.
$n_solutions
is a counter of solutions
$t_solution
is a float containing the number of seconds and milliseconds
spent computing this solution
$t_tot
is the total time spent for all solutions so far.
If the return value from the callback is true, then the computation continues to find a new solution; otherwise it stops.
For every possible permutation of each pentomino, we compile a subroutine that just attempts to perform a regular expression substitution on the board, replacing empty cells by the pentomino name.
At any point in time, the global variable $board
contains the
description of cells remaining to be filled, while $placed
contains
the description of cells already filled. The algorithm starts at the
first character in $board
(the first empty cell), and iterates over
pentominos and permutations until finding a successful substitution
operation. It then removes all initial non-empty cells (storing them
in $placed
), and recurses to place the next pentomino. Recursion
stops when $board
is empty (this is a solution).
Laurent Dami, <laurent.d...@justice.ge.ch>
Copyright 2007 Laurent Dami, all rights reserved.
This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
Games::Pentominos - solving the pentominos paving puzzle |