trinity_solution, a MATLAB code which prints or plots a solution to the trinity tiling puzzle, after it has been defined by trinity_lp_automatic() and solved by cplex().
The function trinity_lp_automatic() is part of the trinity() code. It sets up a 144 x 142 underdetermined linear system, in which the 144 equations each correspond to a single triangle in the trinity grid, and the 142 variables each represent a single configuration involving rotation, reflection and translation, of one of the four trinity tiles. The solution is constrained to contain only 0 and 1 values, with a 1 value indicating that the corresponding configuration is to be used in the tiling.
The function trinity_lp_automatic() writes this linear system to an LP file, which has enough information to completely describe the linear system. This linear system can be solved by packages such as cplex(), gurobi(), and scip(). Each package returns the solution in its own particular format, so a procedure must be provided to extract the solution vector and pass it on to MATLAB.
In this case, we assume the solution was computed by cplex(), and we provide the function cplex_solution_read() to extract the solution. We then use the function trinity_solution_plot() to display a plot of the tiling. Visual inspection of the plot should confirm that each of the four tiles is used once, that each tile remains entirely inside the trinity region, and every triangle of the trinity region is covered exactly once by one of the tiles.
In theory, having gone through the process of generating, solving, and displaying a solution of the tiling problem for the trinity puzzle, the same procedures can be applied to find all solutions to the eternity puzzle, which involves 209 tiles, each consisting of 36 triangles of 30-60-90 shape, and a grid of 7,524 such triangles in the shape of a slightly irregular dodecagon. The linear system to be generated will have 7,524 rows, but more importantly will have millions of columns, because each of the 209 tiles now has a very large number of configurations that will remain in the grid.
The Octave version of this library is not working. I installed the io package, which enables xmlread(), but I still need to install xercesImpl.jar or xml-apis.jar...
The computer code and data files described and made available on this web page are distributed under the MIT license
trinity_solution is available in a MATLAB version and a MATLAB version.
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.
eternity_tile, a MATLAB code which considers the individual tiles of the eternity puzzle, 209 distinct pieces, each formed by 36 contiguous 30-60-90 triangles, known as polydrafters.
pariomino, a MATLAB code which considers pariominoes, which are polyominoes with a checkerboard parity, and the determination of tilings of a region using a specific set of pariominoes.
polyiamonds, a MATLAB code which considers polyiamonds, simple connected shapes constructed from equilateral triangles connected edgewise.
polyominoes, a MATLAB code which defines, solves, and plots a variety of polyomino tiling problems, which are solved by a direct algebraic approach involving the reduced row echelon form (RREF) of a specific matrix, instead of the more typical brute-force or backtracking methods.
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 a set of 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.
Here is information related to the generation of the cplex() solution file.