This puzzle is part of the Matt Parker's Maths Puzzles series.
Avoid the Square is a game for two players, played on a grid of squares. Players
take turns placing a counter in the grid and have to avoid creating a square out
of their own counters. For example, in the following game on a 3 x 3 grid, the
player marked by x
must place a counter.
_________________
| | | |
| x | o | x |
|_____|_____|_____|
| | | |
| | | o |
|_____|_____|_____|
| | | |
| | o | x |
|_____|_____|_____|
However, they cannot place a counter in the bottom left square as it would create a square, so they place their counter in the middle.
_________________
| | | |
| x | o | x |
|_____|_____|_____|
| | | |
| | x | o |
|_____|_____|_____|
| | | |
| | o | x |
|_____|_____|_____|
Now the player marked by o
must place a counter, but they cannot place it in
the middle left square, as it would create a square, so they must play in the
bottom left corner.
_________________
| | | |
| x | o | x |
|_____|_____|_____|
| | | |
| | x | o |
|_____|_____|_____|
| | | |
| o | o | x |
|_____|_____|_____|
The final player x
can now place a counter in the last remaining square to
draw the game.
_________________
| | | |
| x | o | x |
|_____|_____|_____|
| | | |
| x | x | o |
|_____|_____|_____|
| | | |
| o | o | x |
|_____|_____|_____|
The grid is now completely filled with counters and no four counters form a square.
Is there a game that ends in a draw on a 5 x 5 grid?
If there was such a game, then there would be 13 x
tokens and 12 o
tokens on
the final board. A naiive solution would be to check every single board and
check if it avoids creating any squares of x
or o
. There are 25 choose 13
(5200300) boards, and for each board there would be 13 choose 4 (715) possible
x
squares and 12 choose 4 (495) possible o
squares to check.
This is not ideal however, as if there is a square of tokens in a given board, then there will be many other boards that we will check containing the exact same square (the square being fixed and the others free gives 21 choose 9 = 293930 boards with the same square!) which is a big waste of time. Instead of checking all boards, we can instead start with an empty board, and attempt to put the counters on the board one by one using a programming paradigm known as backtracking. When we are at a space on the board, we can attempt to place a certain tile checking two things:
- Are there too many of the given tile on the board already; and
- Does the new counter form a square with any of the the other similar tokens already on the board.
The first condition is calculated easily enough, by keeping a count of how many counters of each type remain and decreasing the count when using a counter. The second condition could be implemented naiively by checking each group of three similar counters on the board and seeing if they form a square with the new counter. A better solution would be checking the areas of the board that form squares with the current tile position and making sure they have at least one different counter.
With this code we can seen that the number of solution for an n * n grid are as follows:
n | Number of Solutions |
---|---|
1 | 1 |
2 | 6 |
3 | 92 |
4 | 2094 |
5 | 2704 |
6 | 24 |
7 | 0 |
8 | 0 |
The number of solutions here is slightly inflated, as reflections and rotations of a given board are also counted.
Both 7 x 7 and 8 x 8 boards have 0 solutions. We can take away the first
condition that we must have half x
and o
tokens, but are still no solutions.
Thus there are no games that end in a draw on an n x n grid where n is greater
than or equal to 7.