On 15 May 1998 14:37:22 /dev/joe posted:
[As a reminder and also for who were not around when this was originally posted, in Lines of Action there are two colors of pieces, and each piece may move in any orthogonal or diagonal direction a number of spaces equal to the total number of pieces in that row, provided that it does not jump over any pieces of the other color, and that it does not land on a piece of the same color. Moves where a piece lands on another piece of the same color are captures, which is irrelevant for the treasure except in the knowledge that it is allowed.]
Purely trial and error, and process of elimination, with a little creativity thrown in on the side.
My initial observation was that the diagonal rows across the corners are one of the hard things to fill. The extreme corner squares are fine either way, but the rows with 2 squares must either be totally filled or totally empty, and the rows of 3 squares must either have 2 like-colored pieces on the ends or two oppositely-colored pieces adjacent to each other, or have all 3 squares filled. Also, I thought it might be easier to get under 32 pieces if you left some rows and columns entirely empty, since each (orthogonal) row or column that is not empty must contain at least 3 pieces for a bare minimum of 24. As a result, the first case I explored was the one where all the edge squares are empty; the 3-diagonals then require that the corners of the inner 6x6 square are also empty, and the 4-diagonals must either be empty or have two oppositely-colored pieces on the middle squares. The result was a 32-square section which could be filled entirely such that no piece could move, I suspect at least one other player found a solution of this type:
........ 8 ..oxxo.. 7 .xoooxx. 6 .oxxooo. 5 .oooxxo. 4 .xxooox. 3 ..oxxo.. 2 ........ 1 abcdefgh
My early work was confined to exploring all the possibilities within this smaller grid. Quickly, I noted that each of the outer rows of 4 pieces (between the empty corners of the 6x6) could either be full or have one interior piece missing; if any of these was entirely empty, they would *all* have to be empty, and this quickly resulted in showing the entire grid must be empty. The end result of this work was the horribly asymmetrical 25-piece grid shown below.
........ 8 ..o.xo.. 7 .x.ooox. 6 ..o.xxo. 5 .ox..ox. 4 .xoox.x. 3 ..oxxo.. 2 ........ 1 abcdefgh
I continued my work by proving many things about boards with particular lines open, noting that to beat this solution, a grid with no lines open must have exactly 3 pieces in every row and column. In particular, I proved that no board could beat the 25-piece one for a variety of configurations of empty rows and columns.
While working on an unrelated area, a brainstorm hit me and I discovered the following, nicely symmetrical 24-piece solution, which proved to be my best:
........ 8 ..x.o.x. 7 .o.o.o.o 6 ..x.o.x. 5 .x.x.x.x 4 ..x.o.x. 3 .o.o.o.o 2 ..x.o.x. 1 abcdefgh
I did very little work toward completing my proof that this was minimal after finding this, despite that fact that it made the proof much easier -- now I could ignore the cases that did not have at least one empty row and one empty column, because those cases must have at least 24 pieces. I had less time to work on this for a short while after finding the above solution, and later I devoted the time to other things.
24 pieces (with 12 of each color) is a notable milestone because it is the number of pieces players actually start with in Lines of Action. However, since there is no move *out* of this configuration, there is also no move *into* the configuration without having more pieces on the board; all non-captures are reversible moves if the same player was to get another move. Some variant games allow for some situations (possibly as the game is starting) when players have some off-board pieces they are allowed to drop onto the board during their turn; in such games, the board above may represent a possible way for the game to end in a situation where neither player can move. This is relevant because it is uncertain whether or not Lines of Action, by the standard rules, can ever end in a draw; one has never been found, but it is also not proven that one cannot exist, and a solution to this treasure with fewer pieces than mine above would have represented a possible draw by inability to move.
/dev/joe