eternity

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.

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 * 32 = 7524 congruent 30-60-90 triangles. To find a tiling of R, we can write 7,524 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

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_drafter, a MATLAB code which describes the outline of an object on a grid of drafters, or 30-60-90 triangles, using a string of symbols that represent the sequence of steps tracing out the boundary.

eternity_hexity, a MATLAB code which evaluates and manipulates a six-fold parity quantity associated with grids and tiles used in the Eternity puzzle.

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.

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.

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.

tortoise_cplex_test a BASH code which calls cplex(), to read the LP file defining the tortoise tiling problem, solve the linear programming problem, and write the solution to a file.

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.

trinity_cplex_test a BASH code which calls cplex(), to read the LP file defining the trinity tiling problem, solve the linear programming problem, and write the solution to a file.

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.

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.
• cplex_solution_multiple_read.m, extracts solution data from a structure obtained from a cplex() solution file that contained multiple solutions.
• cplex_solution_read.m, reads an XML file, converts the data to a structure, and extracts the data representing solutions.
• cplex_solution_single_read.m, extracts solution data from a structure obtained from a cplex() solution file that contained a single solution.
• 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_grid_word.m, returns the boundary word for the Eternity grid.
• eternity_lp.m, sets up the linear programming problem using sparse matrix storage, and writes it to an LP file, working only from the primary geometric data.
• eternity_tile_num.m, returns the number of tiles in the puzzle.
• eternity_tile_word.m, the boundary word for any tile, given its index number.
• eternity_vertex_xy.m, returns (x,y) coordinates of the 12 vertices 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.
• lp_alt_write.m, writes linear programming data to an LP file, using an alternative form for the objective function.
• lp_generate.m, generates linear programming data for a tiling problem.
• lp_write.m, writes linear programming data to an LP file.
• lpa_generate.m, generates linear programming data for a tiling problem, using a format suitable for an approximate approach.
• lpa_write.m, writes information generated by lpa_generate() to an LP file for the approximate eternity problem.
• 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, using (i,j) coordinates.
• rectangle_vertex_xy.m, (x,y) coordinates of vertices for the NX by NY rectangle grid, using (x,y) coordinates.
• rectangle_word.m, returns the boundary word for the NX by NY rectangle grid.
• region_contains_tile.m, is TRUE if a tile (after rotation, reflection, and translation) remains entirely inside a region.
• region_grid_ij_plot.m, displays the triangles composing a region, using (i,j) coordinates.
• region_grid_ij_tikz.m, displays the boundary or elemental triangles of a region, using (i,j) coordinates, with tikz output to a latex file.
• region_grid_xy_tikz.m, displays the boundary or elemental triangles of a region, using (x,y) coordinates, with tikz output to a latex file.
• s_substitute.m, substitutes characters in a string.
• solution_plot.m, plots a solution generated by cplex().
• solution_print.m, prints the tile configurations that comprise a tiling solution.
• solution_tikj_ij.m, creates a tikz() image of a solution, using (i,j) coordinates.
• solution_tikj_xy.m, creates a tikz() image of a solution, using (x,y) coordinates.
• subnode_ij.m, uses the boundary word to determine the (i,j) coordinates of subnodes of an object.
• tile_overlay_ij_plot.m, adds the image of a tile to a plot using (i,j) coordinates.
• tile_overlay_xy_plot.m, adds the image of a tile to a plot using (x,y) coordinates.
• tile_vertices_xy_tikz.m, prints the Tikz commands needed to plot the vertices of a tile.
• 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_ij_plot.m, displays the 30-60-90 triangles comprising an object, using (i,j) coordinates.
• triangle_xy_plot.m, displays the 30-60-90 triangles comprising an object, using (x,y) coordinates.
• 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_area.m, returns the area, in elementary triangles, of a polygon from its boundary word.
• word_parity.m, determines the parity of a shape.
• 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_ij.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_centroid_ij.m, determines the centroid of an Eternity object from its boundary word, using the (i,j) 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.
• xml2struct.m, reads an XML file and converts the data to a structure.