Permudrome -- Grid Game

[Leroy Quet]

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

Start with an n-by-n grid,
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

[Leroy Quet]

Should I tell you why I have players draw 2 x's at a time, instead of
just one x? Or should I leave the question why as a simple puzzle?

Thanks,
Leroy Quet

[Leroy Quet]

I might as well answer this. If you must place just one x each move,
and n is even, then player 2 can match every move by player 1. If
player 1 places an x at (a,b), then player 2 could just place an x at
(b,a) every time or at (n+1-a,n+1-b) every time or at (n+1-b,n+1-a)
every time, at least until the last couple moves. If player 2 always
matches player b, this guarantees a tie. Otherwise the game just comes
down to the last few moves only. -- not much strategy is required. If
n is odd, then player 1 can place an x in the middle square, then
match player 2's moves thereafter. However, if players play two x's at
a time, and player 1, say, is detecting player 2 matching his moves,
then player 2 can place an x at (a,b) and (n+1-a,c), c not equal to n
+1-b, say, if, say, player 2 was placing an x at (n+1-a,n+1-b) at
every x placed at (a,b) by player 1.

By the way, here is my blog of my games. There are like 130 games
there now.
http://gamesconceived.blogspot.com/

Thanks,
Leroy Quet

[Leroy Quet]

Should be: However, if players play two x's at

a time, and player 1, say, is detecting player 2 matching his moves,

then player ONE can place an x..."