Polymino Tiling Software and Example Pentomino Tiling Solutions

A 1986,1987,2007 self-directed software study in two-dimensional tiling solutions
by Scott Kurowski

TERMS:
(c) 1987, 1997, 2007 Scott Kurowski, all rights reserved - Free license use granted PROVIDED run-time
citations of software source and scott@scottkurowski.com are in same view as software version.
NO LIABILITIES OR WARRANTIES ARE OFFERED OR IMPLIED.

1.0 Introduction

With a little work this old Borland Turbo Pascal 3.0 code could be brought back to life.
An ambitious student should be able to make short work of it.  At any rate, I thought it
might get reused by another person looking for just this sort of software, on the Internet.

It was Arthur Clarke's 'Imperial Earth' that got me started on this project in my second year
of junior high school, around 1978.  Long before I knew how to apply a computer to puzzles I
made sets of wooden and plastic pentominos and cataloged my solutions in a notebook.
After finding and writing down several dozen solutions I gave up on this manual method.
In high school around 1981 I read an article in BYTE magazine where pentominoes were tiled
using assembly code on a ~1 MHz 6502 Apple computer, from which I used the piece/orientation
permuation method.  When in 1985 I bought my first personal computer I realized it might be
possible to resume and complete this catalog.  Why not?

So in summer of 1986 I wrote most of this software and used it to generate the pentomino
piece image tables, the tiling solutions and the 'sifted' unmirrored solutions.  I wrote
the printing code several months later, and printed them out still later in fall 1987.

Back then, my 8 Mhz Intel 80186 CPU required over a week non-stop computing to solve the
6x10 tiling permutations.  In 1987, my 200 Mhz Pentium Pro repeats this feat in 3.75 hours,
sifted out the redundant reflections to catalog the 2339 unique solutions in 53 minutes.

In 2007 my 4-year-old 2.0 GHz Windows XP laptop repeated this search in 0.9 hours and
sifted them in 0.2 hours.


2.0 Software Contents

There are 4 Pascal programs.  Their input and output file names are hard coded, but I changed the
names for each set of Pentomino solutions I solved with it.  The files created by these programs
include everything for the 3x20, 4x15, 5x12, 6x10 and 8x8 with a 2x2 hole in several different
positions.  Due to storage constraints, I long ago discarded some of the unsifted .SOL files.

gener.pas	Creates images of all possible orientations and rotations of 2-dimensional
   output:	polymino objects, in this case pentomino pieces.  It used keyboard input for
     .MAP file	the polymino square coordinates, and produced .MAP files.

poly.pas	Polymino tiling solution generator.  This uses the image tables created by
   input:	gener.pas, and exhaustively tiles these images into a box you define for it.
     .MAP file 	For pentominos, this was typically 3x20, 5x12, etc. The program tiles 4
  output:	reflections of the same solution, unless there is no axis of symmetry, as
     .SOL file	in the case of 8x8 with a central 2x2 hole - in this case 8 solutions are
                tiled.  I called 3 (or 7) of these reflections 'mirror images'.  It reads
                .MAP files and produces .SOL (solution) files. It has been left customized
                for the 6x10 catalog, which I regenerated to benchmark the Pentium time.

sift.pas	Polymino tiling solution mirror image solution filter.  I used this to take out
    input:	the redundant 3 (or 7) reflections of each 'real' solution.  It reads the .SOL
      .SOL file	files and produces .SFT ('sifted') solution files.
   output:
      .SFT file

dump.pas	Polymino screen plotting of tiling solutions.  It neatly tiled the video monitor
setpoint.p	with polymino solutions in high-resolution graphics, and called SCRNDUMP,
		which printed the screen (before PrintScrn keys, kids).

If you need help, contact me at entropy@scottkurowski.com.
All e-mails receive replies.