trinity


trinity, an Octave 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.

The trinity puzzle was devised as a warm-up exercise for the eternity puzzle, which involves a region of 2,508 triangles, and 209 tiles, each composed of 36 triangles.

To find a tiling of R, we can write 144 linear equations. Linear equation #I expresses the condition that triangle #I must be covered exactly once by one of the 4 tiles. Each tile has as many as 12 orientations, (involving rotations, reflections, and mirror imaging) and a variable number of possible translations. The resulting underdetermined linear system A*x=b can be treated as a linear programming (LP) problem, written to an "lp" file, which can then be read by optimization software such as CPLEX, GUROBI, or SCIP, and all possible solutions computed.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

trinity is available in a MATLAB version and an Octave version.

Related Data and Programs:

eternity, an Octave 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, an Octave 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, an Octave 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, an Octave code which considers polyiamonds, simple connected shapes constructed from equilateral triangles connected edgewise.

polyominoes, an Octave 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_test

Reference:

  1. Marcus Garvie, John Burkardt,
    A new mathematical model for tiling finite regions of the plane with polyominoes,
    Contributions to Discrete Mathematics,
    Volume 15, Number 2, July 2020.
  2. Solomon Golomb,
    Polyominoes: Puzzles, Patterns, Problems, and Packings,
    Princeton University Press, 1996,
    ISBN: 9780691024448
  3. Ed Pegg,
    Polyform Patterns,
    in Tribute to a Mathemagician,
    Barry Cipra, Erik Demaine, Martin Demaine, editors,
    pages 119-125, A K Peters, 2005.
  4. Mark Wainwright,
    Prize specimens,
    Plus magazine,
    01 January 2001,
    https://plus.maths.org/content/prize-specimens

Source code:


Last revised on 23 May 2021.