t_puzzle, a MATLAB code which considers the T puzzle, a set of 4 wooden pieces. The challenge is to arrange the pieces to form the shape of the letter T. Three other challenge shapes are an arrow, a rhombus, and a "fat" T.
The full T shape can be constructed using two rectangles, each of dimensions 3 x 9 units. Thus, the T shape can be decomposed into 54 squares. We form an underlying grid in which each square is split into 4 isoceles right triangles. This grid then consists of 54 * 4 = 216 such triangles. The other three challenge shapes can also be represented as 216 such triangles. Similarly, the four puzzle pieces can be decomposed into 90, 66, 42 and 18 such triangles, respectively.
To find a tiling of the challenge shape, we can write 216 linear equations. Linear equation #I expresses the condition that triangle #I must be covered exactly once by one of the 4 pieces, in one of its possibly 8 orientations (involving rotations and reflections) and a variable number (much less than 216!) possible translations. Four additional constraints specify that each tile must be used exactly once. Finally, the linear system is required to have a binary solution, consisting of only 0's and 1's. The resulting linear system can be treated as a linear programming (LP) problem, using optimization software such as CPLEX, GUROBI, or SCIP.
The computer code and data files described and made available on this web page are distributed under the MIT license
t_puzzle is available in a MATLAB version.
boat, a MATLAB code which considers the boat tiling puzzle, a smaller version of the eternity puzzle. The boat puzzle specifies a region R composed of 756 30-60-90 triangles, and a set of 21 "tiles", each consisting of 36 30-60-90 triangles, and seeks an arrangement of the tiles that exactly covers the region.
boomerang, a MATLAB code which considers the boomerang tiling puzzle, a smaller version of the eternity puzzle. The puzzle specifies a region R composed of 2376 30-60-90 triangles, and a set of 66 "tiles", each consisting of 36 30-60-90 triangles, and seeks an arrangement of the tiles that exactly covers the region.
boundary_word_right, a MATLAB code which describes the outline of an object on a grid of isoceles right triangles, using a string of symbols that represent the sequence of steps tracing out the boundary.
eternity, a MATLAB code which considers the eternity puzzle, which considers an irregular dodecagon shape that is to be tiled by 209 distinct pieces, each formed by 36 contiguous 30-60-90 triangles, known as polydrafters.
pram, a MATLAB code which considers the pram puzzle, a smaller version of the eternity puzzle. The pram puzzle specifies a region R composed of 2304 30-60-90 triangles, and a set of 64 "tiles", consisting of 36 30-60-90 triangles, and seeks an arrangement of the tiles that exactly covers the region.
serenity, a MATLAB code which considers the serenity puzzle, a smaller version of the eternity puzzle. The serenity puzzle specifies a dodecagonal region R composed of 288 30-60-90 triangles, and a set of 8 "tiles", each consisting of 36 30-60-90 triangles, and seeks an arrangement of the tiles that exactly covers the region.
t_puzzle_cplex_test, a BASH code which calls cplex(), to read the LP file defining the T-puzzle tiling problem, solve the linear programming problem, and write the solution to a file.
t_puzzle_gui, a MATLAB code which sets up a graphical user interface for the T puzzle, by Cleve Moler.
t_puzzle_gurobi_test, a BASH code which calls gurobi(), to read the LP file defining the T-puzzle tiling problem, solve the linear programming problem, and write the solution to a file.
tortoise, a MATLAB code which considers the tortoise tiling puzzle, a smaller version of the eternity puzzle. The puzzle specifies a region R composed of 1620 30-60-90 triangles, and a set of 45 "tiles", each consisting of 36 30-60-90 triangles, and seeks an arrangement of the tiles that exactly covers the region.
trinity, a MATLAB code which considers the trinity puzzle, a smaller version of the eternity puzzle. The trinity puzzle specifies a region R composed of 144 30-60-90 triangles, and 4 "tiles", T1, T2, T3 and T4, each consisting of 36 30-60-90 triangles, and seeks an arrangement of the four tiles that exactly covers the region.
whale, a MATLAB code which considers the whale tiling puzzle, a smaller version of the eternity puzzle. The whale puzzle specifies a region R composed of 288 30-60-90 triangles, and a set of 8 "tiles", each consisting of 36 30-60-90 triangles, and seeks an arrangement of the tiles that exactly covers the region.