# Polyomino solver

Over eight years ago I created the Polyomino Tiler a browser application that attempts to tile arbitrary grids with sets of polyominoesbut I haven't ever written about the algorithm it uses.

If any aspects of what follows are confusing, it may help to play with the polyomino tiler a bit to get a better idea for what it's doing. So the algorithm needs to be generic enough to not get bogged down in all the edge cases resulting from these two facts. The main preprocessing step is to calculate all possible placements of all available pieces. When hundreds of piece variants are available this step can be lengthy, and the result can require a lot of memory. But the result is essentially a bipartite graph or, in database terms, a many-to-many relationship between placements and grid points.

Notice that all of the geometric details have been abstracted away; this means that the rest of the algorithm could just as easily be applied to grids of triangles, or hexagons, or hyperbolic grids, or higher dimensions.

Given the bipartite graph, the problem of tiling the grid can be reformulated as the problem of finding a subset of the placements that, as a whole, is connected to every one of the grid points exactly one time.

The search algorithm is a backtracking algorithm that at each step chooses an untiled grid point and a random placement associated with that grid point; it adds that placement to the solution set and then tries to tile the remainder of the grid taking note of which placements are invalidated by the one selected. If it fails to tile the rest of the grid, then it tries the next placement.

If it runs out of placements, then the grid must be untileable. For example, if we decide to start tiling the above grid from grid point A, the search tree might look like this:. The reason the tree is so sparse is that each time we descend we remove placements from the graph that conflict with the one chosen.

Since every placement we select makes several other placements impossible, it's easy to get to a point where there is some grid point that no longer has any possible placements. This is the most common sign of untileability, and it means we need to backtrack and try something different. For example, if we descended down the ACD branch of the search tree, the graph would look like this, and the existence of grid points with no placements indicates that there's no solution.

A given set of polyominoes places restrictions on what grids can be tiled purely based on their size. This is solely a function of the set of distinct sizes of the polyominoes. For example, with the tetrominoes, only grids whose size is a multiple of four can be tiled. If the polyominoes have sizes 4 and 6, then only grids whose size is an even number greater than two can be tiled.

This kind of analysis is closely related to the coin problem. Further, if a grid consists of disconnected subcomponents, then we can analyze the tileability of each one separately, and conclude that the whole grid can't be tileable if any of the subcomponents is not tileable.

For example, this grid has been disconnected, and even though the size of both pieces together is a multiple of three and so could theoretically be tiled by trominoes, the individual subcomponents do not have a multiple of three grid points, and so neither of them are tileable.

If the grid at any point becomes disconnected, we immediately restrict the algorithm to the smallest subcomponent and try to tile that completely before moving on to the next one. The logic here is that if the disconnected grid as a whole can't be tiled, there's a decent chance that the smallest subcomponent can't be tiled. The smallest subcomponent is also likely the one that we can finish searching the fastest, and so this hopefully leads to a more aggressive pruning of the search space.

For example, this grid has a small component and a large component, and the small component can't be tiled with trominoes can you figure out why?

Within a subcomponent, we select the next grid point to tile based on the number of remaining placements it has. It is not uncommon for there to be a grid tile with only a single option, and in those cases it's important to place that piece immediately, since it likely decreases the size of the search space by eliminating other placements and potentially causing more grid points to have only one option.

When there's not a grid point with a single placement, we still prioritize grid points with the fewest number of placements, since these are intuitively the most "difficult" parts of the grid to tile, which makes them more likely to be rendered untileable by other placements. For example, in this grid the untiled grid point in the bottom left corner has only one possible placement with trominoes; tiling it lets us eliminate seven other placements that conflict with the forced placement.

The last heuristic is a little crude but still useful. The motivation is that being able to split the grid into subcomponents is useful since they can be analyzed independentlyand so if we have the opportunity to split it by placing a piece, we should do so. So the precise rule is that, when there aren't any single-placement grid points which are higher priorityand there is a single grid point that splits the grid in graph theory terms, a vertex whose removal disconnects the graphthen we search placements for that grid point next.

For example, there are a couple grid points that disconnect the bottom right portion of this grid from the rest of it; either of these could be chosen for the next search step. This approach could probably be generalized to something that tends to select grid points that make the grid easier to split, rather than only acting on this principle when it can be achieved in a single step.

However, this would likely be somewhat in tension with the prioritization of the most restricted grid points, so I'm not sure how it would work out. Since the polyomino tiling problem is NP-complete, it's not surprising that there's a variety of scenarios where the algorithm gets stuck. Some of these are artifacts of the particular algorithm, and it could conceivably be tweaked to handle those special cases.For this to work you will need a recent version of Java installed in your computer, and the.

To download and install Java i. Most web browsers no longer allow Java appets to run on a webpage due to security concerns. 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. Send any comments or suggestions to puzzles a t jaapsch d o t net.

PolyForm Puzzle Solver 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. 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 applet both versatile and easy to use. The most important features are:. 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:. 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:. 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. 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.

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.A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling. Polyominoes have been used in popular puzzles since at leastand the enumeration of pentominoes is dated to antiquity. Related to polyominoes are polyiamondsformed from equilateral triangles ; polyhexesformed from regular hexagons ; and other plane polyforms. Polyominoes have been generalized to higher dimensions by joining cubes to form polycubesor hypercubes to form polyhypercubes. In statistical physicsthe study of polyominoes and their higher-dimensional analogs which are often referred to as lattice animals in this literature is applied to problems in physics and chemistry.

Polyominoes have been used as models of branched polymers and of percolation clusters. Like many puzzles in recreational mathematics, polyominoes raise many combinatorial problems. The most basic is enumerating polyominoes of a given size. No formula has been found except for special classes of polyominoes. A number of estimates are known, and there are algorithms for calculating them. Polyominoes with holes are inconvenient for some purposes, such as tiling problems.

In some contexts polyominoes with holes are excluded, allowing only simply connected polyominoes. There are three common ways of distinguishing polyominoes for enumeration:  .

The dihedral group D 4 is the group of symmetries symmetry group of a square. This group contains four rotations and four reflections. It is generated by alternating reflections about the x -axis and about a diagonal.

One free polyomino corresponds to at most 8 fixed polyominoes, which are its images under the symmetries of D 4. However, those images are not necessarily distinct: the more symmetry a free polyomino has, the fewer distinct fixed counterparts it has. Therefore, a free polyomino that is invariant under some or all non-trivial symmetries of D 4 may correspond to only 4, 2 or 1 fixed polyominoes. Mathematically, free polyominoes are equivalence classes of fixed polyominoes under the group D 4. Polyominoes have the following possible symmetries;  the least number of squares needed in a polyomino with that symmetry is given in each case:.

The following table shows the numbers of polyominoes with n squares, sorted by symmetry groups. This leads to algorithms for generating polyominoes inductively.

## polyomino puzzles

The basic idea is that we begin with a single square, and from there, recursively add squares. Depending on the details, it may count each n -omino n times, once from starting from each of its n squares, or may be arranged to count each once only.

The simplest implementation involves adding one square at a time. Beginning with an initial square, number the adjacent squares, clockwise from the top, 1, 2, 3, and 4. Now pick a number between 1 and 4, and add a square at that location.Square: 6 solutions. A trivial result, but the number of solutions comes in handy in more complex puzzles like the poly-5 diamond.

The 5 tetrominoes are well known from their use in the video game "Tetris". Tetris does not allow the pieces to be flipped mirror-reflected ; its pieces comprise the 7 "one-sided" tetrominoes.

Due to a parity imbalancethe 5 free tetrominoes cannot fit into a simple rectangle without introducing holes or other irregularities. However, if we consider a 5x4 rectangle and join the short sides together to form a cylindrical tube, we can find solutions:. In this solution, the 4x1 "I4" piece spans the join between right and left edges.

Here it is, unwrapped:. These puzzles use the 1 monomino, 1 domino, 2 trominoes, and 5 tetrominoes, for a total of 29 squares. Skewered square design by Dan Klarskov : 1, solutions. Skewered 9x3 rectangle design by Dan Klarskov : 5, solutions. Skewered 7x3 rectangle: solutions. This is just a 7x4 rectangle using the polyominoes of order 2 through 4, plus the monomino separately. I thought it was cute. These puzzles use the 1 monomino, 1 domino, 2 trominoes, and 7 tetrominoes, for a total of 37 squares.

Octagon: solutions incomplete. Square: 7, solutions.

### A Polyomino Tiling Algorithm

Octagon: 1, solutions. Diamond: 7, solutions. Aztec Diamond: 11, solutions. These puzzles use the 1 domino, 2 trominoes, 5 tetrominoes, and 12 pentominoes, for a total of 88 squares. X designed for G4G10 :solutions. These puzzles use the 1 monomino, 1 domino, 2 trominoes, 5 tetrominoes, and 12 pentominoes, for a total of 89 squares.

Diamond a. Kadon's "Poly-5" : solutions incomplete. These puzzles use the 1 monomino, 1 domino, 2 trominoes, 5 tetrominoes, 12 pentominoes, and 35 hexominoes, for a total of squares. As with the poly-5 diamond above, the various orders of polyominoes occupy different areas.

The hexominoes red occupy the outer ring of the configuration. Polyominoes of Order 1 Through 3 This puzzle uses the 1 monomino, 1 domino, and 2 trominoes, for a total of 9 squares. Square: 6 solutions A trivial result, but the number of solutions comes in handy in more complex puzzles like the poly-5 diamond.

Tetrominoes The 5 tetrominoes are well known from their use in the video game "Tetris". However, if we consider a 5x4 rectangle and join the short sides together to form a cylindrical tube, we can find solutions: 5x4 tube: 7 solutions In this solution, the 4x1 "I4" piece spans the join between right and left edges. Polyominoes of Order 1 Through 4 These puzzles use the 1 monomino, 1 domino, 2 trominoes, and 5 tetrominoes, for a total of 29 squares.

One-Sided Polyominoes of Order 1 Through 4 These puzzles use the 1 monomino, 1 domino, 2 trominoes, and 7 tetrominoes, for a total of 37 squares. One-Sided Polyominoes of Order 2 Through 4 These puzzles use the 1 domino, 2 trominoes, and 7 tetrominoes, for a total of 36 squares.Years ago, I programmed a polyomino solution engine, that was able to solve any polyomino puzzle, based on run-time parameters.

The same program is now avaliable in Java. On this page are a number of examples. In all puzzles exactly the same java applet is used; the different puzzles are completely specified in HTML.

Most of the problems presented on this page are published in Appendix B of Solomon Golomb's book. I left out two kinds of problems: those my applet cannot solve, and those for which has been proven no solutions exist.

Each problem is presented with its number from the appendix in Golomb's book, a short description, a tiny picture of a solution, and the total number of solutions according to the applet. I added some problems myself, which don't have a number. Clicking the "Solve" link starts the solver in a separate window. Jagged square with 12 pentominoes and one monomino. The monomino can only be at the edge. Triplication of the "F": use 9 of the other pentominoes to construct an "F" three times the normal size.

Obtain simultaneous solutions for the previous two problems by constructing two 4 x 10 rectangles. Use the set of 35 hexominoes to construct this almost rectangular shape. It is not possible to fit the hexominoes into a perfect rectangle. Like 68a, but now the pentominoes form a "rook" in the center of the rectangle. I had to split it into two puzzle definitions; puzzle 1 is the hexomino part, puzzle 2 the pentomino part. Special thanks to Steve Strickland for defining the heptomino set. One of the subparts is a triangle congruent subparts are not possible here.

An 8 x 8 with the corners removed, and consisting of two congruent subparts. An 8 x 8 with a hole in the middle, and consisting of two congruent subparts. Construct an 8 x 10 rectangle from the 12 pentominoes and the 5 tetrominoes. Construct an 4 x 20 rectangle from the 12 pentominoes and the 5 tetrominoes.

Construct a 5 x 16 rectangle from the 12 pentominoes and the 5 tetrominoes. Solution provided by Andrew Clarke. Solution provided by Stephen Montgomery-Smith. This solution by Andrew Clarke. Use the 35 hexominoes and the 12 pentominoes to build a 18 x 15 rectangle. Solve 1 Solve 2.I became a bit obsessed with Sudokuand soon wanted to write my own Sudoku solver actually I wanted to write my own Sudoku game.

But after seeing a lot of pictures of polyomino puzzles, my interest in writing a Sudoku solver deviated to a polyomino puzzle solver. I thought that filling a board with polygons of diferent shapes and colors seemed a bit more interesting than filling a board with numbers. A polyomino is a collection of cells equal-sized squares which are connectedthat is, each cell shares a border with another one.

Looks like attaching a Greek prefix was fancier. For example, the seven Tetris pieces are one-sided tetrominoes, because the S and J tetrominoes are flipped to get the Z and L, respectively…. Pentomino 5-cell polyomino puzzles were more common than I thought. As far as I know, they are mentioned in Arthur C.

The objective is to tile a set of pentominoes on a rectangular board without leaving any blank space.

Jake Armstong's CS135 (UWaterloo) Polyomino Puzzle Solver

After reading a bit on the subject, I decided to write a pentomino puzzle solver. There were different ways to solve this problem, but I started with the simplest one. The basic idea of this simple method is as follows:. Given a list of polyominoes of order nwe add a square to each one of them, in each possible position, and we remove any duplicates. In the following pictures, you can see how all polyominoes of order 3 are generated:.

First, the algorithm starts with a monomino. For each position adjacent to it, it adds a square. The final step is to check that there are no duplicates, i. There are two equal dominoes, so it discards them. Now it starts doing the same thing it did for the monomino, but this time for each of the two dominoes. You can see from the picture that the second domino only bears one new trinomino, because almost all of them are duplicates. First, I represented a polyomino as a set of cellsi.

The integers meant the position of a cell in a grid. I also incorporated the following functionality to my Polyomino class:.Skip to content. Instantly share code, notes, and snippets. Code Revisions 2. Embed What would you like to do? Embed Embed this gist in your website. Share Copy sharable link for this gist. Learn more about clone URLs. Download ZIP. Polyomino Solver.