Help-Site Computer Manuals
Software
Hardware
Programming
Networking
  Algorithms & Data Structures   Programming Languages   Revision Control
  Protocols
  Cameras   Computers   Displays   Keyboards & Mice   Motherboards   Networking   Printers & Scanners   Storage
  Windows   Linux & Unix   Mac

Games::Pentominos
solving the pentominos paving puzzle

Games::Pentominos - solving the pentominos paving puzzle


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.

Programminig
Wy
Wy
yW
Wy
Programming
Wy
Wy
Wy
Wy