7 replies to this topic

[bonanova]

A king tours an nxn chessboard without visiting a square twice. Your opponent begins by placing the king in any corner. Thereafter, you and she alternate making legal moves of the king. A player loses when there is no previously unoccupied square available for a move.

For what n do you have a winning strategy?

Is there an n for which you have a winning strategy in the modified case where your opponent can make any move on her turn, while you are constrained to make legal king moves only?

[Prime]

Spoiler for For starters

One square was occupied by King's starting position. Thus after your move an even number of squares have been used, after her move -- an odd. In the absence of traps, you must win where n is even, and she -- where it is odd.
On a 2x2 board there is no time to build a trap. So you must win, regardless how she jumps.
A trap would be an isolated area of the board with odd number of unused squares inside, into which you have no choice but going on your move.
On 3x3 board you shall lose in either case.
A 4x4 and higher seems more complex.

[bonanova]

Spoiler for For starters

One square was occupied by King's starting position. Thus after your move an even number of squares have been used, after her move -- an odd. In the absence of traps, you must win where n is even, and she -- where it is odd.
On a 2x2 board there is no time to build a trap. So you must win, regardless how she jumps.
A trap would be an isolated area of the board with odd number of unused squares inside, into which you have no choice but going on your move.
On 3x3 board you shall lose in either case.
A 4x4 and higher seems more complex.

OK so far. How about n=8?

[TimeSpaceLightForce]

This is like a Tron game with diagonals. Nice to play. The strategy is get in the middle first.

[Prime]

I can’t find any simple formal description for the strategy. It appears, for an even “n” - you win; for an odd - she does.

Spoiler for Diagram

Whoever steps into an isolated territory with even number of squares - must lose the game. (I am afraid, I mistakenly, stated the opposite in my previous post.)
Since she makes the first move, you must win on any 2n x 2n board and lose on (2n - 1) x (2n - 1) (for integer n > 0) board.
For the losing side, the only hope to change fortune is to cut off a territory with an odd number of squares and step into it. However, since the two sides take turns to make their move, you cannot do both cutting and stepping into an odd territory. And whenever you split an even number territory into two or more with your move, you take one square from that territory, making total number of squares odd, thus necessitating at least one bordering odd territory, into which your opponent can step.

On the diagram the odd numbers show her moves, and even numbers - yours. At the position on the diagram, she could split the board into 7 and 48 by moving king to B8, 5 and 50 by A7, 4 and 51 by A6. In all those cases you want to step into the odd territory by moving the King to A8, A6, and A7 correspondingly.
If she moves A8, C8, or C7; your responses could be B8, C7, and C8 correspondingly splitting the board into 6 and 48;  8 and 46;  8 and 46; leaving her with the choice of only even territories. Finally, if she goes to C6, the board is wide open and in your favor.

It seems, with an even n, she can only win with your cooperation. (Sometimes it’s a wise choice.)

Interesting question is: with an even n, can she have a winning strategy in the modified version, where she can jump the King to any available square?

[Prime]

And then you must watch out for traps

Spoiler for a trap

Where your move into the odd territory happens to split that territory into two.

After the 11th move on the diagram, she has the winning position.

 

[k-man]

And then you must watch out for traps

Spoiler for a trap

Where your move into the odd territory happens to split that territory into two.

Kingmoves2.gif

After the 11th move on the diagram, she has the winning position.

Not really. Your next move is A6 and she loses.

[Prime]

 

 

And then you must watch out for traps

Spoiler for a trap

Where your move into the odd territory happens to split that territory into two.

Kingmoves2.gif

After the 11th move on the diagram, she has the winning position.

Not really. Your next move is A6 and she loses.

True. My mistake.

Perhaps, the following could be thought of as a trap, though it's a stretch

Spoiler for a trap?

Of course, 12) KC5 was a blunder. Could go 12) KB6. And the whole thing could have been avoided by 8), Kb6.

For any even n, you must win.