Quadratis Puzzles

Year: 2022 Authors: Mario Gutiérrez; Hugo Parlier; Paul Turner

Core claim

Quadratis puzzles connect geometry and topology to solvable configuration graphs that can be explored through visualization and play.

Topics

reconfiguration puzzles, square-tiled surfaces, configuration graphs, visualization

Domains

geometry, topology, graph theory, combinatorics, puzzle design, visualization, interactive media

Methods

square pasting, move graph construction, configuration enumeration, visual exploration

Media

square tiles, colored configurations, website quadratis.app

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 2022 Conference Proceedings

Quadratis Puzzles

Mario Gutiérrez${}^1$, Hugo Parlier${}^2$ and Paul Turner${}^3$

${}^1$Mixed Reality Group, Logitech Europe; mgutierrez1@logitech.com ${}^2$Department of Mathematics, University of Luxembourg; hugo.parlier@uni.lu ${}^3$Section de mathématiques, University of Geneva; paul.turner@unige.ch

Abstract

We introduce a family of reconfiguration puzzles arising from ideas in geometry and topology. We present their construction from square-tiled shapes, discuss some of the underlying mathematics and describe how they are naturally associated to puzzle spaces which can be explored through visualization.

Introduction

There is a historic relationship between reconfiguration puzzles, such as the 15 puzzle or the Rubik’s cube, and mathematics. In particular, there are many so-called “sliding puzzles” where pieces slide around a board (see for instance [4] for a collection of examples). In another direction, Weeks [11] took standard puzzles and transferred them onto a torus.

In this paper we discuss a new family, Quadratis puzzles, which are inspired by topological and geometric constructions of surfaces. These puzzles also come with an associated “space” of possible configurations, that can be studied and even visualized. In contrast, the so-called Rubik’s graph was studied for decades, resulting in a computation of its diameter [6, 5], but which is very far from being visualizable. The reader can also directly experience the puzzles for themselves by playing them [10].

The mathematics behind the puzzles

Defining puzzles

To define a puzzle we must first describe what is meant by a board and a color scheme. A board is constructed by pasting together (unit) squares: we assemble collection of $N$ squares, each with upper, lower, left and right edges, by pasting the edges together in such a way so that each left edge is pasted to a right edge, and each upper edge is pasted to a lower edge. This results in an orientable surface tiled by squares (see discussion below). In practice, we often begin with a square-tiled shape that lives in the Euclidean plane, such as the one shown in Figure 1a.

The non-pasted edges are then paired following the left-right or upper-lower conventions. One possible pasting of Figure 1a is shown in Figure 1b (for left-right paring) and 1c (for upper-lower).

Given a square-tiled shape, there is an “obvious” way to paste the remaining sides together. Taking each horizontal line in turn, paste the first (ordering from left to right) free left side to the first available free right side on the same line. A similar procedure can be used to paste upper sides to lower sides in the same column. We’ll refer to this pasting scheme as the standard pasting. In Figure 2a and Figure 2b we see the standard pastings of two different square-tiled shapes. Figure 1b and 1c present pasting that is not the standard pasting.

The squares of a board will be colored from a fixed palette with a predetermined number of squares of each given color. We refer to this information as a color scheme. Formally, though this is unnecessary for this article, we have a positive integer $K\le N$ together with a $K$-tuple $(n_1,n_2,\dots ,n_K)$ such that ${\sum }_{n_i}=N$.

Gutiérrez, Parlier, and Turner

(a) A square-tiled shape

(b) Left-right pasting

(c) Upper-lower pasting

(a)

Figure 1 (b) Figure 2: Two square-tiled shapes and their standard pastings

Note that a color scheme does not determine how to color each square of a board, only the number of each color we must have.

Given a color scheme a particular coloring of a board (of which there are many) will be referred to as a configuration. In Figure 3 we see five different configurations of the board in Figure 2b with the color scheme requiring 1 pink square, 4 blue squares and 4 purple squares.

Figure 3: Five of the possible 630 configurations with the given color scheme

To make a puzzle out of a board and a color scheme, we introduce a dynamic element, via moves which transform one configuration into another. A single square on a board always has 4 (not necessarily distinct) neighboring squares: the ones above, below, to the right and to the left. “Pushing” a given square upwards, will have a knock-on effect on its upstairs neighbor, pushing it upwards as well. This in turn pushes its neighbor and so on and so forth until we end up back where we started. A coherent collection of squares are all displaced by one step upwards. A similar thing is seen if we push downwards, or to the left or to the right. We refer to these as moves. Figure 4 illustrates a left to right horizontal move involving all squares of the middle row. This can be effected by “pushing” any square in that row towards the right. The reader is

Quadratis Puzzles

encouraged to visit [10] to try this out for themselves.

Figure 4: Making a move

Out of all of this we may now make a puzzle. Choose a particular configuration as the home configuration: the aim will be to reproduce this configuration. Starting with the home configuration we can apply a number of random moves (in any direction) to obtain a new configuration. We refer to this as shuffling. The goal is to put the squares back into the home configuration, by using the moves described above. No distinction is made between two squares of the same color: if two squares of the same color are swapped in the process of solving, we do not care, the puzzle is still considered solved. Note that if a puzzle was shuffled using $m$ moves, it is entirely possible that it can be solved with fewer than $m$ moves. Pretty quickly, players tend to want to find the optimal number of moves to solve a puzzle, which brings us to the main mathematical object associated to a board equipped with a color scheme: its puzzle space.

The configuration spaces of puzzles

The puzzle space of a puzzle is a graph whose vertices are configurations and where two configurations are related by an edge if they can be related by a single move. We are only interested in configurations that can in principle be solved, so we simply ignore the other configurations. This amounts to only considering the component of the graph of all configurations which contains the puzzle home configuration. Thus, by definition, a puzzle space is a connected graph.

One could instead consider all possible colorings of a board with a prescribed set of colors, and then relate configurations as above. The graph obtained this way won’t always be connected, and in fact determining the number and size of components seems to be an interesting problem. In [1], there is an elementary proof of the fact that a standard 3 by 3 torus (see Figure 2 (a)) with all squares colored differently is disconnected.

In Figure 5 we see a simple example which can be worked out by hand. The board is a two-by-two square with the standard pasting, and we color the squares with two colors and two squares of each color. Any of the 6 configurations shown may be used as the home configuration.

As the complexity of the puzzle increases, the graphs become more complicated and enjoy richer geometries. For instance, Figure 6a is the graph for a three-by-three square board with standard pasting and two colors, 3 of one color and 6 of the other. As all configurations are related by moves in this example, the choice of home configuration is again unimportant. The figure represents one of many possible planar representations of the graph, and was obtained using standard graph visualisation software (Gephi) and a force-directed graph layout algorithm.

Relationships to moduli theory

By standard surface topology techniques the pasting procedure described above results in an orientable surface equipped with a decomposition into squares. In the examples shown in Figure 1 and Figure 2, the underlying surface is connected, but that is not necessarily a requirement. Interestingly, one can show that if one randomly pastes the squares together, the result is often connected. In fact, the probability of obtaining

Gutiérrez, Parlier, and Turner

Figure 5: A simple puzzle space

(a) Figure 6: Puzzles spaces display intriguing features

(b)

Quadratis Puzzles

a connected surface goes to 1 as the number of squares goes to infinity [9, 8].

The board given by Figure 2b is a genus 2 surface (so topologically a double-torus). This can be shown by a standard Euler characteristic computation and the classification of surfaces. By using the Euler characteristic again, it can be proved that the board from Figure 1 is a genus 6 surface.

Beyond the topology and the combinatorics of the decomposition into squares, the boards are surfaces with a geometric structure. In fact, they are important objects in the theory of moduli spaces, and are generally called square-tiled translation surfaces. (The word “translation” comes from the fact that side identifications are made by Euclidean translations.) These surfaces have all sorts of interesting properties, including being dense in the space of all translation surfaces (up to scaling). Some of them are quite exotic and have fascinating dynamical and geometric properties [7] and there has been a lot of research about square-tiled and translation surfaces in general, a partial survey can be found in [3]. As an example, a very natural question is: how many square-tiled translation surfaces can be made with $N$ squares? It turns out to be very difficult and is related to computing volumes of moduli space (see [2] for partial results). In general the answer is not known, making the question of enumerating the number of possible puzzle boards with a given number of squares, an open and difficult problem.

For these reasons, the puzzle spaces we introduce above can be seen as “toy” moduli spaces, and can be studied using a similar approach. How many vertices are there? How do you determine the distance between two configurations? More generally, what do these spaces “look” like?

These questions, as for moduli spaces, can range from specific to more general, from elementary to more sophisticated. For instance, what are their diameters? Whereas a very limited number of small examples can be worked out, finding a general answer to this type of question very quickly turns into serious and seemingly difficult research questions.

Visualizing puzzle spaces

There are two desirable properties we might ask of a puzzle, namely that it is interesting and visualizable. These are rather loose concepts: interesting means non-trivial yet doable in the sense that a player can, with some thought, develop strategies which help to provide a solution; visualizable means that the puzzle space is of a size that may be displayed so that the vertices and edges remain discernible. These two constraints pull in different directions with increasing interest often resulting in graphs that are too large.

The first examples: chroma-squares

A particularly simple class of puzzles was introduced in [1] under the name chroma-squares: the board is a square $N\times N$ array and the color scheme has $N$ colors with $N$ squares of each. The pasting is the standard one, meaning the underlying surface is a torus.

Figure 7: Five of the approximately $2.7\times 10^{24}$ configurations of size $6\times 6$ , images from [1]

There are some rather obvious choices to make for home configurations, namely lines or columns of uniform color. With essentially no mathematical background it is possible to explain that any two

Gutiérrez, Parlier, and Turner

configurations can be linked by a sequence of moves (see [1]), which shows that the graph of all configurations is connected.

With 1680 vertices and around 10,000 edges, the case $N=3$ yields a puzzle that is both interesting and visualizable. For $N=2$ the puzzle is too trivial and the graph too simple (it is given in Figure 5 above) and for N > 3 the graph is too large (although the difficulty of solving the puzzle does not really increase).

Beyond tori

As we saw above, the underlying surface of a puzzle is an orientable surface. Higher genus examples also give a rich source of interesting and visualizable puzzle spaces. Recall that the board shown in Figure 2b has genus two. With color scheme indicated in Figure 3 it is a relatively easy puzzle (for any chosen home configuration), but not completely trivial, and it possesses a visualizable puzzle graph as shown in Figure 6b.

Exploring large puzzles

While many puzzles are both interesting and visualizable, sometimes we may want to partially visualize a configuration space of a puzzle complicated enough so the entire space is beyond visualization (either for computational or presentational reasons). The puzzle shown in Figure 8b (in which the board is a $5\times 5$ grid missing its middle square) is interesting because the usual strategies do not resolve a potential problem of switching at the end. There is something new here, which means it is worth retaining as an example despite its large configuration space (which has over 3000 billion billion points, roughly the number of square millimeters needed to cover the entirety of the Grand Duchy of Luxembourg).

(a) Exploratis installation at the Luxembourg Science Center Figure 8

(b) A puzzle which is too big to be explored entirely

One solution is to dynamically develop the graph as the player walks through different configurations: if a new configuration is reached, add it to the graph along with the edge used to reach it. This is the basis of the Science Museum installation Exploratis developed in conjunction with the Luxembourg Science Center in which an iPad driven puzzle is linked to a large screen displaying an ever larger portion of the configuration space (see Figure 8a). Here again, a type of repulsion based algorithm is used to visualize the graph. Players can play individually, race or collaborate. This time, because the graph changes with every move, the visuals have a wow-effect. A similar installation was made available to visitors of the Luxembourg Pavilion at the World Expo in Dubai. Hundreds of visitors each day were able to test the puzzles and explore the graphs. In each case, the puzzles are tailored for the event. While many of the puzzles that we use are the same as the one in the available app, we can create new puzzles, such as one representing the flag of Luxembourg for the pavilion, for special installations.

Quadratis Puzzles

(a)

(b)

(c) Figure 9: Exploratis installation at Expo Dubai (Luxembourg Pavilion)

Conclusion

Although only recently made public, we have already had several opportunities to test the Quadratis puzzles with a variety of different player profiles, and we get continual feedback from the Science Center. Something that was not obvious to us at first, and that required a lot of testing, is that the puzzles can be scaled in difficulty, ranging from completely obvious to (apparently) beyond the reach of human capability (and with basically everything in between). By careful planning, a sequence of puzzles can be presented that allows players of any level to learn as they progress. The lessons learnt, along with tricks and techniques uncovered through play, can be subsequently applied to increasingly challenging situations.

So why is this interesting? The puzzles can be appreciated without any scientific background, and yet the surrounding mathematics gives a player a glimpse at what it is like to explore unchartered mathematical territory. In light of the feedback we’ve received so far, we see this is a starting point for a multi-faceted adventure. What is particularly exciting is to see the diversity of players (background, origin, age…) that have experienced the joy of simply playing these puzzles. As we create more and more puzzles, we are ourselves discovering new and interesting phenomena. The exploration of the mathematics, particularly the study of the associated graphs, has only just started. In a different direction, it would be fascinating to know more about what and how players learn while progressing though a sequence of puzzles.

Quadratis puzzles are regarded as simple fun by some, but the fact that they can be used to illustrate mathematics and the nature of mathematical research remains, for us, a central motivation.

Acknowledgements

This article is part of a more general long standing project aiming to illustrate mathematical research in different ways, and we’ve received a lot of support along the way.

The original Mathema project was co-financed by the Swiss National Science Foundation and by TomBooks. In particular, we thank Thomas Steinmann for his personal support.

The exhibitions where we have presented Quadratis and Exploratis are brought alive by mediators so many thanks to all of you who have participated in science festivals. There are too many of you to name, but a particular thank you goes to Bruno Teheux. Not only was he co-organiser of many of the events but his feedback and encouragement has been invaluable. More generally, the University of Luxembourg, and in particular the Department of Mathematics of the Faculty of Science, Technology and Medicine, has provided logistical and financial aid. Thank you in particular to Giovanni Peccati. We also thank Sorbonne Abu Dhabi and the University of Geneva for help with certain exhibitions and to the Luxembourg Pavilion at the Expo

in Dubai for hosting us.

The Exploratis station had the support of many partners. First of all, thank you to the Luxembourg Science Center for hosting us, and to Julien Meyer for his help in making this vision a reality. Exploratis was supported by a PSP Classic grant from the Luxembourg National Science Foundation, who has also supported the project indirectly in many ways (Researchers’ Days and Science Festivals). Exploratis was also co-developed with Reyna Juárez who went far and beyond the call of duty.

References

• [1] Hugo Parlier and Paul Turner, Mathema, TomBooks, 2015.
• [2] A. Eskin and A. Okounkov. Asymptotics of numbers of branched coverings of a torus and volumes of moduli spaces of holomorphic differentials. Invent. Math. 145 (2001), no. 1, 59–103.
• [3] G. Forni and C. Matheus. Introduction to Teichmüller theory and its applications to dynamics of interval exchange transformations, flows on surfaces and billiards. J. Mod. Dyn. 8 (2014), no. 3–4, 271–436.
• [4] E. Hordern. Sliding Piece Puzzles. Oxford University Press, 1986.
• [5] E. Demaine, M. Demaine, S. Eisenstat, A. Lubiw, A.Winslow. Algorithms for solving Rubik’s cubes. Algorithms – ESA 2011, 689–700, Lecture Notes in Comput. Sci., 6942, Springer, Heidelberg, 2011.
• [6] T. Rokicki, H. Kociemba, M. Davidson and J. Dethridge. The diameter of the Rubik’s cube group is twenty. SIAM J. Discrete Math. 27 (2013), no. 2, 1082–1105.
• [7] G. Schmithüsen. Examples for Veech groups of origamis. The geometry of Riemann surfaces and abelian varieties, 193–206, Contemp. Math., 397, Amer. Math. Soc., Providence, RI, 2006.
• [8] S. Shrestha, J. Wang. The topology and geometry of random square-tiled surfaces, arxiv preprint, 2020.
• [9] S. Shrestha, J. Wang. Statistics of Square-tiled Surfaces: Symmetry and Short Loops, arxiv preprint, 2019.
• [10] The website quadratis.app with puzzles and links to downloads.
• [11] J. Weeks. Torus games. Available on the AppStore, 2011.