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 306090 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 306090 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 306090 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 GNU LGPL 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
306090 triangles, and a set of 21 "tiles", each consisting of 36
306090 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
306090 triangles, and a set of 66 "tiles", each consisting of 36
306090 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 306090 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 sixfold 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 306090 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
306090 triangles, and a set of 64 "tiles",
consisting of 36 306090 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 306090 triangles, and a set of 8 "tiles",
each consisting of 36 306090 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
306090 triangles, and a set of 45 "tiles", each consisting of 36
306090 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
306090 triangles, and a set of 4 "tiles", T1, T2, T3 and T4,
each consisting of 36 306090 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
306090 triangles, and a set of 8 "tiles", each consisting of 36
306090 triangles, and seeks an arrangement of the tiles that
exactly covers the region.
Reference:

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.

Solomon Golomb,
Polyominoes: Puzzles, Patterns, Problems, and Packings,
Princeton University Press, 1996,
ISBN: 9780691024448

Ed Pegg,
Polyform Patterns,
in Tribute to a Mathemagician,
Barry Cipra, Erik Demaine, Martin Demaine, editors,
pages 119125, A K Peters, 2005.

Mark Wainwright,
Prize specimens,
Plus magazine,
01 January 2001,
https://plus.maths.org/content/prizespecimens
Source code:

adjacency_plot.m,
plots the 36 306090 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 306090 triangle.

triangle_neighbors_ij.m,
computes the (i,j) coordinates of vertices of the neighbor triangles
for a 306090 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 306090 triangle.

triangle_neighbors_xy.m,
computes the (x,y) coordinates of vertices of the neighbor triangles
for a 306090 triangle.

triangle_neighbors_xy_plot.m,
using the (x,y) coordinate system,
shows the 3 neighbor triangles
for a 306090 triangle.

triangle_ij_plot.m,
displays the 306090 triangles comprising an object,
using (i,j) coordinates.

triangle_xy_plot.m,
displays the 306090 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.
Last revised on 08 June 2022.