Communications of the ACM
Last byte
Open Field Tic-Tac-Toe
In the spirit of Gomoku, two people play a version of the classic paper-and-pencil game tic-tac-toe but on an infinite checkerboard. In it, a player wins by getting four pieces in a row—vertically, horizontally, or diagonally.
Warm-up. Can the first player—blue—force a win in seven turns or less, where a turn consists of both blue and red placing pieces.
Solution to warm-up. The first player can force a win in five turns. Blue moves. No matter where red moves, blue can, in the second move, have two in a row.
Red must now respond to prevent blue from having three in a row that is open on both ends. So R blocks, giving us something like
Blue can now force a two-by-two fork with
No matter where red goes, blue can force an open-ended vertical or horizontal line with three blues, as in
So... now that we know how it works, let us try it for some other problems.
Suppose we have a board with a nine-by-nine grid with the following configuration, and red is about to take the next turn. Can either side force a win?
Solution. Yes, red can force a win. Red threatens...
Blue then red then blue...
Red continues to threaten...
Blue responds...
Red now gets three in a row...
Upstart. Suppose the board is a six-by-six grid with a red exactly in every corner? Blue moves first. There is no limit on the number of turns. Can either side force a win?
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2017 ACM, Inc.
No entries found