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 pentominos 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 :
$board
"\n"
'x'
xxxx....xxxx xxxx....xxxx xxxx....xxxx xxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxx
The $solution_callback is called whenever a solution is found, as follows
$solution_callback
$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.
$placed
$n_solutions is a counter of solutions
$n_solutions
$t_solution is a float containing the number of seconds and milliseconds spent computing this solution
$t_solution
$t_tot is the total time spent for all solutions so far.
$t_tot
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>
<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.
To install Games::Pentominos, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Games::Pentominos
CPAN shell
perl -MCPAN -e shell install Games::Pentominos
For more information on module installation, please visit the detailed CPAN module installation guide.