Beguiling Games IV: Scruffle.

We’ll start this installment of Beguiling Games by discussing who has a winning strategy in Splotch!  Recall the rules of the game:  players alternately color in squares in a 4 x 4 grid, with the goal of creating a specified splotch, shown below.  The splotch may be rotated and/or reflected as well.

For a more complete description together with an example of how the game is played, you can look at the previous installment of Beguiling Games.

OK, now for the solution!  It turns out that the second player can always win.  Let’s see how.  I found it easiest to think about a strategy by imagining the grid as being divided into quadrants, like this:

Now here is the important observation:  the first player who fills in a second square in any of the quadrants loses, regardless of whether the squares are adjacent or diagonally situated.  Of course there are other ways to lose, too — as with all these two-player games, there are multiple ways to analyze them.

So let’s get specific.  Suppose the first player colors in square A1 (see the figure below).  The second player then colors in the square labelled B1.

At this point, the red squares indicate all the places the first player cannot play without losing the next turn.  So the first player must color in one of the two empty squares, after which the second player will color in the other one.  So after two turns for each player, the board now looks like this:

So no matter what square the first player colors in next, one of the quadrants will contain two filled-in squares, and so the second player will win on the next move.

A similar strategy may be used no matter where the first player begins.  Consider the first few moves in the following game.  The first player colors in the square A1, and the second player colors in B1.

Again, the first player must avoid the red squares, or else the second player would win on the next turn.  Whichever square the first player colors in next, the second player can always play “two away.”  The result will be 1) the first player will not be able to win on the next turn, and 2) one square in every quadrant will be colored in.  This means that the first player is forced to put a second square in one of the quadrants on the next move, meaning that the second player will win on the turn after that.

This is the simplest strategy I found for the second player.  I would be happy to hear if some reader found an even simpler way to describe a winning strategy!

What about using other splotches?  If the splotch contains too many squares, it is possible to force a draw.  For example, given the splotch below, either player may force a draw simply by coloring in the four corners on their first four moves.

Interestingly, it is difficult to come up with a splotch where the first player has a winning strategy (other than a splotch which is just a single square, of course).  The more squares included in the splotch, the more difficult the analysis.  But for simpler splotches, it seems a clever division of the board allows the second player to win.

For example, consider the following square splotch.

Now divide the board into the following 2 x 1 regions, or dominoes:

Player two has a simple winning strategy.  Whenever the first player fills in a square, the second player fills in the other square of the domino.  It should be clear that the second player can never lose this way.  The first player will eventually have to fill in a square directly above or below a filled-in domino, and when this happens, the second player wins on the next move.

A complete analysis of Splotch! is likely beyond reach.  Just counting the number of possible splotches (up to rotation and reflection) would be a challenging task unless you wrote a computer program to exhaustively find them.  Without rotations and reflections, there are 2¹⁶ = 65,536 possible subsets of 16 squares, and hence 65,535 splotches (since a splotch must include at least one square).  So a computer program would be able to find them all relatively quickly.  The interested reader is welcome to undertake such a task….

Here is another simple two-player game for you to think about, which I call Scruffle.  It is played on a typical 3 x 3 Tic-Tac-Toe grid.  Players alternate playing either a 1, 2, or 3 anywhere in the grid.  A player wins when a number they place creates a column, row, or diagonal which contains a 1, 2, and 3 in any order.

There is one additional constraint:  only three of each number may be placed in the grid.  So once three 1’s (for example) are placed in the grid, no player may place another 1 anywhere in the grid.  This is not an arbitrary constraint — you can show that the game cannot end in a draw with this condition.  See if you can show this!

For the first puzzle, show that the first player has a winning strategy.  This is not difficult; the simplest strategy I found involves the first player’s second turn involving playing the same number they played on the first turn.

A slightly more challenging puzzle is to require the first player to play a different number than the number they played on their first move.  Does the first player still have a winning strategy?  I’ll give you the solution in the next installment of Beguiling Games!