eternity

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.

The region R can be decomposed into a coarse grid of hexagons, some of which are only partially contained in R, or a fine grid of 30-60-90 triangles, completely contained in R. We refer to these as the grid and the "subgrid". The grid can be drawn by bounding R by 90 nodes, and then connecting certain pairs, resulting in grid lines in 3 directions. The subgrid can be drawn by 180 boundary "subnodes", connecting certain pairs, and resulting in grid lines in 6 directions.

The subgrid is formed by 209 * 12 = 2508 congruent 30-60-90 triangles. To find a tiling of R, we can write 2,508 linear equations. Linear equation #I expresses the condition that triangle #I must be covered exactly once by one of the 209 shapes, in one of its possibly 12 orientations (involving rotations, reflections, and mirror imaging and a variable number of possible translations. The resulting underdetermined linear system can be treated as a linear programming (LP) problem, using optimization software such as CPLEX, GUROBI, or SCIP.

Licensing:

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

Languages:

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

Related Data and Programs:

eternity_test

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, 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.

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:

• adjacency_plot.m, plots the 36 30-60-90 triangles that form an object.
• adjacency_to_triangle_ij.m, computes (i,j) coordinates of triangle vertices from adjacency.
• adjacency_to_triangle_xy.m, computes (x,y) coordinates of triangle vertices from adjacency.
• boolean_to_string.m, returns "True" or "False", given a boolean value.
• border_plot.m, displays the border of a region by connecting the vertices, using either (i,j) or (x,y) coordinates.
• boundary_word_compass_plot.m, displays the compass used for boundary words.
• ch_wrap.m, forces a character to lie between given limits by wrapping.
• chvec_lt.m, is TRUE if c1
• color_rgb.m, returns the RGB values of one of 20 colors.
• edge_plot.m, plots the edge nodes of an object.
• eternity_grid_line_edges.m, indexes edge nodes that end grid lines for the Eternity grid.
• eternity_grid_line_plot.m, plots the grid lines for the Eternity grid.
• eternity_vertex_xy.m, returns (x,y) coordinates of the 12 vertices for the Eternity grid.
• eternity_word.m, returns the boundary word for the Eternity grid.
• hexagon_adjacency.m, adjacency information for the hexagon grid.
• hexagon_edge_xy.m, (x,y) coordinates of edge nodes for the hexagon grid.
• hexagon_grid_line_edges.m, indexes edge nodes that end grid lines for the hexagon grid.
• hexagon_grid_line_plot.m, plots the grid lines for the hexagon grid.
• hexagon_node_label.m, labels of nodes for the hexagon grid.
• hexagon_node_xy.m, (x,y) coordinates of nodes for the hexagon grid.
• hexagon_triangle_k.m, returns the indexes (k) of the three nodes forming each triangle for the hexagon grid.
• hexagon_vertex_xy.m, (x,y) coordinates of vertices for the hexagon grid.
• hexagon_word.m, boundary word for the hexagon grid.
• hexagon3_grid_line_edges.m, indexes edge nodes that end grid lines for the hexagon3 grid.
• hexagon3_grid_line_plot.m, plots the grid lines for the hexagon3 grid.
• hexagon3_vertex_xy.m, returns (x,y) coordinates of the vertices for the hexagon3 grid.
• hexagon3_word.m, returns the boundary word for the hexagon3 grid.
• hexagon4_vertex_xy.m, returns (x,y) coordinates of the vertices for the hexagon4 grid.
• hexagon4_word.m, returns the boundary word for the hexagon4 grid.
• i4_wrap.m, forces an integer to lie between given limits by wrapping.
• is_octave.m, is TRUE if the function is called by Octave.
• ksub_random2.m, returns a random subset of k items from a list of n.
• node_ij.m, uses the boundary word to determine the (i,j) coordinates of nodes of an object.
• node_ij_plot.m, plots the (i,j) coordinates of nodes of an object.
• node_ij_to_xy.m, converts node coordinates from (i,j) to (x,y).
• node_xy_plot.m, plots the (x,y) coordinates of nodes of an object.
• polygon_contains_point.m, is TRUE if a polygon contains a point.
• polygon_draw.m, plots a polygon using (i,j) or (x,y) coordinates.
• r8mat_print.m, prints an R8MAT;
• r8mat_print_some.m, prints some of an R8MAT;
• rectangle_edge_xy.m, (x,y) coordinates of edge nodes for the NX by NY rectangle grid.
• rectangle_grid_line_plot.m, plots the lines for the NX by NY rectangle grid.
• rectangle_node_count.m, computes the number of nodes for the NX by NY rectangle grid.
• rectangle_node_ij.m, returns the (i,j) coordinates of the nodes for the NX by NY rectangle grid.
• rectangle_subnode_ij.m, returns the (i,j) coordinates of the subnodes for the NX by NY rectangle grid.
• rectangle_triangle_k.m, returns the indexes (k) of the three nodes forming each triangle for the NX by NY rectangle grid.
• rectangle_triangle_plot.m, plots the triangles that compose the NX by NY rectangle grid.
• rectangle_vertex_xy.m, (x,y) coordinates of vertices for the NX by NY rectangle grid.
• rectangle_word.m, returns the boundary word for the NX by NY rectangle grid.
• s_substitute.m, substitutes characters in a string.
• subnode_ij.m, uses the boundary word to determine the (i,j) coordinates of subnodes of an object.
• tile_word.m, the boundary word for any tile, given its index number.
• triangle_k.m, returns the node indices of the vertices of the triangles contained in an object.
• triangle_neighbor_ij.m, returns the (i,j) coordinates of the vertices of a specific neighbor triangle for a 30-60-90 triangle.
• triangle_neighbors_ij.m, computes the (i,j) coordinates of vertices of the neighbor triangles for a 30-60-90 triangle.
• triangle_neighbors_ij_plot.m, demonstrates triangle_neighbor_ij() by plotting a sequence of neighbor triangles, using the (i,j) coordinate system.
• triangle_neighbor_xy.m, returns the (x,y) coordinates of the vertices of a specific neighbor triangle for a 30-60-90 triangle.
• triangle_neighbors_xy.m, computes the (x,y) coordinates of vertices of the neighbor triangles for a 30-60-90 triangle.
• triangle_neighbors_xy_plot.m, using the (x,y) coordinate system, shows the 3 neighbor triangles for a 30-60-90 triangle.
• triangle_plot.m, displays the 30-60-90 triangles comprising an object.
• trinity_word.m, returns the boundary word for the trinity grid.
• type_to_color.m, translates an element type to a color index.
• vertex_plot.m, plots the vertices that define the polygon bounding an object.
• vertex_ij_print.m, prints the (i,j) vertices that define the polygon bounding an object.
• vertex_xy_print.m, prints the (x,y) vertices that define the polygon bounding an object.
• word_print.m, prints a boundary word of a shape.
• word_range_ij.m, returns the horizontal and vertical limits of an object, given its boundary word, using the (i,j) coordinate system.
• word_range_xy.m, returns the horizontal and vertical limits of an object, given its boundary word, using the (x,y) coordinate system.
• word_reflect_ij.m, returns the boundary word for an object reflected across the 0, 30, 60, 90, 120, or 150 degree line through the base point, using the (i,j) coordinate system.
• word_reflect_xy.m, returns the boundary word for an object reflected across the 0, 30, 60, 90, 120, or 150 degree line through the base point, using the (x,y) coordinate system.
• word_representative.m, returns the representative for a boundary word, the lexically first member of the equivalence class.
• word_reverse.m, returns the boundary word for an object when it is traversed in the reverse direction.
• word_rotate_xy.m, returns the boundary word for a rotated object, using the (i,j) coordinate system.
• word_rotate_xy.m, returns the boundary word for a rotated object, using the (x,y) coordinate system.
• word_to_edge_ij.m, determines the (i,j) coordinates of edge nodes from a boundary word.
• word_to_edge_xy.m, determines the (x,y) coordinates of edge nodes from a boundary word.
• word_to_vertex_ij.m, determines the (i,j) coordinates of vertices from a boundary word.
• word_to_vertex_xy.m, determines the (x,y) coordinates of vertices from a boundary word.
• word_translate.m, returns the boundary word for a translated object.