Jaap's Puzzle Page

PolyForm Puzzle Solver

Written by Jaap Scherphuis © 2004-2016.

The program may be freely used or adapted for use on any other website provided that its copyright message remains intact and a link is given to this page, or to Jaap's Puzzle Page. The program may not be sold.

If the applet doesn't work, it may be that you need to install a more recent version of Java. You can go to www.java.com to get it.
You will also need to change the Java settings. In the Configure Java app, choose the security tab, and add http://www.jaapsch.net to the Exception Site List of sites that are allowed to run Java applets.
If you are unable to do this, you can also simply download the jar file below, and run that on your computer directly, instead of from within your web browser.

Downloads:
   Executable jar file
   source files

Send any comments or suggestions to .

Launch the Polyform Solver Applet

Polyforms are shapes built up from identical parts glued together. The best known polyforms are the twelve pentominoes, which are all the shapes that can be made by gluing 5 squares edge to edge. They contain 5×12=60 squares all together, and can in fact form rectangles of 3×20, 4×15, 5×12, or 6×10.

PolySolver is a Java Applet with which you can make and solve many polyform problems, such as puzzles involving pentominoes, hexiamonds, or many other such tile sets, with which you have to build a particular shape. I have tried to make this applet both versatile and easy to use. The most important features are:

  1. The grid can vary, square grid for polyominoes, or various other grids for polyiamonds, polyhexes, polytans, polydrafters, and more.
  2. The board and the pieces are completely user defined.
  3. The rotations and/or reflections of pieces can be generated automatically, or user defined.
  4. Multiple pieces of the same shape are allowed.
  5. Complete sets of pieces can easily be generated.
  6. Pieces can be placed on the board manually.
  7. A puzzle can be uploaded to the server for everyone to share.
  8. There is a fairly powerful built-in solver.
  9. Solutions found by the solver can be displayed.
  10. The program can be run as an applet in a webpage, or the jar file can be run as a local application. In that case you can save/load puzzles to file as well.

How to use PolySolver

The program has a number of screens, which you can select using the tabs along the top, as well as a file menu. The screens are:

Grid Type:    Choose the shape of the grid to work on.
Shapes:Manually define or edit the shapes of the pieces.
Generate:Generate complete sets of pieces.
Board:Define or edit the shape of the board.
Place:Place some pieces on the board, or try to solve the problem yourself.
Solve:Let the computer attempt to solve the problem.
Notes:Keep notes related to the problem.

The file menu and these screens will now be explained in a little more detail.

File menu

The File menu has the following options:
New:Creates a new empty puzzle.
Download:Downloads any of the available puzzles from the server.
Upload:Uploads your puzzle to a file on the server, sharing it with all other users of this program. A password can be provided so that no one else can edit it.
Remove:Remove a previously uploaded puzzle. If the puzzle file is password protected, the password must be entered before deletion takes place.
Rename:Change the name of an uploaded puzzle file. If the file is password protected, the password must be entered before renaming takes place.
Change Password:Change the password of an uploaded password-protected puzzle file, or set a password on an unprotected file.

Note that the password protection is rather trivial, so do not use a password that you use anywhere else. Note also that the server file name must consist only of letters, numbers and underscores.

If you run this program as an applet within your web browser, then it has limited permissions to change things on your computer. The File menu will then have only the options above. If you run the program from the executable jar file outside your browser as a stand-alone application, then the File menu will have the following additional options:

Open:Opens a previously saved file.
Save:Saves any changes you have made in the current puzzle.
Save As:Saves the current puzzle to a file, with a file name of your choice.
Exit:Exits the program.

Grid Type

Here you can choose the shape of the grid to work on. Simply click on one of the types listed on the left. In the centre you will see a preview of this grid.
Note that you cannot change the grid type if there are already shapes or a board defined. If this is the case, you can use the 'clear shapes' and 'clear board' buttons to remove those definitions.

Currently the grid types you can choose from are:

Square, Hexagon, Triangle:These are the three regular grids most commonly used in these problems (44, 63, 36).
Rectangle:A square grid that is stretched along one axis to make rectangles.
Diamond:A 'squashed' square grid, made of diamond shapes.
Tan:A grid of squares that are divided into four 45-45-90 triangles.
Octagon:A grid made of octagons and squares (4.8.8). Checkerboard problems on a square grid can be solved on this grid instead.
Pentagon:A tiling made with non-regular pentagons, also known as the Cairo tiling.
Pentagonhalf:The above pentagon tiling with all pentagons split in two.
Dodecagon:A tiling made of dodecagons and triangles (3.12.12).
Heptagon:A tiling made of regular heptagons and irregular pentagons.
Nonagon:A tiling made of regular nonagons and 6-pointed stars.
Cubetiling:A grid made of diamonds that are put together in hexagons, and which looks like a projected array of cubes.
Drafter:A grid of hexagons divided into twelve 30-60-90 triangles.
Snub-Square:A tiling of regular triangles and (subdivided) squares, with two non-adjacent squares at each vertex (3.4.3.3.4).
Cube:A 3-d arrangement of cubes, displayed with layers side by side.

If there is any other kind of grid that cannot be easily simulated by one of these, please let me know so that I can add it.

Shapes

On this screen you can define the shapes of the pieces. An empty section of the grid is shown in the editor. When you move your mouse over it, the cell under the mouse pointer is outlined in red. If you click, that cell is added to (or removed from) the current shape. Note that the section of the grid is resized and centred after each change you make. You can click and drag to select a large section of cells, which will be changed when you release the mouse button.

By changing the 'piece' option you select which shape is currently shown in the editor. The last of these is always an empty grid, so you can add a new piece there.

If you want multiple pieces of the same shape, you should change the 'Amount Max' option to the correct amount. If you were instead to define the identical shapes separately the solver would later treat those tiles as distinct, and therefore solutions that differ only by swapping identically shaped pieces would be treated as distinct as well. If you want to force a certain number of a piece of a shape to be included in every solution, then you can change the "Amount Min" option.

By default, all rotations and reflections of the piece will be allowed. You can select one of the options None/Rotations/Reflections to change this behaviour. Choosing 'None' means that the piece will not be rotated at all, and will be used only in the exact orientation(s) you defined.

If you wish, you may define the various orientations of a piece yourself. To do this, simply change the 'Orientation' option, and add a new shape for this piece. This can be useful if you want to restrict its rotations in a particular way, or if you want a piece to look different when turned over. See the examples later on.

To clear the current shape in the editor, you can use the 'Delete' button.

Generate

On this screen you can generate sets of pieces. You can create a tile shape, and let the program join together copies of that tile in all possible ways, so generating a complete set of shapes. The list of shapes generated in this way can then be added to the shapes you want to use in your polyform puzzle.

On the left of the screen is an editor similar to the regular Shapes screen. There you can click cells to build a shape. In most cases this will be the monoform you want to use, i.e. the basic shape from which the set of pieces will be built. As before, click any cells you wish to add or remove from the shape. The "Expand" button adds all neighbouring cells to your shape, and the "Clear" button will clear the editor.

To directly add this shape to the list, press the 'Add Tile' button. If you press the 'Join Tile' button, the tile will be joined to the shapes on the list in every possible way to create a new set of pieces. For example, suppose you are using a square grid, and in the editor on the left you have clicked only a single square for the tile shape, i.e. the tile is the monomino. By repeatedly pressing the 'Join Tile' button the initially empty list first contains only a monomino, then only the domino, then the two trominoes, then the tetrominos, the pentominoes, etc.

Note that the shapes generated in this way are not automatically part of the polyform puzzle you are defining. Pressing the 'Add List' adds the generated pieces to the current set of pieces of your puzzle. You can review and further edit those pieces on the 'Shapes' screen.

The 'Delete Shape' button is used to delete only the current shape from the generated list. The 'Clear List' button on the other hand empties the whole list. The 'Add list' button adds all the pieces in the generated list to the shapes used in your puzzle. No check is made for duplicates at this stage, so you may wish to review the shapes by going to the 'shapes' screen.

Board

On this screen you can define the shape of the board. It is very similar to the shape editor, and therefore needs no further explanation.

Place

On this screen you can place some pieces on the board yourself. In this way you can try to solve it yourself, or partially solve it so that later the solver will try to complete the solution.

The main part of the screen shows the (still empty) board. On the bottom of the screen is a view of one of the pieces. With the controls at the bottom right you can change which piece is shown, and choose its orientation. Clicking on the piece will pick it up or drop it again. When a piece has been picked up, its outline is shown which moves with the mouse pointer. Move over the board, and click when you want to drop the piece. You can pick up a piece that is already on the board (if you aren't carrying another piece already) by clicking it. Note that the controls for selecting the current piece and its orientation work still when you are carrying a piece.

Solve

On this screen you can let the computer attempt to solve the problem. Click the 'solve' button to start the solver. The display is frequently updated to show the current position it is examining. Once solutions are found, you can choose between showing a solution or showing the current search with the 'progress/solution' options. When you choose 'solution', the slider bar allows you to select which of the solutions is displayed.

A solution is an arrangement of pieces that completely fills the board (possibly with some pieces left over), or an arrangement in which all the pieces are placed on the board (possibly with some space left over). In other words, a solution uses up all the pieces, or uses up all the board (or both).

Note that no checks are performed on the piece sizes. For example it is obviously impossible to cover an odd area with dominoes (whose area is even), but if there are more dominoes than fit on the board, the solver will try to fill the board anyway.

The solving algorithm the program uses is a version of DLX, the 'Dancing Links' algorithm by Donald Knuth (P159 on his preprints page.) It is a depth first tree search which cleverly treats pieces and cells of the board in the same way, so that it either fills the board cell where the fewest pieces fit or places the piece that has fewest remaining possibilities. By doing so, the branching factor is kept as low as possible. I have made three minor adaptations to the algorithm. Firstly, if the pieces don't always cover the whole board, extra monotiles are added, so that there is never any need to deal with empty parts of the board. Secondly, you can have multiple copies of polyforms, so the matrix columns in the DLX algorithm that represent those pieces have to be covered several times rather than exactly once. Thirdly, if the pieces (plus any added monotiles) don't cover the board exactly there will be pieces left over, so then the DLX matrix columns representing the polyforms need not be fully covered.

Notes

On this screen you can type in any text that you want to keep with the puzzle.

Examples

All the examples listed here can be downloaded from the server via the File menu.

Example 1: pentomino_3x20

The canonical example is always the set of pentominoes on a rectangular board. Lets first try the 3×20 rectangle. Every solution can be flipped over or rotated 180 degrees to get another arrangement which solves the problem. We would consider these solutions to be identical, but if they were counted separately you would get four times the actual number of solutions. We don't want all these to be counted separately, which is what would happen if we allow every piece to be rotated and flipped.

A solution to this is to restrict the L pentomino for example. It fits on the board in exactly four orientations, which would all occur in those quadruply counted solutions. The L pentomino has been drawn horizontally, aligned with the long axis of the rectangle, and the 'none' option has been chosen so that no rotations or reflections are allowed of that piece.

This problem has 2 solutions.

Example 2: pentomino_4x15

On the 4×15 rectangle we again have the problem of quadruply counting solutions. Restricting the L pentomino like before is not correct, because the L actually fits on the board in 8 orientations, and we want to allow only two of those 8. Therefore we can define the two allowed orientations of the L by hand. I have drawn one vertical and one horizontal L, and set its symmetry option to 'None'.

This problem has 368 solutions.

Example 3: pentomino_8x8

The board is an 8×8 square with a 2×2 hole in the centre. This board has 8-fold symmetry, so now we can simply restrict the L pentomino (or any other non-symmetric pentomino) to one orientation.

This problem has 65 solutions.

Example 4: pentochess_8x8

This problem uses the pentomino set to tile a chessboard. The pieces are however made from alternating black and white squares, and the resulting pattern should be also. This program does not allow such colourings. Using the octagon/square grid pattern we can solve this problem anyway, because we can identify the black squares with the octagons, and the white squares with the squares of the grid.

In this puzzle the pieces all have a different colouring on one side than on the other. Therefore I have set the 'Rotations' option on every piece (instead of the Reflections option), and defined two orientations, one for the front and one for the reverse.

As defined, the solver gives 4 solutions. These are similar to each other (rotated 180 degrees, or flipped over). To avoid that, you could restrict one piece as before (e.g. the L pentomino, defining only a vertical and a horizontal version, and setting the 'None' option).

Example 5: Y_pento_in_15x15

It is possible to use 45 Y pentominoes to fill a 15×15 square. To do this in the solver, simply define one Y pentomino shape, and set the 'Number' option to 45. It is unfortunately not possible to eliminate multiply counted solutions the way we did before. The program will find 1696, but there are really only 212 solutions to this problem, and each is counted 8 times.

If you insist one finding each solution once, you can split the problem up into subcases. We can define the orientation of any solution by the orientation of the Y pentomino that covers the centre cell of the board. By restricting ourselves to those solutions in which that centre pentomino has a particular orientation, say horizontal with its arm at the top right, we can be sure of counting each solution exactly once. By placing that centre piece beforehand, we can be sure that no solutions will be double counted. Not only that, it is faster as well as the search space is reduced. This leads to 5 subcases, depending on which part of the Y pentomino covers the centre cell.

These subcases are:
  Y_pento_in_15x15_A 120 solutions
  Y_pento_in_15x15_B 0 solutions
  Y_pento_in_15x15_C 0 solutions
  Y_pento_in_15x15_D 0 solutions
  Y_pento_in_15x15_E 92 solutions

Example 6: N_pento_in_5x5x5

Polycube problems can be defined in the program by using the cube grid. The layers of the pieces and the board will be shown side by side. A square in a layer will be marked by an X and/or O if it is connected to the same square in the layer shown to the left and/or right. For example, twenty five N pentacubes can fill a 5×5×5 cube. Because of the symmetries of the cube, every solution would be counted 48 times, unless we use a similar trick as in example 5. By placing a piece in the centre cell we fix the orientation of the solution. Unfortunately we will still get mirror image solutions (those with the layers in reverse order) because the pieces are mirror symmetric in three dimensional space.

There are three subcases:
  N_pento_in_5x5x5_A 2 solutions
  N_pento_in_5x5x5_B 6 solutions
  N_pento_in_5x5x5_C 0 solutions

This gives a total of 8 solutions, but really only 4 when we discard the mirror images.

Example 7: F_pento_in_5x7x7

This problem involves packing 49 F pentacubes into a 5×7×7 box. It is now known that there are no solutions.

Possible future enhancements

History:

Send any comments or suggestions to .