Cubic tic-tac-toe: A matching-based approach
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916970736123904 |
|---|---|
| author | Cain, John W. Raymond, Ioannis M. Källersjö, Nora C. |
| author_facet | Cain, John W. Raymond, Ioannis M. Källersjö, Nora C. |
| contents | In the natural generalization of tic-tac-toe to an $n \times n \times n$ board where $n \in \mathbb{N}$, it is known that the first player has a winning strategy if $n \leq 4$ and that either player can force a draw if $n \geq 8$. The question of whether the first player has a winning strategy if $n = 5, 6$ or $7$ has remained open. Here, we prove that the first player does not have a winning strategy if $n = 7$. The proof, which is computer-assisted, exploits the fact that the second player's first four moves can always be chosen such that their remaining moves can be automated via a simple pairing strategy. The process of finding the pairing strategy involves reframing the problem in such a way that the goal is to seek a maximal matching in a bipartite graph that represents the tic-tac-toe board after each player has made four moves. We use the Hopcroft-Karp matching algorithm to find such maximal matchings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_21494 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cubic tic-tac-toe: A matching-based approach Cain, John W. Raymond, Ioannis M. Källersjö, Nora C. Combinatorics 05D15, 91A46 In the natural generalization of tic-tac-toe to an $n \times n \times n$ board where $n \in \mathbb{N}$, it is known that the first player has a winning strategy if $n \leq 4$ and that either player can force a draw if $n \geq 8$. The question of whether the first player has a winning strategy if $n = 5, 6$ or $7$ has remained open. Here, we prove that the first player does not have a winning strategy if $n = 7$. The proof, which is computer-assisted, exploits the fact that the second player's first four moves can always be chosen such that their remaining moves can be automated via a simple pairing strategy. The process of finding the pairing strategy involves reframing the problem in such a way that the goal is to seek a maximal matching in a bipartite graph that represents the tic-tac-toe board after each player has made four moves. We use the Hopcroft-Karp matching algorithm to find such maximal matchings. |
| title | Cubic tic-tac-toe: A matching-based approach |
| topic | Combinatorics 05D15, 91A46 |
| url | https://arxiv.org/abs/2509.21494 |