Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Simple


Mar00: Dr. Ecco's Omniheurist Corner

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


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.