Play randomly until each connected component becomes small (<= 10 possible moves). After that, compute grundy function of each component in O(2^n), and xor values for all components. With high probability, result will be non-zero.

One of the solutions involves only trivial observations, but a fair bit of coding.

When we have a game position, it can be partitioned into independent regions where moves can be made. Two possible moves are immediately dependent when they share at least one cell.

We will recognize three classes of regions based on two boolean outcomes.

1. Is it possible to invalidate all possible moves in the region by a single move?

2. Is it possible to make a move such that there remains at least one possible move from the region?

An example of (1) but not (2) is a square of 2 × 2 or 3 × 3 cells. Such a region (a Type I region) requires exactly one move to disappear.

An example of both (1) and (2) is a rectangle of 2 × 4 or 3 × 4 cells. In such a region (a Type II region), we have a choice: it requires either one or two moves to disappear.

An example of (2) but not (1) is any large region. Such a region (a Type III region) requires at least two moves to disappear.

Our first goal will be to have only Type I and Type II regions left on the board. We can try to achieve a perfect grid of Type II regions (4 × 2 rectangles) by trying to place every square of the pattern shown on the left picture. Of course, Felix will mess things up, and the resulting board will look more like the right picture (result of a 16 × 20 game up to this point).

There are 8 Type I regions, 8 Type II regions and 2 Type III regions on the right picture.

In the second part of the game, we eliminate all Type III regions by detecting them and making random moves in these regions.

In the endgame, we have only X Type I regions and Y Type II regions.

• If X and Y are even, the player who makes a move loses if both play optimal: the winning strategy for the other player is to keep them both even after their turn. If we find Sophia in such position, we can make a random move and hope Felix does not follow the winning strategy.

• If X is even and Y is odd, we make by eliminating one Type II region, so that both are even after our turn.

• If X is odd and Y is even, we remove one Type I region just the same.

• Finally, if X and Y are both odd, we move in a Type II region such that it leaves a new Type I region, effectively making the new values of X and Y even: X increases by one and Y decreases by one.

The more Type II regions we had at the beginning, the more are our chances to eventually avoid the situation when X and Y are even and Sophia has to make a move. If we avoid that at least once before the game is over, we follow the above simple strategy to win.

The above strategy is a simple case of calculating and using Grundy numbers for regions, as in winger's solution: they are 1 for Type I regions and 2 for Type II regions. Still, this solution requires only knowledge of elementary game theory and invention of simple symmetric strategies.

When checked several times against the judges' test cases with different random seeds, it won at least 293 out of 300 games.