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

Download:
Games-Pentominos-1.0.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 1.0   Source  

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

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.

syntax highlighting: