## The Game Of Halma

"An admirable place for playing halma," said Chelifer, as they entered the Teatro Metastasio.

—Aldous Huxley, Those Barren Leaves

Two new families of puzzles based on a long-neglected counter-moving game have recently come to light. Each family offers a series of unsolved problems and the opportunity to devise ingenious proofs that some solutions are impossible. The puzzles stem from Dialogue on Puzzles, a splendid collection of unusual problems by Kobon Fujimura and Michio Matsuda published in 1971 in Japan. (Unfortunately the book is not available in English.) Fujimura has translated the puzzle books of Sam Loyd and Henry Ernest Dudeney into Japanese and is the author of several delightful books that contain his own original puzzles. The two new counter-moving puzzles are derived from one problem created by Matsuda.

Matsuda's problem exploits the simple rules of a popular late-19th-century British proprietary game called Halma, after the Greek word for leap. The game was invented in 1883 by George Howard Monks, a 30-year-old Harvard Medical School graduate who was then pursuing advanced studies in London. He later became a prominent Boston surgeon. Halma is still played in Britain but, although it was issued here in 1938 by Parker Brothers, it has never caught on in this country.

The traditional Halma board has 16 cells on a side [see Figure 65]. If two players are competing, each begins by placing his 19 counters in a section called a "yard." There are two yards,

 r" . ¡r L______ î____ 1 f:r •

The Halma board

The Halma board one at the top left corner of the board and the other at the bottom right corner. The counters are identical except that the two sets are of contrasting colors. The goal is to occupy the opposing player's yard, and the first player to move all his counters into the opposite yard is the winner. Two kinds of moves are allowed:

(1) A "step." This is a move, like the move of a chess king, to any one of the eight adjoining cells.

(2) A "hop." This is a leap over another counter, as in checkers, except that the leap may be made in any direction, orthogonal or diagonal. The jumped piece is not removed.

A connected chain of hops counts as a single move. It is not compulsory to make a hop. A player may continue a chain of jumps as long as possible or stop wherever he pleases. The color of a jumped piece does not matter; a chain of jumps may be a mixture of friendly and enemy counters. Steps and hops may not, however, be combined in the same move. Players alternate turns, moving one counter at a time.

Halma can also be played by four people, with each player having 13 counters. The yards are at the four corners of the board behind the boundaries indicated by the broken lines in the illustration. The four-player game can be each man for himself, with each seeking to reach the diagonally opposite yard, or pairs of opposite (or adjacent) players can be partners who help each other, and the first pair to yard all 26 of their counters is the winner. Halma strategy is so complex, however, that the game is best when only two people play.

Of many later games based on Halma the two most popular in the United States have been Camelot and Chinese checkers, both of which appeared on the market in the 1930's. Camelot was a revival (with minor changes) by Parker Brothers of a late-19th-century Parker game called Chivalry. Chinese checkers, which has no connection whatever with China, is played on a hexagonal-cell board that is usually shaped like a six-pointed star. The hexagonal tessellation allows steps and hops in only six directions. A French version of Halma, known as Grasshopper, can be played on a standard checkerboard [see Figure 66]. It is an excellent game.

Figure 66

Figure 66

Grasshopper

To prevent a stubborn player in games of the Halma type from forcing a draw by keeping a man permanently in his own yard it is wise to add extra rules. Sidney Sackson, the New York City game inventor and game collector, suggests the following. If a counter can leave its own yard by jumping an enemy counter, or by a chain of jumps that starts with a leap over an enemy counter, it must do so, although once out of the yard it may stop jumping at any desired spot. After a counter has left its yard it may not rest in the yard again, although it may hop across it.

The Halma problem devised by Matsuda for the Japanese chessboard, which has nine cells on a side, begins with nine counters in a square array at the board's lower left corner. How few moves of the Halma type, Matsuda asked himself, are needed to transfer the nine counters to the same formation at

chapter 11

the upper right corner? He found a solution in 17 moves, but this was reduced to 16 moves [see Figure 67] by H. Ajisawa and T. Maruyama. The 16-move solution is believed to be minimum.

Figure 67

 1 ; - • • - • • • 4 - • i-

::

1

...

-

5

/

i

 • • t • • • •/ • • • ) • Cm3^ • ) • • ! 1 ' ' . ..

• •

•J

---

• •

• •

Solution to Matsuda's problem on the Japanese chessboard

When I saw this elegant solution, I at once began tackling the same problem on the Western chessboard with eight cells on a side and on smaller square boards with seven and six cells on a side. In each case, a square of 3 x 3 counters is diagonally shifted to the opposite corner. Using the technique of first establishing a diagonal ladder—a basic strategy, by the way, of all games of the Halma type—the best I could achieve was 15 for the chessboard, 13 for the order-7 and 12 for the order-6. I have been unable to prove that any of these are minimum solutions. It is not hard to show that at least 12 moves are necessary for the order-8 square, 10 for the order-7 and 11 for the order-6.

Next I experimented with a similar transfer of the nine-counter square, on the same three boards, to the lower right corner instead of the corner diagonally opposite. The order-6 board has many solutions in nine moves, one of which is shown in Figure 68. Nine is obviously minimal because each counter must move once. (It is necessary that at least one counter hop to and from the fourth row on its way to the other yard, consequently nine-move solutions cannot be achieved on a three-by-six board.) On the order-7 board 10 moves will do it. This too is readily seen to be minimal since the first piece to move must move at least once again to reach the adjacent yard.

Figure 68

 • • Si • • • •
 • • • • • •
 • • • « K I • • • •

Orthogonal transfer on an order-6 board

Thirteen moves will solve the problem on the order-8 board. That 12 are necessary is evident from a simple parity check. The six counters in column 1 and column 3 can hop only to column 7, therefore three of the six must each make at least one step move. I tried vainly for weeks to find a 12-move solution until Donald E. Knuth, a mathematician at Stanford University, came to my rescue by devising a proof of impossibility in 12 moves. It is too involved to give here, but it is based on the necessity for one of the original four corner counters to step to a different color, the fact that the reverse of a solution is another solution and other considerations. Readers may enjoy searching for minimum solutions to the six transfer problems.

The second family of puzzles suggested by Matsuda's problem is based on removing every jumped counter from the board. The goal is to remove all counters but one, the last counter reaching a specified cell, and do it in a minimum number of Halma moves. Such problems are similar to those of the classic peg-solitaire game discussed in an earlier column (reprinted in my book Unexpected Hanging and Other Mathematical Diversions) except that the greater freedom of movement allows for much shorter solutions, and proofs of minimum solutions are usually much more difficult.

Consider, for example, the puzzle on a five-square board that was first issued in 1908 by Sam Loyd [see Figure 69, No. 1]. He labeled each counter with the name of a hopeful in that year's presidential election. The idea was to eliminate eight men, leaving one's favorite on the center cell. Loyd allowed Halma moves but did not count a chain of jumps as being one move. Eight jumps are clearly minimal and there are many such solutions for each counter. Henry Ernest Dudeney, in his Amusements in Mathematics (Problem 229), improved the puzzle by disallowing step moves, counting jump chains as single moves and allowing any counter to end at the center. He gave a four-move solution that is surely minimal, although I know of no proof. Counter 5 jumps 8, 9, 3, 1; counter 7 jumps 4; 6 jumps 2 and 7; then 5 returns to its original cell by leaping 6.

Figure 69

Six Halma solitaire problems

Let us combine the rules of the two rival puzzlists by allowing both steps and hops, as in Halma, and counting a chain of hops as one move. Each hopped counter is of course removed. Can the reader find one of the many three-move solutions that leave the last counter on the center cell? The solution is an elegant one that begins with two step moves and ends with an eight-jump chain.

Similar problems are shown in the same illustration, numbered 2 through 6. The second is to be solved in three Halma moves, the surviving counter on the cell initially occupied by the counter at the top of the triangle. The third problem is to be solved in three moves, last counter on the board's center cell. The fourth problem is to be solved in a minimum number of moves, last counter on the cell initially occupied by counter 6, the triangle's center. The fifth problem is to be solved in three moves, surviving counter at the board's center. The last problem, the most difficult of the six, calls for three moves that end with the lone counter on one of the board's four center cells.

The field of Halma puzzles is so unexplored that it is a challenge to devise and solve new puzzles, then see if one can prove by simple arguments that the solution actually is minimal. I have not the slightest notion, for example, how few moves are required on an order-7 board with 25 counters in a square array in the center to leave the last counter on the center cell. I have avoided trying this problem for fear of accomplishing no other work for the next month or so.

0 0