Flats and Steeps

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), Database Tuning: A Principled Approach (Prentice Hall, 1992), and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer Verlag, 1998). He can be contacted at [email protected].

The journalist Cloe Anne Bennet explained, "It's the strangest mathematician story I've ever written. A group of brilliant mathematicians form an association, the Borghese Club, dedicated to mathematical games inspired by the construction techniques of the Renaissance and Antiquity. Each year, they meet in Rome. They walk together through the stone arches and post-and-beam construction of the Imperial Forum; then the two-thousand year old Colosseum built to hold 50,000 spectators and hundreds of animals and gladiators; and finally that jewel of the Renaissance -- the Villa Borghese. Walking among the paintings of Caravaggio and the sculptures of Bernini, they exchange game proposals, until one wins, usually by consensus."

Ecco nodded. "They have invited me several times. But something always comes up: a kidnapping, a trial, a criminal. You know, my normal lot," he said with a smile.

"That's okay," Bennet responded. "This year, the game has come to you. The Borghese Club has invented a series of games based on the principle of columns and beams. They call it 'Flats and Steeps.' It is played on a grid of dots. The president, Maurizio Ferro, sends you the description with his compliments.

"Here is the simplest version called 'Straight Flats and Steeps':

1. There are two players who alternate moves until one player cannot move. The winner is the player who makes the last move.

2. A move of the first player consists of drawing a flat (a horizontal line segment connecting two adjacent dots). A move of the second player consists of drawing a steep (a vertical line segment connecting two vertically adjacent dots). The first player is called 'Flats,' the second 'Steeps.'

3. A player's line segment may not touch a dot touched by a segment previously drawn by his opponent. Nor may a player draw a line segment between two dots that already have a line segment between them.

"Figure 1 shows how a game on a 4×4 grid might evolve.

"Now, the first player (the one playing Flats) has two moves and so does the second player (Steeps). Neither can prevent the other from making those moves. After they are over, Flats will be the first one who can't move and so loses. Here's the first question the Borghese Club poses to you, Ecco: Does either player have a winning strategy on a 4×4 grid?"

Liane entered the fray, "A winning strategy means being able to force a victory, right uncle?"

Ecco nodded. "Right. No matter what the other player does, one player should have a strategy for winning," he responded.

Liane thought about this for some time, "Well, then, I think the first player should be able to win," she said. "The first player's first Flat move should be here."

She drew a line segment between two points of an empty grid.

Reader: Can the first player, in fact, force a victory with the right strategy? If so, how? If not, why not?

Cloe Anne Bennet smiled at the 11-year-old girl. "That was fast," she said. "I'll check whether or not they agree with you. Given your reputation, I suspect they will.

"In the meantime, they have a second variant called 'Articulated Flats and Steeps' that modifies 'Straight Flats and Steeps' in two ways:

1. (Articulation) Each player may draw a line segment in any direction if he or she already has a line segment ' touching one of the endpoints of (it doesn't matter whether that player has another line segment '' touching the other endpoint of ). Thus, the Flats player may make steep moves provided the resulting line segment attaches to at least one dot previously touched by Flats and neither endpoint is touched by a segment of Steeps. The same applies symmetrically for Steeps.

2. (Compensation) To compensate for the disadvantage of going second, Steeps may draw up to one flat line segment anywhere he likes, provided neither endpoint is touched by a segment of Flats.

"Figure 2 illustrates all of this. The moves of Steeps are represented by green dotted lines. Note that Flats makes a steep move in Figure 2(c), and Steeps makes an unattached flat move in Figure 2(d).

"Their question is: Which player can force a win of 'Articulated Flats and Steeps' on a 4×4 grid?"

To my amazement, neither Ecco nor Liane came up with a solution before I left, although Ecco developed a strong conjecture that Steeps had an advantage this time.

Reader: I think this is a tough game to find a winning strategy for, especially as the grid gets large. Since DDJ readers are a very clever lot, I suggest a collective approach to "Articulated Flats and Steeps." If any reader would like to set up a web site that will permit competing Java programs to play or human players to play, the DDJ web page will give pointers to the sites after I check them out. As winning strategies emerge, I will report the results in future columns. Eventually, we may evolve to variants that allow diagonals (Flats, Steeps, and Slopes) and to strategies for multiplayer versions, but for now please let's stay with "Articulated Flats and Steeps" of size 4×4 and larger squares.

Last Month's Solution

Figure 3 illustrates the solution to the June 1999 "Fitting" problem.

Reader Solutions to the "Joints in Space" Problem

The following readers matched or improved upon Dr. Ecco's solution to the "Joints in Space" problem (DDJ, April 1999): Burghart Hoffrichter, Earl Paddon, Pearl Pauling, Jean-Francois Halleux, and Alan E. Dragoo.

Alan's solution was the best I've received so far. Whereas Ecco was able to establish 34 adjacency guarantees, Dragoo's solution was able to establish 15 additional ones. His design involved 5 levels. The first was 4×3 but with three missing blocks. The second was 4×3. The third was 4×3. The fourth was 3×3 with an extra block. The fifth was 5×2 with many gaps (5 blocks in total). Clever guy.

DDJ