Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998), Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992). He can be contacted at [email protected].
Benjamin Baskerhound himself was at our door. Kidnapper of Ecco, stealer of submarines, would-be founder of a colony in Antarctica, Baskerhound had promised the authorities that he would avoid mischief ever since his radical brain surgery and subsequent (in my opinion, ill-advised) presidential pardon.
"I now invent fictional strategy games," he said, paused, his eyes twinkling, "without ulterior motive." He had lost weight since the last time I saw him. He now would have blended into the professional class of any college campus: sports jacket, unruly hair, crooked glasses, and intelligent, bemused eyes. I still saw wickedness behind those eyes, I must confess. "I have invented a game now that I can't solve. It's so easy to explain, I call it 'Simple.'"
I saw Liane rub her hands in delight. Ecco too leaned forward in his chair. In spite of (or because of?) their history together, Ecco seemed comfortable with Baskerhound.
"The game is played on a grid without boundaries," Baskerhound began. "Players -- we'll call them player X and player O -- alternate moves as in tic-tac-toe. Player X goes first. The object is to get four-in-a-row. But the four must be connected either vertically or horizontally. Diagonal foursomes don't count."
"Still, as in tic-tac-toe, the first player has quite an advantage," Liane observed. "Is there any compensating advantage for the second player?"
"Well, yes," said Baskerhound, "But that is where I need your help. To win, player X (the first player) must get four-in-a-row before player O does and player X must win within his first 10 moves. If, after 10 moves of player X, that player has no vertical or horizontal four-in-a-row, then player O wins."
"So, no game can have more than 19 Xs and Os on the page," said Liane, showing off a little.
"You do credit to your uncle Ecco here, young lady," Baskerhound said to Liane. "But the real question is this: Does either side have a winning strategy? If so, is 10 too low a number or doesn't it matter?"
After a few seconds of silence, Liane spoke up. "If only three-in-a-row were necessary, then player X could win in exactly three moves. Here is how:
Player X moves and O moves next to X.
XO
Now, player X moves orthogonally to where O moved:
XO
X
Since X only needs to get three in a row, there is no way for O to stop X."
"Right," said Ecco. "The question of four should bend to the same reasoning. After all, any three-in-a-row with open ends on both sides should force a win. Still, the problem is not trivial at all. We need to think."
Ecco invited Baskerhound and Liane to a table. After an hour of playing on paper and chessboard, with much chuckling and exclamations of surprise, Ecco, Baskerhound, and Liane turned to me with a look of triumph.
"We think we have it," said Liane.
Reader: Does either player have a winning strategy and, if so, what is the strategy? If player X can force a win, then how many moves are needed? If player O can force a win (by preventing player X from winning in 10 moves), then does X ever have a winning strategy?
"But there are some open questions with answers we don't know," Ecco added. "Does the answer change if both players must always--after player X's first move--place a mark that is one square away (either horizontally or vertically) from some other mark? That is, after player X's first move, every new O must be next to some O or X and similarly for every X. What if we allow one square away diagonally too?
"We also have some variants of the game. Can either player be sure to get four-in-a-row more than once? What is the situation if winning requires five-in-a-row?"
I don't know the answers to any of the questions, nor do I know whether my friends -- and Baskerhound, too -- ever figured them out.
Reader: Would you like to have a try?
Last Month's Solution
The data is consistent, thankfully. Figure 1 is one design that works.
Reader Notes on "My Enemy's Enemy"
Nearly all readers who submitted a solution for "My Enemy's Enemy" (DDJ, December 1999) submitted the best possible solution. (Dr. Ecco's published solution was worse, partly because the initial conditions stated numerically were wrong. Group 9 was initially red, but was miscounted as blue.)
First, readers recognized that good solutions required having some groups change alliances twice. (Are border states always fickle?) Next, they saw that nine alliance changes was a minimum. As Alan Dragoo put it: "The five original reds must change once each and two other groups must change twice each, creating and destroying links connecting the reds to each other and/or to the sea in order to avoid having a group surrounded by its enemies."
Finally, they found the following ordering, which should present the minimum difficulty of 309,803.55 for conversion: 10 to red, 6 to red, 20 to blue, 2 to blue, 8 to blue, 9 to blue, 15 to blue, 10 to blue, and 6 to blue.
Readers who achieved this were, in order of submission: Jon Beal, Richard Roy, Greg Smith, Eric W. Biederman, Kevin Ruland, Jason Strickland, James H. Puttick, Rodney & Jialin Meyer, Magne Oestlyngen, Patrick R. Schonfeld, Steve Tether, Pearl Pauling, Larry Holding, Philip Mayfield, Jimmy Hu, Tomas G. Rokicki, Alan Dragoo, and Mark Yendt. Clever people.
DDJ
