|
This page uses a Java applet. Java applets are no longer well supported and will soon be completely unsupported. Please use the JavaScript version of Pentominos Puzzle Solver: http://math.hws.edu/eck/js/pentominos/pentominos.html |
 |
Pentominos Puzzle SolverTHE APPLET ON THIS PAGE can solve pentominos puzzles. The applet appears as a button bellow. When you click this button, the program itself is opened in a separate window. This applet requires Java 1.4 or higher. You can find an older and much simpler version that works with any version of Java at http://math.hws.edu/xJava/Pentominos_old/. The image at the left shows a puzzle that was solved by the program. Each color represents one of the 12 possible pentominos, while the black squares were selected to be left empty. Instructions for using the program are given below. For more detailed information about pentominos, you might want to check out the Wikipedia article on the subject.
David Eck, March 2006 |
Click Here:
(Might require two clicks on Windows.)
If you don't see a button here, try the old applet at
http://math.hws.edu/xJava/Pentominos_old/
The source code for the program is available.
An executable .jar file can be downloaded to
run the program as a stand-alone application.
Instructions and Information
This program applies a simple "recursive backtracking algorithm" to the problem. This means that it simply tries the pentominos in all possible orders, trying to fill the available spaces from left to right and from top to bottom. It keeps placing pieces as long as it finds one that fits in the next available spot. When it can't find a piece that fits in the next spot, it backs up and tries a different piece on the previous level.
When the Pentominos window first appears, it creates an 8-by-8 puzzle in which four squares have been selected at random to be left empty. It starts solving this puzzle, moving rather slowly. It will stop when it finds a solution. However, you can control what is happening by selecting any of the menu commands at any time. You can control the speed. You can change the size of the board. You can Pause the solution process and step through it one move at a time. You can restart with an empty board and select the squares that will be left empty. What follows on the rest of this page is just more detailed instructions...
The Speed Menu: The program can run at seven different speeds. The slower speeds are meant mostly to help you understand how the solution process works. In speeds 2 through 6, each move is shown on the board; even though the moves go by pretty fast at speeds 2 and 3, drawing the pieces takes a lot of time -- much more than finding the moves -- and so it usually takes a lot of time to find a solution at these speeds. At speed 1, the board is drawn only once every 1000 moves, which moves things along much more quickly but still gives you an idea of the progress that is being made. In each of the speeds 1 through 6, the program will pause when it finds a solution. Speed 0 is a little different from the other speeds. At this speed, the board is only redrawn when a solution is found. Furthermore, the program does not pause when it finds a solution -- it just keeps looking until it has found all possible solutions. For example, you can use Speed 0 when you want to count the number of solutions.
By the way, a move in the game means successfully placing one piece on the board. Testing a piece to see if it fits does not count as a move. Removing a piece during backtracking does not count as a move.
The Size Menu: Use this menu to change the size of the board. The "Custom Size" commands allows you to choose any number of rows or columns in the range 3 to 21. You can make a small board that holds fewer than 12 pentominos; the program will try to place as many pentominos as will fit. You can make a large board that has lots of extra spaces. You can color these squares black to create an interesting or oddly-shaped white area for the program to try to fill. For example:
Restarting: In most cases, there are three "Restart" commands in the control menu. The basic "Restart" command will stop the current solution and remove all pieces from the board. At that point, you can select different black squares, and you can click "Go" to start solving again. The "Restart with Empty Board" is similar, but the black squares are also removed from the board. The "Restart with Random Board" will remove all pieces from the board, select a set of black squares at random, and begin solving the new puzzle immediately, as if you had also selected "Go". On a board that can be exactly filled with pentominos with no empty squares left over, there is only one "Restart" command, and it simply clears the board and waits for you to select "Go".
Selecting Squares: When selecting square to be left empty, simply click on a white square to make it black. You can also click on a black square to turn it back to white. You can use the "Go" command at any time, even if you have not selected the maximum allowed number of black squares. A solution then means filling the white area with the largest possible number of pentominos, leaving some of the white squares empty
The Randomize Order of Pieces Command: The program has a certain order in which it tries the pieces. (In this ordering, the program tries the more symmetric pieces first, on the grounds that the less symmetric pieces are easier to place because they come in more different reflected and rotated versions.) This means that on a given board, you will always see exactly the same sequence of moves. If you turn on the "Randomize Order of Pieces" option, then before starting the solution, the pieces are placed in a random order, which will yield a different sequence of moves. Note that the program would still find exactly the same solutions, just in a different order. This command is not available when a solution is in progress and there are pieces on the board; it is available after a "Restart."
The Check for Obvious Blocking Command: Without this option, you will sometimes see that the program seems to be doing something stupid: You'll see an isolated group of one to four white squares that is not large enough to hold any pentomino, but the program will be chugging away trying to places pieces in other parts of the board. This is particularly obvious if you make a board with 3 rows and 20 columns, where the problem is so bad that I have never had the patience to wait for a solution to be found. (This is why there is a 20-by-3 board in the "Size" menu rather than a 3-by-20; the 20-by-3 board is solved very quickly.) If you turn on the "Check for Obvious Blocking" option, the program will check for blocking of this type every time it makes a move. (In fact, it checks for any white area whose size is not a multiple of five -- or an even more complicated check when you haven't selected the maximum number of black squares.) This option can greatly decrease the number of moves needed to find solutions. However, the test itself is fairly complicated and so the net computer time spent searching for solutions is in many cases not very different. One case where the difference is quite large is on the 3-by-20 board. With the "Check for Obvious Blocking" option turned on, the program found the following solution in 319093 moves:
The Symmetry Check Command: For some boards [before any pieces are added], when you rotate or reflect the board, it looks the same after the operation as it did before. This is called a "symmetry" of the board. There are seven possible symmetry operations: horizontal reflection, vertical reflection, rotation through 180 degrees, reflection through the descending diagonal, reflection though the ascending diagonal, rotation through 90 degrees, and rotation through 270 degrees. (The last four of these only apply to a square board.) If you have one solution of a symmetric board, then a symmetry operation will transform that solution into another solution. You might want to avoid counting this transformed solution as a separate solution. If you turn on the Symmetry Check option, that's what will happen: only one member of each set of symmetric solutions will be generated. To implement this, several piece orientatins are removed from the set of possible orientations. For example, consider a board that is symmetric under the two diagonal reflections and under rotation through 180 degrees, and not under the other symmetries. Consider the "T" shaped pentomino. This piece has four possible orientations. Any solution contains the "T" pentomino in one of these orientations and, if it does not contain the "T" in its upright orientation, can be transformed by one of the three symmetry operations into a solution that does. The Symmetry Check option removes three of the orientations of the "T" pentomino from consideration, leaving only the upright position. The only solutions that are generated are the ones that contain the "T" in this orientation. This includes exactly one solution from each set of four symmetric solutions. This option is probably useful mainly for counting solutions. The Symmetry Check command does not appear in the menu for a board that is too small to hold all 12 pentominos, since the method that is used for symmetry checking assumes that all the pieces are on the board. This command is not available when a solution is in progress and there are pieces on the board; it is available after a "Restart.
The One Sided Command: This command was inspired by a pentominos puzzle in which the pieces are colored white on one side and red on the other. In this puzzle, you want to find a solution in which all the face-up sides have the same color. You can use the One Sided command to solve puzzles of this sort. It doesn't change the colors of the pieces, but it prevents the pieces from being turned over. You get to pick which side you want to be face up -- there is a choice in the case of only six of the twelve pentominos, since the other six are symmetric under a flip operation. When you use the One Sided command, a dialog box appears. At the top of the window is a check box that specifies whether the One Sided option is on or off. Once you turn the option on, you can select which side of each of the six two-sided pentominos you want to use. The default choices (with the left-hand option selected in each case) was chosen so that the 20-by-3 board would have a solution. Note that if you turn on the Symmetry Check option as well as the One Sided option, reflectional symmetries are disallowed since they would flip the pieces over. This command is not available when a solution is in progress and there are pieces on the board; it is available after a "Restart.
The Save Image Command: This command does not appear in the applet version of the program, since applets are not allowed to save files for reasons of security. If you download the executable jar file (or download the source code and compile it yourself), the stand-alone application will have a "Save Image" command in the "Control" menu. This command will save an image of the current board in PNG format. The "Save Image" command was used to create the images on this page. The "Save Image" command is only enabled when the program is paused (by the "Pause" command or after finding a solution), or after a "Restart" command before you select "Go".