Tatami Maker: A Combinatorially Rich Mechanical Game Board

Year: 2013 Authors: Alejandro Erickson

Core claim

Tatami Maker makes tatami covering constraints physically playable and reveals that simple local rules generate rich, visually appealing combinatorial behavior.

Topics

tatami tilings, mechanical puzzle design, combinatorial game boards, enumerative combinatorics, puzzle games

Domains

combinatorics, enumerative combinatorics, tiling theory, graphical puzzle constraints, game design, interactive installation, 3D printing, physical puzzle artifact

Methods

rectilinear grid coverings, mechanical constraint enforcement, prototype fabrication, game rule design

Media

dominoes, monominoes, desktop 3D printer, modular board pieces

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.

Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture

Tatami Maker: A Combinatorially Rich Mechanical Game Board

Alejandro Erickson Department of Computer Science, University of Victoria, V8W 3P6, Canada alejandro.erickson@gmail.com

Abstract

Japanese tatami mats are often arranged so that no four mats meet. This local restriction imposes a rich combinatorial structure when applied to monomino-domino coverings of rectilinear grids. We describe a modular, mechanical game board, prototyped with a desktop 3D printer, that enforces this restriction, and transforms tatami pen-and-paper puzzles into game board puzzles. We review some recent mathematical discoveries on tatami coverings and present five new combinatorial games implemented on the game board.

Introduction

Tatami mats are a common floor furnishing, originating in aristocratic Japan, during the Heian period (794-1185). These thick mats, once hand-made with a rice straw core and a soft, woven rush straw exterior, are now machine-produced in a variety of materials, and are available in mass-market stores. They are so integral to Japanese culture, that a standard sized mat is the unit of measurement in many architectural applications (see [7]).

Here we depart considerably from traditional layouts, but we retain two essential features. The first of these is aspect ratio; a full mat is a $1\times 2$ domino, and a half mat is $1\times 1$ monomino. The second is the 17th century rule for creating auspicious arrangements; no four mats may meet.

Counting domino coverings is a classic area of enumerative combinatorics and theoretical computer science, but little attention has been paid to problems where the local interactions of the dominoes are restricted in some fashion. The tatami restriction is perhaps the most natural of these, and it imposes a visually appealing structure with nice combinatorial properties (see Figure 1). It is the subject of exercise 7.1.4.215 in Volume 4 of “The Art of Computer Programming” (see [8]), where Knuth reprints a diagram of a 17th century Japanese mathematician, and recently the tatami restriction has been studied in several research papers (see [1, 3-6, 9]). We present a mechanical game board which gives a popular appeal to this mathematically rich topic, even making some of it accessible to children.

Figure 1: A tatami domino covering, generated in software using a logical satisfiability formula.

Many popular games, such as chess and checkers, are also the subject of mathematical research, but we attempt the reverse; to create a game with popular appeal, from mathematical research.

Perhaps the prior work that is most closely related to ours is Scott Snibbe’s Boundary Functions (see [10]). Participants on the floor of the installation become points in a Voronoi diagram that is projected onto the floor from the ceiling. That is, lines are projected to form a 2-dimensional cell around each

Erickson

participant. As more participants enter the installation and move around, the installation reveals more about the nature of Voronoi diagrams. The Voronoi diagram is a topic in higher mathematics which Snibbe converts to an inviting, aesthetically appealing, and self explanatory activity.

On paper, a tatami puzzle is comprised of a grid and some instructions. The player must internalize the tatami restriction, and apply it every time she draws a tile. The structure of a tatami covering is not obvious to the uninformed, and applying the local restriction can overwhelm the player’s efforts to solve the puzzle. Furthermore, the appearance of the pen-and-paper puzzle depends on the player’s artistic ability and care, which can negate the natural beauty of tatami coverings.

A mechanical game board that enforces the tatami restriction eliminates the preoccupation with “no four tiles meet”. The uninformed player engages with the game board configuration using trial and error and thereby learns the restriction intuitively. At the end she is rewarded with a completed tatami covering.

We describe the structure of tatami coverings and a prototype game board called Tatami Maker, which realizes all of the combinatorial properties of tatami coverings. We review some of these properties, in order to generate mathematical interest, and we introduce five puzzle games that are playable on the game board.

Tatami Maker, as compared with Snibbe’s work, is our attempt to convert the higher mathematics of tatami coverings, into an inviting, aesthetically appealing, and self explanatory activity.

Structure

We introduce the tatami structure with an interactive demonstration. Take a pencil and complete the partial covering in Figure 2(a). Once again, no four mats may meet at any point; in other words, every interior intersection of the grid will contact the midpoint of a broad edge of a domino. You should find the completion is unique and equivalent to Figure 2(b).

Completing the exercise will inevitably bring about the discovery of the ray, which occurs wherever a vertical domino shares an edge with a horizontal domino. The tatami restriction forces the pattern to repeat itself until it reaches the boundary of the grid.

(a)

(b) Figure 2: Attempt to complete the partial tatami coverings by placing tiles which are forced by the tatami restriction. (a), A partial covering and, (b), its unique completion. (b), This covering contains every possible type of feature. (c), This partial covering cannot be completed.

(c)

The tiles in the partial covering in Figure 2(c) are incompatible because the tatami restriction forces the propagation of rays that cross paths. I invite the reader to check.

Tatami coverings have the remarkable property that a simple local restriction imposes an aesthetically appealing, combinatorial structure. We discovered the ray in Figure 2, and a case analysis of how rays begin reveals that in a rectangular covering, there are only four distinct ray-producing features, up to reflection and rotation. These four features and their rays are shown in Figure 3 (see [5]). A natural brick laying pattern fills the areas between the features and rays with either horizontal or vertical dominoes.

We conjecture that the following lemma, proved for rectangular grids in [5], also holds for general rectilinear regions (with and without holes).

Tatami Maker: A Combinatorially Rich Mechanical Game Board

Figure 3: Tatami coverings of rectangular grids are comprised of these four types of feature and the bond pattern.

Lemma 1 ([5]). A tatami covering of a rectangular grid is uniquely determined by the tiles touching its boundary.

By Lemma 1 the amount information required to describe a tatami covering of a rectangle is proportional to its perimeter, rather than its area. The result is that a randomly chosen tatami covering has an inevitable simplicity that is harmonious, not only in its construction, but also in its appearance. In spite of this, the structure described here is not obvious to the uninformed, and building an intuition for it can take considerable effort.

Tatami Maker: a combinatorially rich mechanical game board

The Tatami Maker game board forms a rectilinear grid that enforces the tatami restriction when it is covered by the accompanying tile pieces. Arbitrary rectilinear grids can be created by placing Tatami Maker’s modules alongside each other (see Figure 4(a)). A simple mechanism is embedded at each grid line intersection, which obstructs the placement of a tile if the other three incident grid squares are covered (see Figure 4(b)).

(a) Tatami Maker modules are placed alongside each other to create larger grids.

(b) The inside of Tatami Maker’s intersection mechanism. Each arm of the X-shape extends to a different grid square. Figure 4: Tatami Maker modules and mechanism.

A tile piece covers one or two grid squares, and the underside of each of its four corners has the specially shaped foot shown in Figure 5(b). The feet interact with the mechanism in the game board by pushing an obstructing ball onto an unoccupied grid square, as well as guiding the tile correctly onto the grid.

Each mechanism occupies one grid intersection, which consists of one quadrant from each of four incident grid squares. A cavity in the game board contains a ball which may travel freely to any unoccupied quadrant. If a quadrant is occupied by a tile’s corner, then one of tile’s feet occupies the part of the cavity that is otherwise available to the ball. When three of the quadrants are occupied by tile corners, the ball is forced to occupy the remaining quadrant, thereby preventing a tile corner from being placed here.

A minimal game board module is one grid intersection. As a result, the dimensions of a module are

Erickson

given in terms of its intersections rather than its grid squares. Our prototype’s modules are $4\times 4$ , but they need not be square, or even rectangular.

(a)

(b) Figure 5: (a), Grid intersections and several Tatami Maker modules. (b), The feet of a tile piece.

The main design challenge is ensuring that the ball can be pushed by an incoming foot, unobstructed, to an available quadrant. We label the quadrants Q1, Q2, Q3, and Q4, in counterclockwise order. A critical case occurs when Q2 and Q4 are occupied by tile corners (and feet), and a tile foot placed in Q1 must push the ball to Q3. Intuitively, the ball must disturb the feet in Q2 and Q4 on the way to Q3, otherwise the midpoint of the intersection would accommodate the ball when all four quadrants are occupied. The mechanism is designed, therefore, so that the ball lifts the tiles in Q2 and Q4 as it passes to Q3, and so that it will not become stuck against another part of the mechanism before it arrives in Q3.

The availability of desktop 3D printers has lowered the cost of creating prototypes sufficiently that rough estimation, and iterative trial and error was the most economical way of solving these design challenges. Tatami Maker was prototyped with a Solidoodle 2 printer; the printer is a 3D CNC machine that extrudes a filament of hot ABS plastic into a $15\times 15\times 15$ cm print area to create real-life versions of virtual 3D models. With each iteration of the prototype, changes to the shape of the cavity and the feet of the tile pieces were made to tease out the required behaviour of the mechanism.

Tatami Maker was tested informally at Science World in Vancouver (see Figure 6).

(a) Figure 6: Science World in Vancouver, Canada, December 2012.

(b)

Five tatami puzzles

We describe how to set up five combinatorial puzzle games for Tatami Maker, and highlight some related mathematical discoveries. The first four are for a single player, and the last one is for two players.

Tatami Maker: A Combinatorially Rich Mechanical Game Board

Oku From the Japanese word for “put”, the most straightforward puzzle requires that the player cover a rectilinear region with tiles. Every instance can be solved with the brick laying pattern, but in practice most players try other configurations, and the errors they make are visually manifested in the game board (see Figure 7). Oku offers more experimental freedom than the games described below, making it particularly instructive of the tatami constraint.

Figure 7: Tatami Maker modules lie under an overlay. The two raised monominoes are obstructed by Tatami Maker’s mechanism.

Some of the nicest combinatorial results for Oku are on square grids. The numbers of coverings for various parameters have simple representations, and divide up into natural equivalence classes (see [6]).

Theorem 1 ([5,6]). If $n$ and $m$ satisfy the obvious parity constraints, the number of tatami coverings of the $n\times n$ grid with $m$ monominoes is

• $m{2}^m+(m+1)2^{m+1}$ when m < n ,
• $n{2}^{n-1}$ when $m=n$ ; and
• 0 when m > n .

A mathematically significant subset of the $n\times n$ coverings are those with $m=n$ and a specific number of vertical dominoes. An algorithm was found to generate these in [3], and Figure 8 shows its output for the $8\times 8$ board. Thus we have the solutions to a restricted version of Oku which involves finding a covering of the square grid using a precise set of tiles, differentiating vertical and horizontal dominoes by colour.

Figure 8: All $8\times 8$ coverings with 7 vertical dominoes.

Tomoku Originally conceived by Martin Matamala (private communication), Tomoku is a contraction of the words tomography, and the above game, Oku. This puzzle is played on a rectangular board, and the player is given the row and column projection of a set of solutions, any one of which the player must find to complete the puzzle.

Tomoku is defined as a decision problem, where one must determine whether or not a solution exists. In practice, it is more interesting to reconstruct a covering when the answer is yes, than it is to solve the following decision problem.

Erickson

(a)

(b) Figure 9: (a) Typical setup for an instance of Tomoku. (b) Monominoes are double stacked in solution, because they appear in both a column and a row.

Problem 1. Given an $r\times c$ grid, and a triple of integers, $(v,h,m)$ , for each row and each column, denoting the number of grid squares covered by vertical dominoes, horizontal dominoes, and monominoes, determine whether or not a covering exists with these row and column projections.

It is not known whether an efficient (i.e. polynomial time) algorithm exists to solve an instance of Problem 1. It is known that there are pairs of coverings with the same row and column projection. For example, an $n\times n$ covering with a central clockwise vortex gives the same row and column projections as a counterclockwise vortex.

An instance of Tomoku is set up by arranging Tatami Maker modules under an overlay which is printed with instructions and masks the modules to expose only the required grid (see Figure 9). For a given row, $(v,h,m)$ is represented graphically by the numbers of monominoes and horizontal dominoes that the row contains, omitting the number of vertical dominoes. This is equivalent to the corresponding triple. A similar graphic, interchanging vertical and horizontal, is used for each column (see Figure 10).

Set up the game board with the Tatami Maker Modules and this Overlay Figure 10: Instructions printed on the Tomoku overlay for the instance in Figure 9(a). This particular configuration can be completed without backtracking.

Cover the game board with this many tiles in each row and column. Double stack the square tiles!

Tomoku may be played with pencil and paper. Two examples reprinted from “Tomoku! 80 challenging puzzles” (see [2]) are given in Figure 11. Considerable efficiency can be achieved by using short line segments to represent dominoes, and dots to represent monominoes.

The Lazy Paver The Lazy Paver is tasked with tatami covering a rectilinear driveway with pavers. She would typically produce a $1\times 1$ paver by cutting a $1\times 2$ paver in half, so instead, she will avoid the extra work by covering the driveway only with domino pavers.

The Lazy Paver is also defined as a decision problem.

Tatami Maker: A Combinatorially Rich Mechanical Game Board

(a)

(b)

Figure 11: Instances of Tomoku, reprinted from [2]. The $5\times 12$ puzzle is quite challenging. (a) Figure 12: Lazy Paver instance and instructions printed on an overlay.

(b)

Problem 2 ([5]). Determine whether or not a given rectilinear region can be tatami covered with dominoes (and no monominoes).

The Lazy Paver problem is known to be NP-complete (see [3]). That is, Problem 2 is as difficult to solve, in terms of the number of corners in the input region, as any other of the most difficult decision problems in the class of those whose answers can be checked efficiently, i.e., in polynomial time.

Once again, we set up the game as a covering problem, rather than a decision problem, by placing an overlay on top of the Tatami Maker modules. The overlay has a rectilinear region cut out of it, as well as the instruction to cover the region with dominoes. A prototypical version and instructions appear in Figure 12.

The Paving Consultant Dr. Matt DeVos communicated this decision problem, which is also playable as a covering game.

Problem 3. Determine whether a partial covering of a given rectilinear region can be completed.

A Paver, perhaps a lazy one, has abandoned her job, and left a partially paved region. The Paving Consultant must decide whether the covering can be completed. The puzzle can be set up with overlays, as above, bearing a diagram of the partial covering and indications on how to arrange the Tatami Maker modules. Tiles of a different colour can be provided so that the player does not mix these up with the tiles that are part of the solution (see Figure 13).

Noku Noku is an adversarial game, perhaps antithetical to Oku, proposed by Frank Ruskey (private communication). Players alternately place tiles onto the game board in order to win by forcing a position where

Erickson

(a)

(b) Figure 13: (a), A non-solvable instance of the Paving Consultant. (b), Placing more tiles hints at why this is so.

their opponent has no available move. A computer analysis of some of Noku’s smallest game trees reveals that Player 2 can force a win on the $2\times 6$ grid, but the first player wins for other similarly small cases, including $4\times 3$ and $4\times 4$ .

Acknowledgements Thanks to Prof. Frank Ruskey for continued support and to the referees for valuable comments.

References

[1] Artiom Alhazov, Kenichi Morita, and Chuzo Iwamoto. A note on tatami tilings. In Proceedings of the 2009 LA Winter Symposium (Mathematical Foundation of Algorithms and Computer Science), volume 1691, pages 1-7, 2010. [2] Alejandro Erickson. Tomoku! 80 challenging puzzles. Self Published, Victoria, Canada, Jan. 2012. [3] Alejandro Erickson and Frank Ruskey. Domino tatami covering is NP-complete. 12 pages, submitted, 2013. [4] Alejandro Erickson and Frank Ruskey. Enumerating maximal tatami mat coverings of square grids with $v$ vertical dominoes. In preparation. http://arxiv.org/abs/1304.0070, 2013. [5] Alejandro Erickson, Frank Ruskey, Mark Schurch, and Jennifer Woodcock. Monomer-dimer tatami tilings of rectangular regions. The Electronic Journal of Combinatorics, 18(1):24, 2011. [6] Alejandro Erickson and Mark Schurch. Monomer-dimer tatami tilings of square regions. Journal of Discrete Algorithms, 16(0):258-269, October 2012. [7] Watanabe Hiroshi. Entry for tatami, Kodansha encyclopedia of Japan, volume 7. Kodansha International/USA Ltd., New York, NY, 1st edition, 1983. [8] Donald E. Knuth. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley Professional, 1st edition, January 2011. [9] Frank Ruskey and Jennifer Woodcock. Counting fixed-height tatami tilings. The Electronic Journal of Combinatorics, 16:20, October 2009. [10] Scott Snibbe. Boundary functions. http://www.snibbe.com/projects/interactive/boundaryfunctions/, 1998.