A New Kind of Play for A-Puzzle-A-Day

Year: 2024 Authors: Bruce Torrence

Core claim

A-Puzzle-A-Day supports a rich configuration graph in which many calendar solutions can be connected by sequences of allowed composite-piece moves.

Topics

polyomino tilings, configuration graphs, calendar puzzles, workshop activities

Domains

combinatorics, tiling theory, graph connectivity, exact cover, puzzle design, mathematical art, interactive workshop, visual pattern recognition

Methods

computer-assisted enumeration, depth-first search, move sequences, hands-on exploration

Media

A-Puzzle-A-Day, polyomino pieces, game board, Mathematica FindExactCover

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2024 Conference Proceedings

A New Kind of Play for A-Puzzle-A-Day

Bruce Torrence

Randolph-Macon College, Ashland, Virginia, USA; btorrenc@rmc.edu

Abstract

We typically build jigsaw puzzles piece by piece, starting with an empty tabletop and adding one piece at a time. For a puzzle whose pieces are polyominoes (which can fit together multiple ways) we explore a different paradigm: Starting from a completed puzzle, we perform a sequence of “moves” whereby an individual piece or an assemblage of contiguous pieces may be rotated or flipped, or pairs of such pieces or assemblages may be swapped, in order to arrive at a different configuration. In this workshop, we will explore this paradigm using A-Puzzle-A-Day, an eight piece polyomino puzzle that has different solutions for each day of the calendar year. While challenging, this mode of play is so versatile that from a single starting configuration, a sequence of moves can be made to reach a solution for any calendar date.

Polyomino Tiling Puzzles

A polyomino is a polygon comprising unit squares joined edge-to-edge. A simple example is the standard domino, built from two squares. Following this naming convention, a tromino is polyomino built from three squares, a tetromino from four, and a pentomino from five. We consider puzzles where the goal is to fit a specific set of polyomino pieces into a “game board,” itself a connected grid of unit squares whose total area meets or exceeds that of the pieces. In the puzzles considered here, players are permitted to flip or rotate each piece before placement—we are using so-called “free” polyominoes.

One of the first such puzzles to appear in print was communicated by Henry Dudeney in 1907, where the reader was charged to fit the 12 pentominoes and a $2\times 2$ square into an $8\times 8$ chessboard [1]. The terms “polyomino”, “tromino,” “tetromino,” and “pentomino” were coined decades later by Solomon Golomb, who both studied and, with assistance from Martin Gardner, popularized them [2].

(a)

(b)

(a) Figure 2: Solved configurations for A-Puzzle-A-Day.

Figure 1: A-Puzzle-A-Day game board and a non-date configuration (b)

A-Puzzle-A-Day is another such puzzle. The creation of Gerd Åsta Bones and Mike Naylor, it was commercially released in 2020 by Dragon Fjord Puzzles and Games. Here the game board has 43 labeled squares (12 for the months and 31 for the calendar days) and eight pieces (seven pentominoes and one $2\times 3$ rectangle), which in total cover just 41 squares. The goal is to fit the pieces into the board to reveal both the current month and the current day. See Figures 1, 2 and 3. One- and two-window puzzles existed prior to A-Puzzle-A-Day

Torrence

Figure 3: The eight puzzle pieces and their names

(one-window puzzles are often called “deficient tilings”). Three-window polyomino calendar puzzles have since appeared, where the goal is to simultaneously reveal the month, day number, and day of the week.

New players are often surprised to discover just how many solutions a puzzle has. For instance, a well-studied puzzle dating from 1935 is to fit the entire collection of 12 pentominoes into a $6\times 10$ rectangle [5]. By the end of the 1950s there were over 1500 known solutions to the puzzle, and in 1960 it was shown by computer that there are in fact 2339 distinct solutions (not counting those induced by flipping or rotating the entire gameboard) [4, 8]. According to my own computer-assisted calculation, A-Puzzle-A-Day has 24,405 distinct solutions that reveal a calendar date (including February 29). It is the richness of the solution space that affords an opportunity to imagine ways to “move” through it.

For those who are curious about the computing techniques used to enumerate solutions to polyomino puzzles: In [7], Donald Knuth describes his “dancing links” depth-first search technique, and gives an overview of the role that pentomino tilings had in the development of search algorithms. I used the Mathematica resource function FindExactCover for my enumerations [6].

A New Kind of Play

We define a configuration to be any placement of all of the puzzle pieces on the game board with no overlap. Note that a configuration for a calendar puzzle need not reveal a valid date; all that is required is that the pieces fit cleanly in the game board, as in Figure 1(b).

Now consider the “Aug 4” configuration on the far right in Figure 2(b). One could pick up the three pieces in the lower right, treating them like a single large piece, and rotate or flip this entire assemblage to get a new configuration, revealing any one of the 4, 7, 25, or 28. Similarly, the Y pentomino (we use the piece names specified in Figure 3) can be rotated to reveal 9 and cover 4. After this, the U could be flipped to reveal 8, or the U and the rectangle could be swapped to reveal either 23 or 30. Such actions are examples of what we call a move.

To formalize, we first define a composite of $n$ pieces recursively as follows: A composite of one piece is just that piece. For n > 1 , a composite of $n$ pieces is obtained by joining a puzzle piece to a composite of $n-1$ pieces, such that the new puzzle piece is connected to at least one other piece in the composite along at least one full edge in the underlying square grid. This rather cumbersome definition ensures that composites are rigid structures; they cannot be disconnected, or connected “only at a corner.” See Figure 4. Loosely speaking, a composite is just several individual pieces that we consider to be bonded together along adjoining edges to form a larger piece.

And we can now define a move: From a given configuration, we may simultaneously remove one or two composite pieces, and keeping each intact but possibly flipping, rotating, or otherwise reorienting and repositioning them, place them on the game board to obtain a valid configuration.

Returning to the example in Figure 2(b), rotating the three pieces in the lower right is a move where just one composite comprising these three pieces is rotated and returned to the game board. Similarly, rotating the

A New Kind of Play for A-Puzzle-A-Day

Figure 4: The structure on the left does not form a composite as the two pieces do not share an edge. The other three are valid composites.

Y piece is a move that repositions a single one-piece composite. After that move has been made, swapping the U piece with the rectangle is a move that repositions two single-piece composites. Or starting again from Figure 2(b), one could swap the composite UY with the yellow rectangle to reveal positions 1 and 4, and then swap the L with the rectangle to reveal April 4.

With the potential to move from one configuration to another, polyomino puzzles offer an entirely new mode of play: Given two configurations, is there a sequence of moves that transforms one to the other? In the remainder of this workshop, most of our time will be spent investigating variations on this question, using A-Puzzle-A-Day as our primary vehicle for exploration. The results of this activity may be somewhat surprising: We will see that not every pair of configurations admits a move sequence that transforms one to the other, but there is a very large subset of configurations where this is true for every pair in it. Although we will not have sufficient time in this workshop to verify it, I have proved that this set is large enough to include at least one representative for every calendar date. There is a configuration for January 1, for instance, from which it is possible to perform a sequence of moves to reach January 2, and from there to reach January 3, and so on. Indeed, given any of the $366\times 365=133$ , 590 ordered pairs of distinct dates (again, counting February 29), there is a move sequence from a configuration for the first date to one for the second. (For this mode of play, perhaps we should rename the puzzle “365 Puzzles A Day.“)

The notion of making “moves” of this sort is not new. Indeed, the idea was advanced in 1960 by the British mathematician and computing pioneer Jeffrey C. P. Miller, who used the term “exchange operations” for moves [8]. In the early 1990s a similar notion was developed by Wilfred Hansen, who programmatically explored all possible moves for the $6\times 10$ pentomino puzzle [3]. But making such moves as a means of play appears to be a new idea, and it is particularly well suited for puzzles such as A-Puzzle-A-Day that have one or more “windows.” First, the windows greatly expand the placement options for laying down composite pieces. This means that for a given configuration, a player typically has more moves available in a puzzle with windows than in one without. Second, the windows serve naturally as markers to differentiate configurations, inviting the type of challenge outlined previously: Find a sequence of moves that transforms one “date” to another.

Conceptually, we can visualize the universe of all possible moves for a polyomino puzzle as follows: On a (very large) poster board, make a sketch of every possible configuration. (For A-Puzzle-A-Day there are on the order of 100,000 of these!) Now draw a connecting line between a pair of configurations precisely when there is a single move that transforms one configuration to the other. In mathematical terminology, this construction is called a graph, where the configurations are the vertices and the moves are the edges. We will call it the configuration graph for the puzzle. A path of alternating vertices and adjoining edges in this graph then represents a sequence of moves. (A supplement to this paper illustrates an example path with 18 moves.) While the configuration graph for A-Puzzle-A-Day is impossibly large to visualize in its totality, we will, through our explorations, gain some insight into its structure. In particular, we will see that there is one dominant connected component, where each pair of configurations in this component can be joined by a path.

One more piece of terminology is in order: We say a collection of configurations is connected if there is a move sequence joining every pair in the collection.

Torrence

Activity 1: A Few Summer Days

We begin by exploring the current month of August. Starting from the configuration in Figure 5(a), observe first that a single move can produce a configuration for each of the days marked with a dot: Aug 7, Aug 25, and Aug 28.

(a)

(b)

(c) Figure 5: Several August configurations.

Next, rotate the composite comprising the rightmost five pieces by $180^{\circ }$ to obtain the configuration in Figure 5(b). Convince yourself that additional moves can be made to obtain a configuration for each August day marked with a dot.

Finally, from the configuration in Figure 5(b) rotate the composite comprising the bottom five pieces by $180^{\circ }$ to obtain the configuration in Figure 5(c). From here, convince yourself that additional moves can be made to obtain configurations for each day marked with a dot.

At this point we have found a connected set of configurations for the following 19 days in August: 4, 5, 6, 7, 9, 10, 11, 13, 16, 17, 18, 19, 20, 23, 25, 27, 28, 30, and 31. Just a handful of moves has given us more than half of the month. And, as a bonus, note that we also have a route to these same days in July (by flipping the U). So that’s 38 configurations with a move sequence between each pair, which collectively cover more than $10\%$ of the calendar year.

Center City

In order to expand this connected collection of configurations, it is useful to stake out a “central” configuration to which we can link new configurations via move sequences. From the configuration in Figure 5(a), flip the Y around its vertical axis to reveal the Oct 4 configuration shown in Figure 6(a). Note how this configuration neatly splits the board into the three composite pieces shown in Figure 6(b). There are three move types that preserve this structure: (1) flip or rotate the four pieces on the left that form the pink composite rectangle into any of its four orientations; (2) flip or rotate the three pieces that form green $4\times 4$ square with the missing corner into any of its eight orientations; and (3) flip or rotate the orange P pentomino into any of its four orientations. Since these three types of moves can be made independently of one another, we see that are $4\times 8\times 4=128$ configurations that can be obtained from the one in Figure 6(a) by at most three such moves. We will refer to any of these 128 configurations as “central” configurations, and we will refer to them collectively as “Center City.” Note that the 38 July/August configurations from the first activity are all connected via move sequences to a central configuration.

Activity 2: Exploring the Suburbs

How many calendar dates are represented by the Center City configurations?

It is, of course, natural to explore the nearby suburbs. Show that two moves can transform the central

A New Kind of Play for A-Puzzle-A-Day

(a)

(b)

(a)

(b)

(c) Figure 6: A central configuration Figure 7: Moving from Center City to the suburbs

configuration in Figure 6(a) to the one in Figure 7(a). Then show that configurations for each of the dates indicated by dots (except July 10) can be attained by making additional moves.

Show that two moves can transform the configuration in Figure 7(a) to the one in Figure 7(b). Then show that configurations for each of the dates indicated by dots can be attained by making additional moves.

Show that one move can transform the configuration in Figure 7(b) to the one in Figure 7(c). Then show that each of the dates indicated by dots can be attained by making additional moves. Find configurations for additional dates that can be obtained by swapping pairs of the P, U and rectangle pieces.

Show that configurations for the 4th, 7th, 25th, and 28th of every month can be obtained via moves from a central configuration.

Verify that in this activity you cataloged configurations for over 140 calendar days!

Activity 3: No Way In, No Way Out

At this point you may wonder if every pair of configurations can be linked via a sequence of moves. In order to show that this is not the case, consider the configurations in Figure 8.

Figure 8: The only possible move from either of these configurations leads to the other.

Convince yourself that there is only one possible move from either of these configurations, and it leads to the other. This will require extreme care and patience, as every possible composite piece, and every potential pair of composite pieces, must be considered.

Can you find another configuration that cannot be transformed to a central one?

Activity 4: A Sister City

Verify that there is a move sequence that gives the left-to-right progression in Figure 9. The configuration on the right neatly partitions the game board into a $3\times 7$ rectangle along the left side and $3\times 4$ rectangle in the lower-right. This “sister” to our central city, while it doesn’t immediately reveal a valid calendar date, provides access to several new date configurations. How many new dates can you reach from here? Be sure to document your work, for as Dudeney noted in 1907, “If you succeed in constructing the chessboard, but do not record the arrangement, you will find it just as puzzling the next time you feel disposed to attack it” [1].

Torrence

Figure 9: From left to right: A sequence of moves, from a center configuration to another bountiful place.

Complete One-Window Puzzles

A one-window polyomino puzzle is complete if for every square on the game board there exists a configuration with the window in that position. It is easy to see, for instance, that the three-piece pentomino puzzle on the $4\times 4$ board in Figure 10(a) is complete. (As it happens, these are the only three distinct pentominoes that produce a complete puzzle on this board.) Moreover, it is just as easy to see that given any two configurations of this puzzle, there is a sequence of at most two moves that will transform one to the other. So if this $4\times 4$ structure exists as part of a configuration for A-Puzzle-A-Day (or some other larger puzzle), then it would yield 15 additional connected configurations via moves that only involve these three pieces.

(a)

(b)

(c) Figure 10: Some puzzles where the window can be moved to any position on the game board.

(d)

Activity 5: Complete Sub-Structures

Show that the three-piece pentomino puzzle in Figure 10(b) is complete by finding a configuration for every window position, such that there is a move sequence between any pair of these 16 configurations.

Do the same for the puzzles in Figure 10(c) and 10(d).

Can you find an A-Puzzle-A-Day configuration that incorporates the $4\times 4$ structure from Figure 10(a) to give 16 days in a single month? What month(s) permit this?

Activity 6: January Jackpot

Returning to A-Puzzle-A-Day, verify that there is a move sequence starting from the “sister city” configuration in the rightmost panel of Figure 9 to give the left-to-right progression in Figure 11. Verify that the 28 dates in the second panel and the 29 January dates in the last panel are attainable via additional moves. (You may want to revisit the complete one-window puzzles from Activity 5.)

Show that January 6 and 7 are attainable from a central configuration in four moves.

Congrats—you have now found configurations for every day in January, with each linked via a move sequence to a central configuration!

A New Kind of Play for A-Puzzle-A-Day

Figure 11: From left to right: A fruitful sequence of moves

Hierarchy of Move Types

In defining “moves” for A-Puzzle-A-Day, we are permitted to remove and replace a single composite piece, or to simultaneously remove a pair of composite pieces, and keeping each intact, replace them to form a new configuration. We now consider these two move types independently, calling them 1-swaps in the first case, and 2-swaps in the second.

More generally, given a polyomino puzzle with $n$ pieces, for each $k$ with $1\le k\le n$ , define a $k$ -swap as follows:

From a given a starting configuration, simultaneously remove exactly $k$ composite pieces, and keeping each intact but possibly flipping, rotating, or otherwise reorienting and repositioning them, replace them on the game board to obtain a valid configuration.

Expanding on the notion of a “move” comprising 1- and 2-swaps, there is a natural hierarchy available for how a move could be defined for a particular polyomino puzzle. We could define a move to be just 1-swaps. Or a move could comprise 1- and 2-swaps (as we have defined it for A-Puzzle-A-Day). Or a move could comprise 1- and 2- and 3-swaps. And so on.

At the end of the line, if a move in an $n$ piece puzzle includes all swaps up to $n$ -swaps, then all configurations are connected to one another. For any two configurations are linked by a single move of this type: Remove all $n$ pieces from the starting configuration and put them back in differently, to make the other.

It should be clear that for any $k$ , if moves for a particular puzzle are defined to be all 1-, 2-, …, $k$ -swaps, then moves can be represented as edges in a graph whose vertices are the configurations. As $k$ increases more edges are added to the graph, and the number connected components potentially diminishes, until the extreme case where $k=n$ and the configuration graph is complete (i.e., there is an edge between every pair of configurations). At some point along the way, possibly with k < n , the graph becomes connected.

Activity 7: 1-Swap, 2-Swap, 3-Swap

Revisit a specific move sequence from any of the earlier activities. For all moves in the sequence, determine which are 1-swaps and which are 2-swaps.

Give an example to show that some 2-swap moves can be decomposed as a sequence of 1-swaps. When documenting a move sequence, it is good to keep this in mind. It is possible to structure a move sequence so that 2-swaps are used as sparingly as possible, only when 1-swaps won’t suffice.

Give an example of a 2-swap that cannot be decomposed into a sequence of 1-swaps. You may find it helpful to design a small puzzle (say, with two pieces) to make it clear that for some puzzles it is impossible from a given configuration to reach a second configuration using only 1-swaps, while it is possible using 2-swaps.

This situation can occur in A-Puzzle-A-Day: Consider the configuration shown in Figure 2(a). Confining

Torrence

yourself to 1-swaps only (so for each move you will remove and replace a single composite piece), see how many moves you can make. Convince yourself that you are stuck; using only 1-swaps this configuration cannot be transformed to any central configuration, as it can only reach three other configurations. Now repeat this experiment, but this time your moves may be either 1-swaps or 2-swaps. Show that additional moves are possible now. This demonstrates that the connected components in the configuration graph for A-Puzzle-A-Day generated by 1-swaps alone are not the same as the connected components generated by moves that may be 1-swaps or 2-swaps. The additional edges representing 2-swaps connect what were distinct components in the 1-swap configuration graph.

Finally, starting from a configuration in Figure 8, show that it is possible to make a 3-swap among the three pieces on the left that results in a new configuration, different from both of those shown. (Hint: See Figure 5(b).) Recall that in Activity 3 we found that there are no 2-swaps possible from the starting configurations of Figure 8. So just as 2-swaps can be used to attain configurations that can’t be reached via 1-swaps alone, we now see that 3-swaps can be used to attain configurations that cannot be reached by 1- and 2-swaps. Open question: Under 1-, 2-, and 3-swaps, are all A-Puzzle-A-Day configurations connected?

Summary and Conclusions

You now have experience with the paradigm of making moves to generate new configurations. It is hoped that you will enthusiastically embrace the challenge of expanding the connected solution set documented here to fill out the calendar.

Many open problems exist. How many connected components does the configuration graph have? Can these components be programmatically cataloged?

The experience of manipulating polyomino puzzles by hand, in real time, hones an ability to identify what types of “moves” can make a puzzle both fun and challenging. And regardless of which types of moves are allowed for a particular puzzle, there is a temporal element to this type of play: each move re-configures the board and reveals new possibilities for a potential next move. This mode of play engages with and sharpens our ability to recognize and differentiate patterns and symmetry, important ingredients for appreciating polyomino puzzles in particular, and mathematical artworks in general.

References

[1] H. Dudeney. “The Broken Chessboard.” The Canterbury Puzzles and other Curious Problems, London, Thomas Neslson and Sons Ltd., 2nd ed., 1919, 119-120. https://www.gutenberg.org/files/27635/27635-h/27635-h.htm#Page_119.

[2] S. W. Golomb. Polyominoes: Puzzles, Patterns, Problems, and Packings. Revised 2nd Edition. Princeton University Press, 1994.

[3] W. J. Hansen. “Equivalence Classes Among Pentomino Tilings of the $6\times 10$ Rectangle.” 1991. http://www.cs.cmu.edu/~wjh/papers/hexclass.html.

[4] C. B. Haselgrove and J. Haselgrove. “A Computer Program for Pentominoes.” Eureka, vol. 23, 1960, pp. 16–18. https://www.archim.org.uk/eureka/archive/Eureka-23.pdf.

[5] F. Kadner. “Problem 1681.” The Problemist, Fairy Chess Supplement, vol. 2, no. 10, Feb. 1935, p. 105. https://www.theproblemist.org/mags.pl?type=fcr.

[6] Klee, B. https://resources.wolframcloud.com/FunctionRepository/resources/FindExactCover/.

[7] D. E. Knuth. “Dancing Links.” Millennial Perspectives in Computer Science, 2000, pp. 187–214. https://arxiv.org/abs/cs/0011047.

[8] J. C. P. Miller. “Pentominoes.” Eureka, vol. 23, 1960, pp. 13–15. https://www.archim.org.uk/eureka/archive/Eureka-23.pdf.

594