API Reference

Eternity2Puzzle()
Eternity2Puzzle(; starter_piece::Bool=true, hint_pieces::Bool=false)
Eternity2Puzzle(pieces::Union{Symbol, String}[, nrows::Int, ncols::Int])
Eternity2Puzzle(nrows::Int, ncols::Int; frame_colors::Int, inner_colors::Int, seed::Int=1)

The Eternity2Puzzle type represents a puzzle instance consisting of the piece definitions and the piece configuration on the board.

The constructor can be called in different ways:

The default constructor without arguments creates a puzzle with 16 rows and 16 columns and with the original Eternity II pieces. Keyword arguments starter_piece and hint_pieces control whether the mandatory starter-piece and the four hint pieces from the clue puzzles 1-4 are pre-placed on the board.

A different set of pieces with the corresponding board size can be used by passing either one of the predefined symbols :eternity2, :meta_16x16, :meta_14x14, :meta_12x12, :meta_10x10, :clue1, :clue2, :clue4, or a path to a file containing the edge color numbers for the pieces in the format as described in the README of this package. In the latter case, the input file is expected to contain an additional header line with the numbers of rows and columns of the board. If the header line is missing, the numbers of rows and columns must be declared explicitly by passing two integers in addition to the filepath. If provided, those numbers override the derived size of the board. This can also be used, for example, to solve a smaller sized board using only a subset of the specified pieces.

If only two integer arguments for the numbers of rows and columns are passed without the pieces argument, a puzzle is created with randomly generated pieces. Optional keyword arguments frame_colors and inner_colors can be used to adjust the numbers of frame and inner color types.

To load the piece configuration on the board from a file in .et2 format, use the load! function.

The Eternity2Puzzle type has two fields; board and pieces. board contains the piece numbers and rotations for each row/column position as a Matrix{UInt16}, where the first 14 bits of each entry represent the piece number and the last 2 bits are used for the rotation in clockwise direction. By convention a value of 0 is used if no piece is placed on a particular position of the board. pieces is a Matrix{UInt8} with rows containing the four color numbers for each of the pieces.

The Eternity2Puzzle type supports a few basic operations, such as getting or setting a piece on the board by indexing with the row and column numbers directly. The corresponding value is returned or must be provided as a tuple of two integers, representing the piece number and the rotation in clockwise direction. An example how to obtain the number and rotation of the pre-placed starter-piece on square I8 (row 9, column 8) of the original Eternity II puzzle is given below.

Examples

julia> puzzle = Eternity2Puzzle()  # The original Eternity II puzzle
16×16 Eternity2Puzzle with 1 piece:
...

julia> puzzle[9, 8]  # Get number and rotation of the piece on square I8 (row 9, column 8)
(139, 2)

julia> load!(puzzle, "path/to/saved_board.et2")  # Load pieces on the board from a file

julia> puzzle = Eternity2Puzzle(:clue1)  # Clue puzzle 1
6×6 Eternity2Puzzle with 0 pieces:
...

julia> puzzle = Eternity2Puzzle(8, 8)  # A puzzle with randomly generated pieces
8×8 Eternity2Puzzle with 64 pieces, 112 matching edge pairs and 0 errors:
...

julia> reset!(puzzle)  # Clear the entire board

julia> puzzle = Eternity2Puzzle(:eternity2, 12, 12)  # Eternity II pieces, but smaller board
12×12 Eternity2Puzzle with 0 pieces:
...

Abstract type for a solver algorithm.

SimpleBacktrackingSearch()
SimpleBacktrackingSearch(; seed::Int=1, slip_array::Vector{Int}=[], exhaustive_search::Bool=false)

A simple backtracking search that can be used with arbitrary board sizes. Pre-placed pieces on the board are considered to be additional constraints for a valid solution. This search algorithm places pieces one after another onto the board and backtracks if no more matching piece can be placed. The implementation favours flexibility over maximum performance.

Examples

julia> puzzle = Eternity2Puzzle(:clue1)
6×6 Eternity2Puzzle with 0 pieces:
...

julia> solve!(puzzle; alg=SimpleBacktrackingSearch())
6×6 Eternity2Puzzle with 36 pieces, 60 matching edge pairs and 0 errors:
  26/1  28/1  31/1  10/1  13/1  14/2
  12/0   4/3  29/2   2/2  24/1   7/2
  18/0   8/2   5/2  32/0   1/3  11/2
  16/0  27/1  33/0  30/2   3/1  21/2
  20/0  35/1   6/2  19/3   9/2  25/2
  34/0  15/3  17/3  23/3  22/3  36/3

E2BacktrackingSearch(target_score::Int, seed::Int)

A backtracking algorithm for the original Eternity II puzzle that searches for arrangements with a high number of matching edges, controlled by the target_score parameter.

estimate_solutions(puzzle::Eternity2Puzzle)
estimate_solutions(puzzle::Eternity2Puzzle, path::Union{Symbol, Vector{String}} = :rowscan, slip_array::Vector{Int} = []; verbose::Bool = false)

Estimate the number of solutions for a given Eternity2Puzzle and the total number of nodes in the search tree for a backtracking algorithm, based on an extended version of the probability model for edge matching puzzles developed by Brendan Owen.

Pre-placed pieces on the board are considered to be additional constraints that must be satisfied in a solution.

The order in which pieces are placed onto the board can be controlled with the path argument. It can either be one of the predefined symbols :rowscan (fill row by row, starting from the bottom left corner), :colscan (fill column by column, starting from the bottom left corner), :spiral_in (in clockwise direction, starting from the top-left corner), or path can be given as a Vector{String}, containing all board positions explicitly; for example ["I8", "A1", "A2", "B1", ...]. Hereby it is required that each board position occurs exactly once, and that the positions of pre-placed pieces are at the start of the list. Note that if no invalid joins are allowed, the placement order doesn't effect the number of solutions, but it can have a significant influence on the total number of nodes in the search tree.

If a vector slip_array is given, its entries specify the numbers of placed pieces at which another invalid join is allowed. This means that a piece arrangement is considered to be valid even if not all of the inner joins match. For example the vector [220, 230, 240] specifies that at least the first 219 pieces have to be placed with all edges matching, at least 229 pieces have to be placed with no more than one invalid join, at least 239 pieces with no more than two invalid joins, and for the rest of the pieces there must be no more than three invalid joins in total. Note that all of the frame joins between neighboring frame pieces still have to match exactly.

If the verbose keyword argument is enabled, the cumulative sum of estimated partial solutions is printed to the console for each depth in the search tree of a backtracking search. This cumulative sum represents the number of nodes that the backtracking algorithm has to visit in order to explore the entire search tree. The ratio between the number of full solutions and cumulative sum of partial solutions can be a measure for the difficulty of the puzzle.

Return the number of solutions and the total number of nodes in the search tree as a tuple of Float128 values.

Examples

Estimated number of valid solutions for the Eternity II puzzle:

julia> puzzle = Eternity2Puzzle()
16×16 Eternity2Puzzle with 1 piece:
...

julia> trunc(Int, estimate_solutions(puzzle)[1])
14702

Estimated average number of nodes that a backtracking algorithm has to visit in order to find a full solution, using a row-by-row search path starting at the bottom left corner:

julia> solutions, nodes = estimate_solutions(puzzle)
(1.47022707008833935129885673337590720e+04, 1.36503111141314673778599540194846603e+47)

julia> nodes/solutions
9.28449175766521657015077720929987568e+42

References

• https://groups.io/g/eternity2/message/5209
• https://groups.io/g/eternity2/message/6408

play()
play(:clue1)
play(:clue2)
play(:clue4)

Start the interactive game.

preview(puzzle::Eternity2Puzzle)

Open a preview image of the puzzle board.

solve!(puzzle::Eternity2Puzzle)
solve!(puzzle::Eternity2Puzzle; alg::Eternity2Solver)

Start to search for a solution of the given Eternity2Puzzle.

Examples

julia> puzzle = Eternity2Puzzle()

julia> solve!(puzzle)

reset!(puzzle::Eternity2Puzzle)

Clear all pieces from the board (except for the starter-piece in case of the 16×16 board).

load!(puzzle::Eternity2Puzzle, filename::AbstractString)

Load the pieces on the board from a file in .et2 format.

The board dimensions of the given Eternity2Puzzle must be compatible with the numbers of rows and columns in the input file.

See also save.

save(puzzle::Eternity2Puzzle, filename::AbstractString)

Save the board of a given Eternity2Puzzle to a file in .et2 format.

See also load!.

score(puzzle::Eternity2Puzzle)

Return the numbers of matching and non-matching edge pairs on the board.

remap_piece_colors(puzzle::Eternity2Puzzle)

Remap and reorder the color numbers such that colors are consecutive numbers starting at 1, with all frame color numbers first and all inner color numbers last. The border color and another "virtual" border color for the corner pieces are appended to the end of the number list.

While the relative orderings of the color numbers within the set of the frame colors and the set of the inner colors are preserved, gaps between the color numbers are eliminated, so that they can be used as array indices.

Return a new matrix for the piece definitions using the remapped color numbers, and two UnitRanges for the numbers of the remapped frame colors and inner colors.

symmetry_factor(puzzle::Eternity2Puzzle)

Return the number of symmetries in the puzzle as a one-based factor, i.e. if there aren't any symmetries, the return value is 1. Symmetries can happen due to rotationally symmetric individual pieces, (rotationally identical) duplicate pieces, and possible rotations of the board if there aren't any fixed pieces on the board. The total number of puzzle solutions is divisible by this factor. When using a backtracking algorithm to enumerate all solutions of a given puzzle, it can be advantageous to first eliminate all the symmetries, for example by fixing one of the corner pieces and by restricting the rotations of the rotationally symmetric pieces, and then to multiply the number of found solutions by the corresponding factor.

generate_pieces(nrows::Int, ncols::Int, frame_colors::Int, inner_colors::Int, seed::Int)

Generate random pieces for an Eternity II style puzzle with nrows rows, ncols columns, frame_colors frame colors and inner_colors inner colors.

nrows and ncols must be between 3 and 20.

All generated pieces are unique and not rotationally symmetric. If no such pieces can be generated for the given numbers of frame colors and inner colors after 1000 iterations, the function throws an error.

Return a valid arrangement on the board (i.e. puzzle solution) and a matrix with the edge colors for the pieces.