DRMacIver's Notebook
Notes on tiling with polyominoes
Notes on tiling with polyominoes
Gary Fredericks wrote about a backtracking algorithm for tiling a board with polyominoes.
His solution is roughly “turn the problem into exact cover and then apply a bunch of interesting optimisations in this context to the naive backtracking algorithm”. The paper Dancing Links by Donald E. Knuth in fact studies this exact problem as an application of the exact cover algorithm.
I think some of the optimisations Gary performs are not ones that would be performed by a modern SAT solver because they are actually too expensive to be worth it if you’re good at the SAT problem-e.g. I know modern SAT solvers tend not to bother decomposing problems into independent problems because the cost is too high-but it’s possible they synergise well enough to be worth it. e.g. the number theory optimisation combined with the independent components may well be worth it, especially with the heuristic of prioritising moves that disconnect the board.
I’ve been doing a bit of casual reading about this class of problem recently. I thought I’d use the opportunity of this new notebook to collect some references. Ideally these would be proper cites, but I haven’t got the citation part of the notebook system working yet.
Checker Boards and Polyominoes by Solomon W. Golomb is a classic here. It looks at the question of tiling the chessboard with a single square monomino and 11 tetrominos of various shapes. In particular it establishes:
- You can do this with right tetrominoes given any placement of the monomino
- There are only four squares where you can place the monomino if you want to do it with straight tetrominoes.
How to Tile a Chessboard by Trupti Patel is a nice expository piece on this.
Golomb also wrote Tiling with Polyominoes, studying much more general questions of how to tile truncated chessboards with polyominoes.
A classic version of this is what Wikipedia refers to as the mutilated chessboard problem (apparently following Max Black):
Suppose a standard 8×8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares?
The answer is no. In Tiling with Dominoes, N. S. Mendelsohn discusses two proofs:
First solution
From the checkerboard diagram, the region contains 30 black cells and 32 white cells. Since each domino covers 1 black and 1 white cell, tiling is impossible.
Second solution
When I was first shown the problem many years ago, it did not occur to me to colour the cells. The region itself had seven cells in the top and bottom rows and eight cells in the remaining rows. The same held for the columns. I proceeded to obtain information on how many dominoes pointed horizontally and how many vertically. The first count dealt with the vertical dominoes. If the region is tiled, the horizontal dominoes in the top row occupies an even number of cells. Hence, the cells in the top row that are not occupied by horizontal dominoes are odd in number. Thus there are an odd number of vertical dominoes between the first and second rows. Since the second row has eight cells, and an odd number are occupied by vertical dominoes coming down from the first row, there remain an odd number of cells in the second row. The same argument now shows there is an odd number of vertical dominoes from the second row to the third. Continuing this way, we see that there is an odd number of vertical dominoes between any pair of consecutive rows. Hence the total number of vertical dominoes is the sum of seven odd numbers, which is odd. In the same way, using columns instead of rows, there is an odd number of horizontal dominoes. Hence the total number of dominoes is even. Since there are 62 cells to cover, the number of dominoes required is 31, an odd number. Therefore, tiling is impossible.
He goes on to say:
Why do I produce two solutions to the puzzle? It is because I am interested in the question of which is the better solution. At first glance, it appears that the first solution is the better. It is much shorter and is easily understood by many people with virtually no knowledge of mathematics. But are there considerations that might judge the second solution to be the better one?
He then discusses whether the second one is better because it generalises better, when setting out to prove Gomory’s theorem (which I’ve not been able to find a copy of the original of so far, but I haven’t looked very hard): If you remove two squares of the same colour, you can always tiling the remainder with dominoes. The proof involves the construction of a hamiltonian circuit on the adjacency graph, and seems fiddly but interesting. I’ve only skimmed it and would like to digest it further.
However note that we saw a generalisation in a different direction in the first paper linked! Golomb’s proof of the impossibility tiling with straight tetrominoes unless the monomino was in a very specific location was also a colouring argument.
The wikipedia page references “Across the board: the mathematics of chessboard problems” by John J. Watkins. I should probably look up a copy.