# Square Achievement Game on a Grid

Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an n x n grid.
The first player to occupy the vertices of a square with horizontal and vertical sides is the winner. What is the smallest n such that the first player has a winning strategy?

Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.

I believe the first player has a winning strategy for N=7.

In the configuration below (with "o" having the next move), "o" can force a win by making a "cross". Note that the "cross" can also be applied to two non-adjacent "o"s in the same row or column. The first player plays in the center. The second player has 9 unique responses. I'll consider the 3 most interesting responses here.

Below, the first player places the second "o" next to the first, threatening to make a cross. So, the second player has 2 unique moves available. However, both moves allow the first player to force a few moves and achieve the "cross", as illustrated. (The two starting pieces for the "cross" are marked with a square around them.) Another possible position for the initial "x". This is also a win for "o". Another possible position for the initial "x". This is also a win for "o". (I omitted 2 branches to save space, but they follow the same pattern). I didn't consider the other 6 initial moves for "x", but I think the same techniques can be used to solve them.

FWIW, I'm pretty sure N=5 is a draw. I haven't considered N=6, yet.

• Tom, This is a nice argument. When you mentioned N=5 being a possible draw, I had another look at that and I don't quite have it, but it does appear to be a draw. ---Martin
– user7975
Jul 28, 2010 at 12:06

I realised after I wrote the following answer that I probably have interpreted "square" the wrong way. I expected the winner to construct a 2x2 square submatrix formed by their own symbol. Upon re-reading the question, it seems that the question requires the distance between the rows and columns in the submatrix to be the same. Nonetheless, perhaps you might find this of interest, since it answers a related question.

I found that when n>=4 the o's win. First note that permuting the rows and columns of the matrix does not affect the result, nor does taking the matrix transpose. If it's a win for the o's for some n, then it's also a win for n+1, n+2, etc.

In the diagram below, the o's can force the top diagram (up to equivalence), with x to move. x's move is equivalent to one of the diagrams in the second row. Afterwards, o can play a sequence of forcing moves, illustrated in the column (the yellow highlights where x is forced to play). (source: Wayback Machine)

It's fairly easy to see that n=3 will be a draw.

• I believe that in your version of the problem, where the players are trying to form a 2x2 subrgrid in their own symbol, then the game is a draw. The second player can consider the board as tiled in a brick pattern by dominos, and complete each domino that the first player enters. This blocks the 2x2 subgrid pattern. Jun 28, 2010 at 15:39
• @Douglas: what graphic package did you use to produce these neat diagrams? I have been looking precisely for one where it would be easy to do something similar. Thank you. Jul 28, 2010 at 14:18
• Well... I used Excel -- I shrunk the column size, added borders and cell colours to draw these things, then I did a screendump, copy/paste to paintbrush and chop the borders. [yes, it's all a bit hacky] Jul 29, 2010 at 1:02