5
$\begingroup$

It is known that, for any tiling of a $6\times6$ rectangle with dominoes, there must exist a fault line, or a line cutting the square without cutting any domino. (There is a nice elementary proof of this fact, which I don't wish to spoil here.)

This suggests a two-player game. Two players alternate placing dominoes on the $6\times6$ board until it is full. If any player places a domino in such a way that the tiling cannot be completed, that move is considered to be illegal. Player 1 wins if the fault line is horizontal; player 2 wins if the fault line is vertical. (If there is both a horizontal and a vertical fault line, it's a tie.) Does either player have a winning strategy? Which one? What about a winning-or-tying strategy?

$\endgroup$
10
  • 1
    $\begingroup$ There are only 6728 domino tilings so this is brute-forceable. $\endgroup$ Aug 3, 2023 at 20:47
  • 1
    $\begingroup$ What have you tried? $\endgroup$ Aug 3, 2023 at 22:16
  • 1
    $\begingroup$ How do the players know when a move is illegal? Do they ask a computer in cases where it's not immediately obvious? $\endgroup$
    – PM 2Ring
    Aug 4, 2023 at 1:36
  • 1
    $\begingroup$ @PM2Ring I think we can assume the players are perfect logicians, for the sake of answering the question. In practice, say a player can "challenge" the other at any time to show that the board is completable; failing a challenge is a loss. $\endgroup$ Aug 4, 2023 at 2:20
  • 2
    $\begingroup$ As a small note, the $4\times 4$ case always ends in a tie - the first player can force a horizontal fault line with their very first move, and all possible first moves have an accompanying second move that forces a vertical fault line. $\endgroup$ Aug 4, 2023 at 20:22

2 Answers 2

5
$\begingroup$

Player 1 has a winning-or-tying strategy. Their first move is as follows (A2 and B2 in chess notation):

enter image description here

Observe that if another horizontal domino is placed in the same row (in any of the three available positions), this will force the existence of a horizontal fault. So Player 1 needs only to cause one more horizontal domino to occur in that row; since Player 2 can't block all three possible followup moves without placing a horizontal domino themselves at (D2, E2), the only way for this to fail is if no such placement extends to a valid tiling.

That is, the only way that Player 2's first move can hope to lead to a win is if all possible extensions of it have vertical dominos on each of C2, D2, E2, and F2. But it's pretty easy to just check by exhaustion that no move has this property. So Player 2 can't win.

(My guess is that the game results in a tie, by e.g. Player 2 doing something very similar along a vertical line someplace far away from wherever Player 1's first move was, but I haven't investigated the game tree enough to prove this.)

$\endgroup$
2
  • 1
    $\begingroup$ I suppose if Player 2 does the same thing but vertically - say, E1/E2, B5/B6, or E5/E6 - then it's a tie. $\endgroup$ Aug 6, 2023 at 19:31
  • $\begingroup$ On second thought, B5/B6 wouldn't work. $\endgroup$ Aug 6, 2023 at 20:51
1
$\begingroup$

I agree with RavenclawPrefect that there isn't a winning strategy for player 2. I suspect that there is a winning strategy for player 1, but if not, they can at least force a tie.

There's a fairly standard heuristic argument that applies to any sufficiently symmetrical two player game. This game is symmetrical because if we rotate the board by a quarter-turn then a winning state for player 1 becomes a winning state for player 2, and vice versa.

Assume there is a winning strategy for player 2. Player 1 makes a potentially useful move somewhere on the board (probably a horizontal move). Thereafter, they follow the player 2 strategy (rotated by a quarter-turn), ignoring their initial piece. If the strategy requires them to make a move that clashes with that initial piece they simply make another arbitrary move. Etc. Hopefully, these arbitrary moves give more benefit to player 1 than to player 2, or are at least neutral, but we can't guarantee that. In this way, player 1 ought to do at least as well as player 2, which contradicts the initial assumption that player 2 has an advantage. But as I said, it's just a heuristic argument, not a rigorous proof.

In the comments, I asked how do the players know when a move is illegal. After playing through several dozen games on a checkered background, I found it's usually pretty easy to see when a move is illegal because it creates a trapped region containing an odd number of empty squares, or a trapped region where the numbers of light & dark squares are unequal. (A set of dominoes must cover equal numbers of light & dark squares on a checkerboard).

In this game, the score is determined purely by the final arrangement of the dominoes. The order that moves are made is irrelevant, and it doesn't matter who places any given domino. When playing through games, I find it helpful to just fill in locations when they become forced. This makes it easier to notice illegal moves. Eg, in RavenclawPrefect's example, a horizontal domino is forced in the bottom left corner (A1B1 in their notation).


I have written some code in JavaScript and Python to help explore this game, which I've placed in a Github Gist. The Gist also contains some statistics related to the game, and several diagrams in SVG format. My code uses zero-based indexing, with the top left corner of the board at (0, 0). I use human-readable SVG to display and save the board images. (The SVG files scale coordinates by 10 to minimise the usage of non-integers).

DominoGridMaker.html makes diagrams for this game, with a simple (colorblind-friendly) palette of 4 colors. You can run this code on SageMathCell, or save it to your machine (or phone) & run it locally offline in your Web browser.

Click on a cell edge to place a domino that straddles that edge. Click a domino to delete it. DominoGridMaker can export the diagram to SVG (and copy it to the clipboard). It can also import diagrams (or partial diagrams) in the same format: just paste the SVG code into the textarea at the bottom of the page and click the Import button. Actually, you don't need to paste the whole SVG, you just need a partial file containing the domino data wrapped in a <g id="cvs"> group. Eg,

<svg xmlns="http://www.w3.org/2000/svg">
<g id="cvs">
<use x="0" y="40" href="#dh" class="c3"/>
<use x="0" y="50" href="#dh" class="c2"/>
</g>
</svg>

places 2 horizontal dominoes in the bottom left corner.

You can also import (and export) other shapes or text.

This program does almost no error checking. In particular, it doesn't prevent overlaps.

I linked an earlier version of this program in the question comments. This version can also import patterns created by the older version.


DominoTiling.py fills a rectangular grid with dominoes, using Knuth's Algorithm X for the exact cover problem. It can detect faultlines, and report on them in various ways. It displays the diagrams in SVG in a format that's compatible with DominoGridMaker, with the same color palette. It was designed to run on the SageMathCell server, but it's mostly pure Python code. It only uses Sage to get the input arguments and to do the SVG display.

DominoTiling.py has two coloring schemes. If you set colors to a pair of numbers in the range (0..3), the first number is used for all horizontal dominoes, the second number is used for all vertical dominoes. But if you set colors to a single integer (usually 4), it uses standard map coloring with that number of colors so no two dominoes which share an edge have the same color. (It uses Algorithm X to determine valid colorings).

You may supply an initial pattern in the init box and DominoTiling will attempt to complete it, or report that it can find no solutions if you give it an illegal pattern. It does not attempt to validate that the input pattern has no overlaps, or lies within the bounds of the board.

For init, you specify dominoes by the x, y coordinates of the top left square and the orientation. Eg, (0, 0, 'v'), puts a vertical domino in the top left corner, and (0, 4, 'h'), gives the horizontal domino in RavenclawPrefect's diagram. Spaces are not significant. The final comma isn't needed when entering multiple dominoes, but it must be given when entering a single domino.

The counts radio buttons select various faultline statistics.
lines prints stats for each faultline position pattern found. Eg, (0, 1) (1, 3) : 30 means there are 30 solutions that have horizontal faultlines in rows 0 & 1 and vertical faultlines in columns 1 & 3.
num_lines counts the total number of horizontal and vertical faultlines. Eg, (1, 2) : 1086 means there are 1086 solutions with 1 horizontal faultline and 2 vertical faultlines.
wins counts the winning solutions for player 1, so 1 gives the number of solutions where player 1 wins, 0 gives the ties, and -1 gives the wins for player 2. The faultline positions are printed at the top of each displayed solution.


Although a full game takes 18 plies (9 turns for each player), most games are fully resolved within 7 or 8 plies. One interesting pattern starts with 3 horizontal dominoes in a diagonal arrangement, eg (0, 5, 'h'), (1, 4, 'h'), (2, 3, 'h'), which are in red in the following diagram. Three move win

After those 3 moves, all the other dominoes are forced! Its faultline position is (0, 4), (), so it's a clear win for player 1. Perhaps it can be the basis for a winning strategy...

$\endgroup$
3
  • $\begingroup$ If you run those scripts on a phone browser, you may want to expand the width of the Sage window, which you can do with this bookmarklet: javascript:(()=>{let%20w=prompt('Width?','130%');if(w)jQuery('.sagecell').css('width',w);})() Place the link in your bookmarks toolbar. $\endgroup$
    – PM 2Ring
    Aug 10, 2023 at 8:08
  • $\begingroup$ I don't think the symmetry argument goes through; the addition of a new domino isn't an unalloyed benefit to Player 1 because it makes some moves inadmissible (since they'll no longer extend to a full tiling). $\endgroup$ Aug 11, 2023 at 0:33
  • $\begingroup$ @RavenclawPrefect Sure, but as I said, it's only a heuristic argument. Those arbitrary moves probably won't help player 1 create a faultine, but they may help to create a tie. IME, it's hard to make useful (legal) moves after 6 or 7 plies. $\endgroup$
    – PM 2Ring
    Aug 11, 2023 at 2:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .