Takipci Var Qr ⚡ Simple

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 be arranged to form a rectangle of size 3×20, 4×15, 5×12, or 6×10.

PolySolver is a Java application 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 application 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 many 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. You can save a puzzle to a local file, or it 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.

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:

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

File menu

The File menu has the following options:

Note that the password protection on the server 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.

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.

Some of the grid types you can choose from are:

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. Choosing 'Rotations' means that only rotations of the defined orientation(s) will be used.

You can select the display colour that you want the piece to have. If you press the button with the coloured square, a colour selection dialog appears where you can choose your preferred colour. You can remove the colour by pressing the Clear Colour button. Any uncoloured pieces will be given colours automatically when used later.

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.

The rotate and mirror buttons will rotate or reflect the currently displayed shape orientation. Copy will remember the currently displayed shape orientation, and with the paste button this copy is added as a new orientation on the current shape.
To clear the current orientation 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. Right-clicking while carrying a piece will rotate it, and right-clicking while not carrying a piece will pick up another copy of the currently selected piece if available.

Solve

On this screen you can let the computer attempt to solve the problem. You can select what kind of solution you are looking for:
Fill all: The whole board is to be filled without gaps
Fill most: Fill as many cells of the board as possible.
Use all: Fit all the pieces on the board.
Use most: Fit as many pieces on the board as possible.
Then click the 'Solve' button to start the solver.

During the solve, the display is frequently updated to show the current position it is examining. There is also a timer that shows how long the solver has been running, the average search time per solution so far, and a node counter which indicates how many times the solver has attempted to place a piece.

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, are available in this example.zip file, or can be downloaded individually below.

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

• Allow pause/restart of solver.
• Automatically reject double counted solutions on symmetric boards.
• Add more grids, especially 3d ones such as tetrahedra+octahedra.

History:

• 2005/03/13: Version 1.0: First public release.
• 2012/05/06: Version 2.0: Major refactoring. Added File menu with upload/download options.
• 2012/06/27: Version 2.1: Bugfix: description not loaded, crash when multiple pieces and more than fit on the board.
• 2012/09/11: Version 2.2: Added server file renaming.
• 2012/11/02: Version 2.3: Added settings menu with colour settings, and timer on solver tab.
• 2012/11/03: Version 2.4: Title bar and close confirmation dialogs on stand-alone version.
• 2012/12/16: Version 2.5: Rewrote file menu and server scripts to add directory structures on server.
• 2013/01/05: Version 2.55: Replaced filechooser dialog that hangs when run within web applet.
• 2013/01/09: Version 2.6: Added Notes tab, and shapes now have a minimum amount.
• 2013/01/20: Version 2.61: Fixed bug in loading notes from file.
• 2013/01/28: Version 2.62: Fixed bug in loading piece placements from file.
• 2013/01/28: Version 2.63: Fixed tracking of changed in the Place tab.
• 2013/12/29: Version 2.64: Fixed number spinners that were broken by java security update.
• 2014/01/27: Version 2.65: Fixed bug introduced in 2.64.
• 2015/12/23: Version 2.7: Added Dodecagon and Heptagon grids. Fixed bug where spinner gets stuck, and bug where solutions double counted when area of pieces smaller than board.
• 2016/09/03: Version 2.8: Added Nonagon grid. Fixed piece selection bug in Place tab.
• 2017/01/14: Version 2.9: Added piece colouring, and solver node counter.
• 2017/01/25: Version 2.91: Changed server to use https.
• 2017/01/27: Version 2.92: Added Unequal Squares grid.
• 2017/02/05: Version 2.93: Added template options to file menu (standalone only).
• 2017/06/19: Version 2.94: Added Nonagon 2 grid. Minor bug fixed.
• 2018/03/30: Version 2.95: Added Brick grid.
• 2018/08/25: Version 3.01: Added Kite and Isosceles grids. Added Rotate/Reflect buttons to Shapes and Board editing screens.
• 2018/10/19: Version 3.05: Added more grids - 3.4.6.4 and some variations.
• 2018/12/07: Version 3.1: Added copy/paste buttons to shape editor. Added options to only store last N solutions, and to skip reduction pass.
• 2019/03/20: Version 3.2: Added solve modes to the Solve tab. Fixed bug in Split Snub Square grid.
• 2019/04/14: Version 3.21: Bug fix: Changing description/notes/solvemode would invalidate puzzle, clearing any placed pieces.
• 2019/06/19: Version 3.22: Added more grids - TriHex (3.6.3.6) and OctaPenta.
• 2019/06/24: Version 3.23: Bug fix: Made loading/saving more robust.
• 2019/09/28: Version 3.30: New grids, grids reorganised as a tree, checks for updates.
• 2023/12/24: Version 3.31: New grids, fixed bug in rhombitrihex grid.
• 2025/12/28: Version 3.32: Improved usability of Place tab, bug fixes, code maintenance.

Send any comments or suggestions to .