# Harary's generalized Tic-Tac-Toe; Winning strategy for Skinny on a 7 x 7 board?

Disclaimer: The purpose of this post is a ask question, not to offer a puzzle. Still, there are some puzzles here for the reader's pleasure.

Disclaimer 2: This question was also asked on Math Stack Exchange. I gave an answer there which gives some partial progress.

Animal tic-tac-toe was conceived by Frank Harary in 1977. It is like regular tic-tac-toe, except it is played on a $$b\times b$$ board, for some integer $$b$$. Also, instead of trying to get three-in-a-row, both players are trying to make a certain polyomino shape with their marked squares. Any rotation or reflection of the polyomino counts as a win. The players are X and O, with X playing first. Each choice of $$b$$ and each choice of polyomino gives a different game. The five possible tetrominos were given the following cute names by Harary: Using a strategy-stealing argument, you can prove that O cannot win under optimal play. Therefore, the question of interest is: for each polyomino, what is that smallest board size on which X can achieve that polyomino, and in how few moves can he do so?

The following data summarizes the known results for polyominos with three and four cells. I have seen these numbers published in several places, cited at the end. However, I cannot find a winning strategy for Skinny, the $$4\times 1$$ rectangle, on a 7 x 7 board.

Question: Can X achieve a 4 x 1 rectangle on a 7 x 7 board? Remember that diagonals are not allowed. Can it be done in eight moves?

I understand that this is a hard question, and the answer would likely be a relatively complex strategy. I hope that it is actually answerable, since all of the sources below claimed it is true without proof, or the barest sketch of a proof.

Puzzles for the readers enjoyment: Show how X can win for each of the other polyominos, on the given board sizes. Also, prove that X cannot achieve the 2x2 square on any board size.

Polyomino Minimal board size where X wins Minimal number of moves for X to win
Straight Tromino 4 3
Bent Tromino 3 3
Tippy (S Tetromino) 3 5
Elly (L Tetromino) 4 4
Knobby (T Tetromino) 5 4
Fatty (2x2 Square) X cannot win on any board size N/A
Skinny (4x1 rectangle) 7? 8?

Sources that claim that Skinny is achievable on a 7 x 7 in 8 moves, all without proof:

Beck, József (2008), Combinatorial Games: Tic-Tac-Toe Theory, Encyclopedia of Mathematics and its Applications, 114, Cambridge: Cambridge University Press, pp. 60–64, doi https://doi.org/10.1017%2FCBO9780511735202

Gardner, M. (2001). The colossal book of mathematics: Classic puzzles, paradoxes, and problems. W. W. Norton.

Harary, Frank, "Achieving the Skinny Animal," Eureka, No. 42, Summer 1982, pp. 8-14; Errata, No. 43, Easter, 1983, pp. 5-6.

X starts by claiming the center. Up to symmetry, O's response is one of the nine squares below: $$\begin{array}{|c|c|c|c|c|c|c|} \hline &&&&&& \\\hline &&&&&& \\\hline &&&&&& \\\hline &&&X_1&&& \\\hline &&\color{gray}{O_1}&\color{gray}{O_1}&\;\;\;\;&\;\;\;\;&\;\;\; \\\hline &\color{gray}{O_1}&\color{gray}{O_1}&\color{gray}{O_1}&&& \\\hline \color{gray}{O_1}&\color{gray}{O_1}&\color{gray}{O_1}&\color{gray}{O_1}&&& \\\hline \end{array}$$ I have winning strategies for seven of these responses, as shown below: $$\begin{array}{|c|c|c|c|c|c|c|} \hline &&&&&\color{gray}{O_3}& \\\hline &&&X_4&\color{gray}{X_5}&X_3& \\\hline &&&\color{gray}{X_5}&&\color{gray}{O_3}& \\\hline &&\color{gray}{O_2}&X_1&\color{gray}{O_2}&X_2&\color{gray}{O_2} \\\hline &&&&\;\;\;\;&\color{gray}{O_3}&\;\;\; \\\hline &\color{gray}{O_1}&&\color{gray}{O_1}&&& \\\hline \color{gray}{O_1}&\color{gray}{O_1}&&\color{gray}{O_1}&&& \\\hline \end{array}\qquad \begin{array}{|c|c|c|c|c|c|c|} \hline &&\color{gray}{O_3}&&&& \\\hline &&\color{gray}{O_3}&\color{gray}{X_5}&&& \\\hline &&X_3&X_4&\color{gray}{X_5}&& \\\hline &\color{gray}{O_2}&X_2&X_1&\color{gray}{O_2}&& \\\hline &&\color{gray}{O_3}&&&\;\;\;\;&\;\;\; \\\hline &&\color{gray}{O_1}&&&& \\\hline \;\;\;\;&&\color{gray}{O_1}&&&& \\\hline \end{array}$$ 