MPMP10 - Avoid the Square

README.md

This puzzle is part of the Matt Parker's Maths Puzzles series.

Avoid the Square

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.

Question

Is there a game that ends in a draw on a 5 x 5 grid?

Solution

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:

1. Are there too many of the given tile on the board already; and
2. 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.

Board.py

class Board:
  def __init__(self, n):
    self.n = n
    self.tiles = [x[:] for x in [[' '] * n] * n]

  def __getitem__(self, point):
    return self.tiles[point.x][point.y]

  def __setitem__(self, point, value):
    self.tiles[point.x][point.y] = value

  def __str__(self):
    result = ' ' + '_' * (self.n * 6 - 1) + ' \n'

    for row in self.tiles:
      result += '|     ' * self.n + '|\n'
      result += ''.join('|  ' + cell + '  ' for cell in row) + '|\n'
      result += '|_____' * self.n + '|\n'
    
    return result

main.py

from itertools import combinations
from Point import Point, formSquare
from Board import Board

def findValid(n):
  """
  Prints the final position of all n x n boards that are a draw and returns the
  total number of different boards that ended in a draw.
  """
  points = []
  avoid = {}
  board = Board(n)
  count = 0
  totalCounters = n * n
  oCounters = totalCounters // 2
  xCounters = totalCounters - oCounters

  for i in range(n * n):
    # the next point
    p = Point(i // n, i % n)
    # if a group of three other points forms a square with p, we should avoid
    # that group.
    groups = filter(lambda x: formSquare(p, *x), combinations(points, 3))
    avoid[p] = set(groups)
    points.append(p)


  def validPlace(target, point):
    # there has to be a member of each group that is different from the target
    # character.
    return all(
      any(
        board[other] != target for other in group
      ) for group in avoid[point]
    )

  def backtrack(x, xLeft, oLeft):
    nonlocal count
    if x == n * n:
      print(board)
      count += 1
      return
    i, j = x // n, x % n
    p = Point(i, j)

    if xLeft != 0 and validPlace('x', p):
      board[p] = 'x'
      backtrack(x + 1, xLeft - 1, oLeft)
    
    if oLeft != 0 and validPlace('o', p):
      board[p] = 'o'
      backtrack(x + 1, xLeft, oLeft - 1)

  # By running the code with negative remaining, we remove the constraint for
  # the number of tokens.
  # backtrack(0, -1, -1)
  backtrack(0, xCounters, oCounters)
  return count

n = int(input('What size board? '))

print(f'There are {findValid(n)} valid games that end in a draw.')

Point.py

from math import sqrt

class Point:
  def __init__(self, x, y):
    self.x = x
    self.y = y

  def __hash__(self):
    return hash((self.x, self.y))

  def __add__(self, other):
    return Point(self.x + other.x, self.y + other.y)

  def __sub__(self, other):
    return Point(self.x - other.x, self.y - other.y)

  def __mul__(self, other):
    return self.x * other.x + self.y * other.y

  def __abs__(self):
    return sqrt(self * self)

  def __lt__(self, other):
    return self * self < other * other

  def __eq__(self, other):
    return self.x == other.x and self.y == other.y

  def __str__(self):
    return f'Point({self.x}, {self.y})'

def formSquare(a: Point, b: Point, c: Point, d: Point) -> bool:
  # We consider the vectors from a to the other points. If the points form a
  # square there will be a single long vector; the diagonal.
  shortA, shortB, diag = sorted([b - a, c - a, d - a], key=abs)

  return (
    # The short sides should be the same length
    abs(shortA) == abs(shortB) and
    # The short sides should be perpendicular
    shortA * shortB == 0 and
    # The short sides should sum to the diagonal
    shortA + shortB == diag
  )