NAME

Games::Pentominos - solving the pentominos paving puzzle

SYNOPSIS

  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);

DESCRIPTION

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.

METHODS

solve

  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.

ALGORITHM

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).

AUTHOR

Laurent Dami, <laurent.d...@justice.ge.ch>

COPYRIGHT & LICENSE

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.