Tuesday, December 21, 2010

Permudrome -- Grid Game

Here is a game for 2 players.
The game's name is a combination of the words "permutation" and "palindrome".

where n is a multiple of 4.
I suggest that n is >= 8.

The players take turns. On a turn a player draws two x's into the grid, each x into an empty square such that no column or row has more than one x.

After there is exactly one x in each row and in each column -- n x's total, n/4 moves for each player -- play is over.

Write down the (n-1) absolute values in order, of the changes in the vertical positions of adjacent x's from column to column, along the bottom of the grid.
Write down the (n-1) absolute values in order, of the changes in the horizontal positions of adjacent x's from row to row, along the left side of the grid.

Player 1 gets as a score the length of the largest palindromic subsequence within the sequence of vertical changes written along the bottom of the grid.

Player 2 gets as a score the length of the largest palindromic subsequence within the sequence of horizontal changes written along the left side of the grid.

Largest score wins. (Ties are possible.)

Example: n=12:

. . x . . . . . . . . .
. . . . x . . . . . . .
. . . . . . x . . . . .
x . . . . . . . . . . .
. . . . . x . . . . . .
. . . . . . . x . . . .
. x . . . . . . . . . .
. . . x . . . . . . . .
. . . . . . . . x . . .
. . . . . . . . . . . x
. . . . . . . . . . x .
. . . . . . . . . x . .

Changes in vertical positions column to column:
3,6,7,6,3,2,3,3,3,1,1
The largest palindromic subsequence is (3,6,7,6,3). Player 1 gets 5 points.

Changes in horizontal positions row to row:
2,2,6,5,2,6,2,5,3,1,1,
The largest palindromic subsequence is (5,2,6,2,5). Player 2 gets 5 points.

It is a tie.

What about strategies for this game?

Thanks,
Leroy Quet