Laurent Dami >
Games-Pentominos-1.0 >
Games::Pentominos

Module Version: 1.0
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 :

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.

syntax highlighting: