Let $N$ be an odd integer. Let us consider a grid from which we cut out a connected shape consisting of $N$ squares. This shape will be our board. By connected, I mean that given any two squares in the board, there must be a path within the board consisting of a succession of adjacent squares going from one to the other.
Two players A and B play the following game. For the first turn, one player removes a square from the board. Then, the other player must remove another square that is adjacent to the previous one. The game goes on like this until one player can not remove any square. The player who removed the last square is the winner.
We assume that player A goes first. Is there always a winning strategy for one of the player ?
Because it's a finite game without any draws, for a given board there must always be a winning strategy for one of the player. After testing on multiple examples, it looks like it is always player A who wins. Intuitively, I can understand such a winning strategy when the board has the shape of a tree.
However, it looks much more complicated to make out a general strategy especially for boards with "cycles". For instance, boards which are $3\times n$ rectangles (with $n$ odd) or boards which look like a doughnut. Yet, on any of these I could not come up with a board where player B could win.
On a sidenote, in order for B to win, because the number $N$ of squares is odd it is necessary to "cut the board" into multiple pieces during the game. Indeed, if $B$ wins then only an even number of squares would have been removed ; which would be impossible if the board remained connected throughout the whole game.
Any hint/suggestion concerning this problem would be appreciated. Also, if this game has a name or has been studied before I'd be interested to know (I couldn't find anything online).
Best Answer
Your question is a special case of this one, and the answer there proves that $A$ wins on all connected regions with an odd number of squares.
A winning strategy is to consider a partial domino tiling of the region which has the most dominos out of all such partial tilings. $A$'s first move will be to remove any square not covered by a domino. Whenever $B$ removes one square of a domino, $A$ responds by removing the other. You can show that the maximality of the partial domino tiling implies that $B$ can never remove a square which is not covered by a domino, so $A$ can always apply this strategy, and is never without a move.
The same proof applies to any region with an even number of squares which cannot be completely tiled by dominos. If the region can be completely tiled by dominos, then $B$ wins with a similar strategy.