Welcome!

About This App

This is a solver for DragonFjord's A-Puzzle-A-Day. The solver is a SvelteKit application with the main logic written in Rust and compiled into Wasm. Every time the solve button is clicked, the Wasm file is executed to solve for the target date in real time. The solutions are not pre-calculated!

Representing the Problem

The board and the puzzle pieces are represented within the code as $M \times N$ matrices where $M$ is the number of rows and $N$ is the number of columns. The elements of the matrix are used to represent the shape of a puzzle piece and the board with 0's representing holes and 1's representing filled spaces. An example of how a puzzle piece is represented as a matrix is shown in Figure 1.

M\bigg\lbrace \overbrace{\begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}}^{\text{N}}

Figure 1. How a puzzle piece is represented as a 2×3 matrix in the code.

When representing the board, the board is squared off and the boundary pieces filled with 1's. The target date is also filled with 1's to indicate that a piece cannot be placed there. A visualisation of this can be seen in Figure 2.

\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}

Figure 2. How the board is represented as a 7×7 matrix in the code when the target date is the 14th of Jan.

The Solution Space

A solution to the A-Puzzle-A-Day is when the puzzle pieces are placed on the board such that only today's day and month are visible. To get to a solution, numerous permutations need to be tested. The number of permutations of n distinct options is n factorial.

Note, in mathematics the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example: $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ .

Naïve Solution

At first glance, there are 8 puzzle pieces to choose from (shown in Table 1) and 8 pieces need to be placed.

Table 1. The puzzle pieces which can be placed.

Piece

Therefore, one might assume the number of permutations that need to be tested is: $8! = 40320$ BUT each piece represents more than 1 piece due to rotations and flips.

Full Solution

By taking into account rotations and flips, each puzzle piece is actually 1 of 8 unique pieces which can be placed. These will be refered to as a piece's unique orientations. For example, the 2×3 zig-zag has 8 unique orientations as shown in Figure 3.

Figure 3. The 8 unique orientations of the 2×3 zig-zag piece. The top row shows the 4 unique rotational orientations of the piece (rotated by 90°). The second row shows the 4 unique rotational orientations of the piece when flipped.

The unique orientations of each piece are summarised in Table 2. This is broken down into the number of rotational and reflection positions for each piece.

Table 2. How many unique rotational positions, flipped (reflection) positions, and total unique orientations a piece has.

Piece
Rotational positions (R)	4	4	4	4	4	4	4	4
Flip (reflection) positions (F)	2	2	2	2	2	2	2	2
Unique orientations (=R×F)	8	8	8	8	8	8	8	8

Now, finding a solution can be described as traversing through a tree structure as shown in Figure 4. Key terminology is defined below:

Node: contains data and may link to other nodes. The basic unit of a data structure. In this particular use case, a node represents the unique orientation of a puzzle piece that is placed.
Edge: the connection between nodes.
Path: the sequence of nodes between two given nodes in the tree structure.
Root node: the node at the top of the tree which has no parent. There is only one root per tree and one path from the root node to any other node in the tree structure. The root node corresponds to 0 pieces (i.e. an empty board).
Child node: any node which extends from another node.
Parent node: the node which a child node extends from.
Leaf node: a node with no children.
Siblings: nodes which extend from the same parent node.
Degree: the number of children a node has (corresponds to the number of unique piece orientations to choose from for the next turn).
Level: the number of edges along the unique path between a node and the root node. The level number equals to how many pieces have been placed. Each level corresponds to a piece type. For example, the first level may correspond to placing the L-shape piece in one of its 8 unique orientations.
Sub-tree: represents the descendants of a node.
Traversal: the process of visiting each node in the tree exactly once.
Pruning: Removing a whole section of a tree.

Figure 4. A snippet of the tree structure which is traversed to find solutions for a target date. The degree of a node corresponds to the number of unique orientations the next piece to be placed has. Refer to Table 2 for the number of unique orientations a piece has. Note, for clarity only a small portion of the tree is shown with some nodes hidden. The structure is labelled with the terminology defined above: root node, edge, parent node, child node, sub-tree, leaf node, siblings and levels.

Therefore, the total number of permutations is calculated as follows: $\begin{equation}\boldsymbol{d} = (d_0, d_1, d_2, ..., d_{L-1})\end{equation}$ $\begin{equation} P(L, \boldsymbol{d}) = L! \times \prod_{i=0}^{L-1}\boldsymbol{d}_i \end{equation}$ where:

L: is the total number of levels (i.e. how many pieces need to be placed).
d: is an array of the degrees of the nodes at level i, excluding the leaf nodes (L8).

Therefore, the total number of permutations calculated using equations (1) and (2) is: $\boldsymbol{d} = (8, 8, 8, 8, 8, 8, 8, 8)$ For comparison, there are estimated to be $2 \times 10^{11}$ to $4 \times 10^{11}$ stars in the milky way.

Smart Solution

Not all of the pieces orientations are unique as some pieces have rotational symmetry and reflection symmetry. Rotational symmetry is when a shape can be rotated by n degrees and appear unchanged. For example, in Figure 5 the 2×3 rectangular piece can be rotated by 180° and appear unchanged.

Figure 5. The rotational symmetry of the 2×3 rectangular piece. It has a order of rotational symmetry of 2. This means when the piece is rotated by 180° it appears unchanged.

Reflection (or mirror) symmetry is when the mirror image of a shape appears unchanged. For example, in Figure 6 the mirror image of the 2×3 rectangular piece appears unchanged and can be overlaid on top of the original image.

Figure 6. The reflection symmetry of the 2×3 rectangular piece. Its mirror image appears unchanged and can be overlaid on top of the original image.

Therefore, by taking into account the symmetry of the pieces, the number of permutations that need to be tested is reduced. Table 3 summaries the updated number of rotations and flips for each piece.

Table 3. How many unique rotational positions, flipped (reflection) positions, and total unique orientations a piece has when taking into account rotational and reflection (mirror) symmetry.

Piece
Rotational positions (R)	2	4	4	4	4	4	2	4
Flip (reflection) positions (F)	1	1	2	2	2	2	2	1
Unique orientations (=R×F)	2	4	8	8	8	8	4	4

Therefore, the total number of permutations calculated using equations (1) and (2) is: $\boldsymbol{d} = (2, 4, 8, 8, 8, 8, 4, 4)$

Where a Piece is Placed

The first available space (board position) is found by scanning across the board left to right and top to bottom, like reading a sentence, as shown in Figure 7.

Figure 7. The next available board position is found by scanning across the board left to right and top to bottom, like reading a sentence.

A puzzle piece is placed on the first available square on the board. When placing a piece, the first "square" of the piece is placed on top of the first available square on the board, as shown in Figure 8.

Figure 8. The first "square" of the piece is placed on top of the first available square on the board as determined in Figure 7.

Note, a puzzle piece is only placed if it is a valid position (see next section).

Definition of Valid

Before placing a piece in one of its unique orientations, the following questions are asked to determine if the piece will be placed in a valid position:

Will the puzzle piece go outside the bounds of the puzzle board?
Will the piece overlap with any pieces that have been placed or the target date (target date is a filled square)?
Will placing the piece leave any unreachable holes?

A hole (an element of the board matrix with a value of 0) is any board position which hasn't been covered with a piece and is not the target date. If a hole is too small, no piece can be placed there without overlapping with other pieces that have been placed. I.e it is unreachable.

If the answer to any of the above questions is yes, the position is not valid and the piece in its current unique orientation cannot be placed.

Lets take Figure 9 which assumes today's date is the 1st of September. If the purple piece is to be placed on to the next available board position, the "May" square becomes the next available board position. However, no piece can be placed on the "May" square without overlapping with the already existing piece. It is unreachable. Hence, this is not a valid position.

Figure 9. Placing the 2×3 middle hole piece at the next available board position results in an unreachable hole at the "May" square. Hence, placing that piece in its current unique orientation is not valid.

How a Piece is Placed

If the piece's unique orientation cannot be placed at the current available board position, the piece's orientation is changed or a new piece may be attempted to be placed instead. The process for exhausting all of a piece's orientations are governed by the rules below. This process is repeated each time a piece's orientation is changed:

If the piece has not exhausted its rotations, rotate the piece by 90°.
Else if the piece has exhausted its rotations, flip the piece if it can be flipped and has not already been flipped.
Else move on to the next available puzzle piece.

Note, the number of unique rotational positions is for each side of a piece if it is flippable. I.e. each side has n unique rotational positions. Refer to Table 3 for how many rotations and flips each piece can undergo. The animation in Figure 10 shows how a piece's orientation is exhausted. The steps consist of:

Rotating the piece 3 times to obtain 4 unique rotational orientations.
Flipping the piece.
Rotating the piece 3 times to obtain 4 new unique rotational orientations.
Flipping the piece which returns it back to its starting orientation.

Figure 10. How the 8 unique orientations of the 2×3 zig-zag piece are exhausted. First the piece is rotated through all of its unique rotational positions. Then, flipped (if it can be flipped). And again, rotated through all of its unique rotational positions.

However, with only these 3 steps, not all valid solutions will be found. We also need to account for puzzle piece orientations with holes in the top row of a puzzle piece. The process for exhausting all of a piece's orientations is now:

If the first "square" of the piece is a hole, move the piece to the left by n squares until the next available board position aligns with the piece's first filled square on the top row.
Else if the piece has not exhausted its rotations, rotate the piece by 90°.
Else if the piece has exhausted its rotations, flip the piece if it can be flipped and has not already been flipped.
Else move on to next available puzzle piece.

Note, this process is repeated each time a piece's orientation is changed. The animation in Figure 11 shows how moving pieces to the left, if there are holes in the top row, allows pieces to be placed on the board in valid positions which were previously unreachable based on the old process.

Figure 11. Translating the 2×4 zig-zag piece allows the piece in its unique orientation to be placed on the next available board position which is impossible to do without translating.

Writing the Algorithm

The solver algorithm is a depth-first tree traversal with branch pruning. The video below (Figure 12) is a visualisation of how the solver traverses through the tree of the possible permutations. The tree only contains the first 4 levels (i.e. the first 4 pieces being placed) with the order of the pieces fixed. The root node, L0, corresponds to an empty board (i.e. no pieces have been placed). The node levels and the pieces they represent are summarised in Table 4.

Table 4. The puzzle pieces which can be placed, the level of the tree structure which they correspond to, and how many unique orientations they have.

Level	L1	L2	L3	L4	L5	L6	L7	L8
Piece
Unique orientations	2	4	8	8	8	8	4	4

Traversing through the tree is as follows:

Starting with an empty board (i.e. the root node) try to place a piece at the next available square on the board (i.e. visit a node at L1, which is a child of the root node).
If placing the piece is valid, another piece is attempted to be placed at the next available square on the board (i.e. visit a node at L2 which is a child node of the last visited L1 node).
If placing the piece is not valid, remove that piece and try another piece (i.e. the visited L2 node can be pruned and all its child nodes do not need to be visited. Visit another L2 node that is a child to the last visited L1 node).

These steps are repeated until the whole tree has been traversed. Figure 12 is a visualisation of this traversal process. Note the following:

Orange nodes are nodes which are currently being visited (i.e. testing if placing that piece's unique orientation on the next available square on the board is valid).
Red nodes are nodes which have already been visited (i.e. tested if valid).
Grey nodes are nodes which been pruned.
Branch pruning is arbitrary and is only for visualisation purposes. It does not correspond to an actual solution.

The colour of the nodes which have not been visited correspond to the colour of the pieces used in the tables throughout this page.

Figure 12. A video of tree traversal using a depth first algorithm. As each node is visited, it turns red. If it is a invalid permutation, it is pruned, and all of its children nodes turn a translucent grey. This video was created using the GraphStream Java library.

The full tree for the fixed order of pieces as shown in Table 4 has an additional 4 levels (L5 - L8). And 8! (8 factorial) of these trees with the same root node are needed to account for the permutations of the order of the pieces placed (i.e. when changing the order at which pieces are placed). Refer to Equation 1 and Equation 2.