Harary's generalized tic-tac-toe

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Harary's generalized tic-tac-toe is a generalization of the game tic-tac-toe, defining the game as a race to complete a particular polyomino on a square grid of varying size, rather than being limited to "in a row" constructions. It was devised by Frank Harary in March 1977, and is a broader definition than that of an m,n,k-game.

Harary's generalization does not include tic-tac-toe itself, as diagonal constructions are not considered a win.[citation needed]

Like many other two-player games, strategy stealing means that the second player can never win. All that is left to study is to determine whether the first player can win, on what board sizes he may do so, and in how many moves it will take.


Square boards

Let b be the smallest size square board on which the first player can win, and let m be the smallest number of moves in which the first player can force a win, assuming perfect play by both sides.

  • monomino: b = 1, m = 1
  • domino: b = 2, m = 2
  • straight tromino: b = 4, m = 3
  • L-tromino: b = 3, m = 3
  • square-tetromino: The first player cannot win
  • straight-tetromino: b = 7, m = 8
  • T-tetromino: b = 5, m = 4
  • Z-tetromino: b = 3, m = 5
  • L-tetromino: b = 4, m = 4


  • Gardner, Martin. The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems: Number Theory, Algebra, Geometry, Probability, Topology, Game Theory, Infinity, and Other Topics of Recreational Mathematics. 1st ed. New York: W. W. Norton & Company, 2001. 286-311.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Harary%27s_generalized_tic-tac-toe&oldid=818949921"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Harary's_generalized_tic-tac-toe
This page is based on the copyrighted Wikipedia article "Harary's generalized tic-tac-toe"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA