Solving the Pentomino Problem

 

hexedalphabet

 

johngfletchersmethod

Ever since my brother, Charles, introduced me to the "pentomino problem" with his hexed puzzle and sent me John G. Fletcher's Paper in 1967, I considered writing a computer program to mimic Fletcher's Fortran Assembly Program (FAP) for the IBM 7094 Computer. In 1967 I had just graduated from the University of Colorado with a B.S. Degree in Mathematics, and had just started learning Fortran on an IBM 7030, at the Naval Weapons Lab in Dahlgren, Va. As computers got faster every year I wondered if someday a brute force solution might be possible; In 2016 I read N.G. de Bruijn's Paper which discusses the futility of a brute force solution. His conclusion was that it would take about 100 million years for a computer to find all of the solutions after searching through 3,909,188,328,478,827,879,681 possibilities. If I had been enterprising enough I probably could have assembled Fletchers Code on the STRETCH (IBM 7030) at NWL and found a few solutions even if the computer time for all solutions would have been too expensive. By 2012 computers were very inexpensive and also extremely fast, so it was feasible to write my first pentomino solver using the C Programming Language. See pentomc.c . My home computer at that time was fast enough to calculate about one solution per second, but since the program worked by drawing random numbers it could not easily find all solutions. Later that year I discovered a Matlab Program, pentomino.m , on the internet, written by Peter Van Alem which used some of the same numbers for defining the Pentomino Patterns that Fletcher used in his program. After studying pentomino.m I understood the long argument to macro, TEST, which was a key part of Fletcher's Program. Fletcher refers to this "list" in the introduction of his paper:

fletchersmainidea

The figure below shows the long argument to macro, TEST, in Fletchers Fortran Assembly Program for the IBM 7094 Computer. This list contains the 63 possible pentomino patterns in a tree-like structure.

FletchersArgumenttomacroTEST

The following segment of code from Peter Van Alem's Program, Pentomino.m, uses a similar numbering scheme for the 63 pentomino patterns.

matlabpatternlist

Fletcher defines each of the 63 patterns in his list with four numbers to define the location of the pentomino in "ARENA", which was a 32 row by 16 column area that enclosed the 6x10 box for the 12 pentominoes. The squares of ARENA were numbered from 1 to 512 and were counted starting with the top left corner and proceeding from left to right and then down. For example, the U Pentomino shown in the figure below can be represented by the numbers: 2,16,17,18,7. The smallest number covered by this pattern, which is called the lead, L, is 22. The other numbers of the pattern are then calculated by subtracting the lead from them. The last number is the number of the pentomino in the list: F,I,L,N,P,T,U,V,W,X,Y,Z. Notice that by using these 4 numbers relative to the lead square, if the next empty square in ARENA is denoted by NEXT, then when any pentomino pattern (x1,x2,x3,x4,x5) is placed at NEXT, x5 is placed in NEXT, NEXT+x1, NEXT+x2, NEXT+x3, and NEXT+x4.

arenafull

Fletcher chose an 32x16 array of 512 squares so that he could analyze all pentomino problems including the 10x6 problem. In my latest C Programs I define a similar array, F, as shown below. Notice that with this definition of F, a program can use the same numbers as Fletcher used to define the 63 pentomino patterns and a 6x10 rectangular region for solving the problem is obtained by simply flipping the 10x6 region of F which is initialized to 0.

codedarena

Using Pentomino.m as a guide I wrote my first pentomino solver based on Fletcher's Code: pentosolver.c. In 2015, I finally wrote a C Program, fletcher1.c , which used his character string of pentomino patterns to find the solutions to the puzzle. I was disappointed that it ran slower than pentosolver.c and took about 3 minutes to find 2339 solutions on my ASUS X54C Laptop. When I replaced the Character String with an equivalent Integer Array I was gratified by the increase in speed in my new program, fletcher_b.c. It calculates 9356 solutions in about 20 seconds. When I replaced the Integer Array that was analagous to Fletcher's Character String with three Integer Arrays, TEST, LEVEL, and SKIPTABLE, the resulting program, fletcher2.c , calculates 9356 solutions in about 7 seconds on my laptop. (Later I cut this time in half in fletcher7.c) Still this program is very slow compared to a solver written by Terje Mathisen, pento.cpp. He won a contest sponsored by Tenie Remmel in 1997 for creating the fastest computer program to solve the 6x10 pentomino puzzle. On my ASUS X54C Laptop, this program runs in about .4 sec using his slow setting. Terje Mathisen stated in a programming note that it ran in .27 seconds on his laptop which had a Penium-M CPU running at 1.6 GHz. I used the following link to compare my laptop speed with Terje Mathisen's laptop speed. Based on these two benchmarks my computer should run about 7 times faster and solve the puzzle in .27/7 = .04 seconds. Just comparing the CPU Clock Speed of my computer, 2.3 GHz, with that of the IBM 7094 in 1965, .74 MHz, you get a factor of about 3500. Since Fletcher's Program took 600 seconds on an IBM 7094 it should run in 600/3500=.17 seconds on my machine.

http://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i3-2350M+%40+2.30GHz

myx54c

intelcorei3

 

It wasn't untill I thought about something I had read about Fletcher's Method in Donald Knuth's Paper on Dancing Links, (see excerpt below) that I found the key to faster execution times by studying N.G. de Bruijn's Algol60 Program. Donald Knuth's Algorithm, DLX, as presented in this paper, solves exact cover problems which include the 6x10 pentomino problem as well as Sudoku Problems.

donaldknuth

 

Fletcher mentioned in his paper that by restricting the X Pentomino to just one quadrant his program reduced the number of solutions from 9356 to 2339. The part of his program that included this logic wasn't in his published article, but the method of restricting the X Pentomino to one quadrant makes a big difference in computing time. Bruijn's Program places the X Pentomino first before searching for a solution instead of searching for a solution and ignoring those which have X in the wrong quadrant. In my comparison of Fletcher's Method and de Bruijn's Method I was handicapped by not understanding Fortran Assembly Language for the IBM 7094, Algol60, or Dutch. After studying Fletcher's Paper I realized that I could write a C Program based on his ideas without a complete understanding of IBM 7094 Macro Instructions, and even though de Bruijn's Algol60 Program is in Dutch, it was easy to translate Algol60 code to C without translating the words in the program from Dutch to English. In order to compare the two methods I wrote two C Programs: fletcher3.c, and de bruijn.c, and compared their execution times: 42/100 sec. for Fletcher's Method and 68/100 seconds for de Bruijn's Method on my ASUS X54C Laptop. Recently I have written a faster versions: fletcher4ns.c based on Fletcher's Method, and pentom2339.c based on N. G. de Bruijn's Method. The execution times on my Laptop Comuter are: fletcher4ns - 33/100 seconds and pentom2339 - 1/2 seconds. Matt Busche's program, polycube1.2, computes the same results in 58/100 seconds on my Laptop. My C Program, bruijn.c, mimics the original Algol60 Code in Professor Bruijn's Program very well, while my program, fletcher3.c is based on the ideas in Fletcher's Paper, but his Code was Assembly Language and mine is Compiler Language. Fletcher used Assembly Language to achieve the ultimate efficiency. As Fletcher desribes in his paper, the efficiency of his program is based on the use of recursion and macro instructions which solve the problem by processing a list of the 63 possible patterns formed by the 12 pentominos in a nested, tree-like structure which includes 19 groups of tetrominos. Bruijn's Algol60 Program is based on the 12 groups based on pentomino type. In fletcher3.c, fletcher4.c, and bruijn.c I restrict the X Pentomino to one quadrant in the same way as Bruijn did in his Algol60 Code. Fletcher also used this technique in his program. I was surprised at the improvement in execution time when I adopted Bruin's Method of eliminating redundant solutions. The execution time went from about 1.8 seconds to .42 seconds (or .33 seconds in my latest version) I don't know how Fletcher restricted the X Pentomino to just one quadrant because his code doesn't contain that funtion, but Bruijn's Method is efficient because he places the X Pentomino in only one quadrant before searching for solutions. Evidently this is more effiecnt than starting with an empty box and restricting the location of the X Pentomino during the search for solutions. The optimization level of a compiler makes a huge difference in the efficiency of the program, so I always set the optimization flag to O3 with the gnu compiler, gcc. The emphasis on run times for computer programs has diminished as computers have become faster and faster and also much less expensive. Back in 1965, when Fletcher published his paper on pentominoes, an IBM 7094 Computer cost about 3.5 million dollars which would be about 27 million in today's dollars. My 100 dollar laptop solves the puzzle in less than a second and Fletcher's Program required 10 minutes on a 27 million dollar computer. Recently I have been looking at the holes in Fletcher's Method. This is, of course, a joke because his method is perfectly sound. But if you look at the steps taken with his method, holes are formed which would most likely not accur with a human solver. For example look at the hole that is formed in the first few steps of his method as shown below:

 

holes

I have written a C Program, fletcher3hole.c, which eliminates holes like the one shown above. When I enable hole testing in the program it takes 1,523,490 steps in 7/10 secs to solve the puzzle and 4,911,878 steps in 4/10 secs without hole testing. Even though testing for holes in this program reduces steps significantly, this testing increases the execution time by about 3/10 second. Recently I have implemented an efficient way of testing for holes by creating a large table, SCRN[63][60] of acceptable pentomino placements to eliminate obviously bad choices such as the U Pentomino on a side so that a hole is created. ( I used pieceplacer.c and screenwriter.c to produce SCRN[63][60]) When I introduced this table in fletcher4ns.c to create a revised program, fletcher4.c , I noticed execution time reduced from .34 seconds to .30 seconds and steps reduced from 4911878 to 4182508.

 

Fletcher's Method in his own words:

searchforsolutions

In the program, the box is viewed as a portion of a large arena. The cells outside of the box are initialized to 13, and the cells inside of the box are initialized to 0. The pentominos can be defined by the cells they cover when placed in ARENA. The "list" that Fletcher refers to is a long argument to a macro instruction, TEST. Although it is not immedietly obvious, this list contains the 63 possible orientations or patterns of the 12 pentominoes in a tree-like structure. The dollar sign is used to mark the end of a string of characters and the "ETC" must be used to append the following string of character to the previous one. The symbols, "((" and "))" increment and decrement the level of nesting in the structure. The tree-like structure of this list is more apparent when written as follows:

testtree

The following figure illustrates the meaning of the numbers in Fletcher's List.

tree

fletcherspatterns

His program would find the first/next empty square in ARENA and identify this square as L, then test square, L+1. If square L+1 was occupied, then the left half of the tree could be eliminated and L+16 was tested. The level of nesting started with zero and was incremented with each level of nesting in the tree. When the level of nesting was 4 a pentomino pattern could be placed in the box.

List of Patterns:

Pentominoes are a natural evolution from polyominoes of order 1 to 5,and an alternative tree would have also worked in Fletcher's Program.

tree2

I have developed a number of programs and three batch files, makegroups1.bat, makegroups2.bat, and makegroups3.bat, which allow the user to easily create various trees and then see the results in programs that use the trees. Recently I automated the production of trees in runpatterns.bat. This batch file first runs makegroups3.bat to produce a pentomino tree that is used to display the patterns and the structure of the tree in a Borland C++ Builder 6 Program, patterns.exe. The file, groupsaved2.txt, is a tree that I found with this program that yields a solution in just 49 steps. Since it takes almost 1.5 million steps to find the 2339 solutions to the puzzle when holes are avoided in fletcher3hole.exe, this result is phenominal. Here is a detailed instrution for runpatterns.bat. Other programs which I have developed for modifying trees without the usual number of 19 main branches are: branches.c and branchesfull.c. When running one of the batch files a text file, groups.txt, pops up so that you can edit the file and save the modified file.

ngdebruijnsmethod

N. G. de Bruijn's Paper:

http://repository.tue.nl/597548

https://pure.tue.nl/ws/files/2352046/597548.pdf

http://alexandria.tue.nl/repository/freearticles/597548.pdf

http://purl.tue.nl/372812914182296

bruijn'sfirstprogram

bruijn'sfirstprogram(english)

In his paper on pentominoes, Professor Bruijn describes the 63 pentomino patterns as an alphabet and a solution to the puzzle as a word in a large dictionary with a large number of words of 12 letters or less:

63 + 632 + 633 + ... + 6312 = 3,909,188,328,478,827,879,681

A brute force solution to the 6x10 pentomino puzzle would require, even on a fast computer (based on 1960's technology), 100 million years. Even given the increase in computer speed during the past 50 years a brute force solution is still not possible. About 50 years ago Bruijn's program took about 6 minutes to compute 24 solutions on an EL-X8 Computer. Fletcher's Fortran Assembly Program took about 10 minutes on an IBM7094 Computer to find the 2339 solutions to the 6x10 puzzle. In his paper on Dancing Links, Professor Knuth states in a footnote that N. G. de Bruijn's Method and Fletchers Method for solving the 6x10 pentomino are almost identical. While these two methods seem very different at first glance, the efficiency of the two methods are very close based on the execution times on my Laptop Comuter displayed in the figure below.

compare

In his paper on Dancing Links, Professor Knuth presents his method for solving exact cover problems; From this point of view the pentomino problem as described in Fletcher's Paper is an example of an exact cover problem and can be solved using Algorithm X, which is Knuth's implementation of his use of "Dancing Links", to solve exact cover problems. The 6x10 Pentomino Puzzle is special because the number of pentominos is manageable and the tiling of a 6x10 box is challenging. Click on the figure below for an introduction to polyominos.

 

polyominos

 

myotherprograms

Solution Display Programs: pentom and show

Pentomino Player Program:Pentomino_Player_BB6

 

Links:

Nicolaas Govert de Bruijn (Wikipedia): https://en.wikipedia.org/wiki/Nicolaas_Govert_de_Bruijn http://www.win.tue.nl/~wsdwnb/

John G. Fletcher: https://www.llnl.gov/community/retiree-and-employee-resources/in-memoriam/john-fletcher

John G. Fletcher RIP http://shearerinsanity.blogspot.com/2012/01/john-g-fletcher-rip.html

John G. Fletcher's Publications: http://dblp2.uni-trier.de/pers/hd/f/Fletcher:John_G=

Donald Knuth (Wikipedia): https://en.wikipedia.org/wiki/Donald_Knuth

Donald E. Knuth: https://arxiv.org/pdf/cs/0011047.pdf Donald E. Knuth's Dancing Links

Matthew T Busche http://www.mattbusche.org/blog/

David J. Eck: http://math.hws.edu/web/faculty/eck.html David J. Eck's Free Online Java Book David J. Eck's Java Pentomino Solver

Peter Van Alem: https://sites.google.com/site/petervanalem/ https://www.mathworks.com/matlabcentral/fileexchange/33197-pentomino-solver

Adrian S Snaffle: http://www.abasmith.co.uk/pentanomes/pentanomes.html

Karl Dahlke: http://www.eklhad.net/ http://www.eklhad.net/polyomino/hexsol.c

Pentomino Solver in Python: http://pynokio.org/pentomino.py.htm

Pentomino Solver in TCL/TK: http://www.geocities.jp/zhuoware/notes/pentomino_solver.html

Gerard's Universal Polyomino Solver: https://gp.home.xs4all.nl/PolyominoSolver/Polyomino.html

Marc Lepage - polycube solver: https://libraries.io/github/mlepage/polycube-solver

https://www.codeproject.com/articles/271634/puzzle-solver

https://blog.codinghorror.com/there-aint-no-such-thing-as-the-fastest-code/

https://en.wikipedia.org/wiki/Pentomino

https://en.wikipedia.org/wiki/Polyomino