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.
 A: 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.
A: 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.
