21626_Hi-Q

Hi-Q is a popular solitaire game that comes in a small box with a playing board that has little holes in the shape of a cross and 32 little pegs that fit into the holes. Starting with the centermost hole open, players move the pegs by jumping one peg over another, either in a horizontal or vertical direction and removing each peg that is jumped over. Diagonal jumps are not allowed. The object for players is to remove as many pegs from the board as possible. This problem involves writing a program that will automatically play Hi-Q so that we can investigate how the game might unfold based on various opening arrangements of pegs.

There is a peg board with the following shape and with holes numbered from 1 to 33 as follows:

1         2         3
4         5         6
 7         8         9        10        11        12        13
14        15        16        17        18        19        20
21        22        23        24        25        26        27
28        29        30
31        32        33

An instance of the game begins with some holes having pegs in them and the rest of the holes being empty. The game proceeds by jumping one peg over another, either horizontally or vertically, with the peg that is jumping landing in an empty hole, and the peg being jumped over being removed from the board. For example, if 9 is empty and 10 and 11 are not, then the peg in 11 can be "moved" to 9 with the peg in 10 being removed. After this move, 10 and 11 would both be empty but 9 would have a peg in it.

Given a specific board configuration your program will pick and model a specific move, over and over, until no more moves are available. Your program will then report the sum of the holes that still have pegs in them. At any point during the game there may be more than one possible move available. In such a case always model the move with the target hole of the moving peg as large as possible. If there is more than one move available to the largest possible target hole, then choose from those moves the one with the larger source hole.

For example, if the board looks like this, with X representing a peg and O representing a hole:

O         O         O
O         O         O
O         O         O         X         O         X         O
O         O         O         X         O         X         O
O         O         O         O         X         O         O
O         O         O
O         O         O

then the following jumps would be made: 1: from 12 over 19 to 26 (26, 24, and 5 are the only possible targets and 26 is the largest), 2: from 26 to 24 over 25 (5 and 24 are the only possible targets with 24 > 5 plus 24 is the target for two possible moves, one from 26 and one from 10; the one from 26 is used since 26 > 10), 3: from 17 to 29 (29 > 5), and two pegs would be left, one in hole 10 and one in hole 29. Thus 39 would be reported as the result for this instance.

NOTE: The above paragraph is wrong. This was discovered shortly after the contest began, and the correction was broadcast to all teams. The second jump should be from 25 to 27. The third jump should be from 10 to 24. The two pegs left will be in holes 24 and 27 and 51 should be reported as the result.

The first line contains an integer N between 1 and 10 describing how many instances of the game are represented. The remaining lines will describe N instances of the game by listing the holes which begin with pegs in them, in increasing order. A 0 will indicate the end of each sequence of unique numbers between 1 and 33 that represents an instance of the game.

There should be N+2 lines of output. The first line of output will read HI Q OUTPUT. There will then be one line of output for each instance of the game, reporting the sum of the holes that still have pegs in them for the final configuration of that instance.. The final line of output should read END OF OUTPUT.

4
10 12 17 19 25 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 0

HI Q OUTPUT
51
0
561
98
END OF OUTPUT