I have been stuck at this problem for a while.

In this problem, there is a rectangular grid where some of the cells are blocked and others are empty. Player 1 can pick any cell to start the game. After that, the second player will be able to pick any adjacent cell of the last picked cell in his move, which has not been picked before. And then the game will continue in this way. The player who cannot pick any cell in his move will lose. We need to know if the first player can win if both play optimally.

This is actually a bipartite matching problem

Can you please explain a bit more ? How can we convert this problem to BPM?

First convert the board into a bipartite graph. Let's define a "turn" in this game as: Player 1 move and then player 2 move

In turn 1: Player 1 can choose any vertex he wants in this bipartite graph, and then player 2 must choose another vertex adjacent to this vertex

Turn 2: Player 1 must choose a vertex adjacent to the last vertex chosen by player 2 in turn 1, then player 2 again choose a vertex adjacent to the one chosen by player 1

Notice that each time a turn is completed, an edge is chosen, and the edge created by different turn is

vertex-disjoint(doesn't share a common vertex), which means this game is actually simulated by repeatedly choosing a matching in this graph. If player 2 can move, it means that a new matching can still be created in this graph. (Try to simulate the sample test case on paper if it's hard to visualize).What do the two sets of the bipartite graph denote?

They denote squares on the board. Color the board like a chessboard, then one color is the left set of the bipartite graph and the other color is the right set. Player 1 can choose 1 color to play on the board, and he can only play in that color. Equivalently, player 1 chooses one of the left/right set in the bipartite graph, and the other player play as the other set

Lets solve a more general problem where you are given a bipartite graph. Player 2 picks a vertex for player 1 to start with , now they alternate turns , within each turn , a player must choose a neighbouring unvisited vertex to go to , game ends when a player can't make a move.

Suppose this graph has a perfect matching , who will win?

Turns out , Player 1 always has a winning strategy irrespective of what start node is chosen by player 2.

Player one can use this strategy : Find any perfect matching initially , When at any node , he chooses to go to a node which this node is matched to in this perfect matching. You can easily prove that this strategy will result in player 2 not being able to make a move at the end.

Now let us generalise it to graphs which do not have a perfect matching.

Suppose there is a node which gets matched to some other node in every possible maximal matching.

Claim: This node is a winning node for player 1 if he starts at it.

Proof: Lets call this node

a, suppose you start ata, if you go to a neighbour ofasayx, ifxhas no other neighbours , then player 1 wins trivially.Otherwise if

yis a neighbour ofx, then if there exists some matching whereyis not matched to some other node , you can matchytoxand not matchato anyone which gives another maximal matching whereais not matched to anyone which is contradicting to the fact thatais a part of every maximal matching.Hence we proved that every neighbour of

yis a part of every maximal matching hence when player 2 moves to a neighbour ofx, he is back again at a node which is a part of every maximal matching.The only way this process would end is when player 2 has no move to make when player 1 would win

Claim:Any node for which there exists some maximal matching where this node is not matched to anyone would make player 1 lose if he starts here

Proof: Lets call this node

a, ifadoesn't have any neighbours , player 2 wins triviallyOtherwise suppose

xis a neighbour ofa, thenxmust have some other neighbour otherwise in every maximal matching ,awould be matched toxAlso in every matching ,

xmust be matched to some node otherwiseacan be matched toxto obtain a better matchingSo consider

yto be a node matched withx,yis not a part of every maximal matching since you can take any matching wherexandyare matched and unmatch them and matchaandxto obtain a maximal matching.Hence if player 1 starts at a node which doesn't belong to every maximal matching , player 2 can force him to stay at such nodes until player 1 has no more moves to make

So player 2 will chose a node to start at for which there is a matching where that node is not matched to someone , since there is no perfect matching in this graph , in any maximal matching , there must exist a node which is not matched to anyone and player 2 can just make player 1 start there and win

so we obtain that

Player 1 wins iff there exists a perfect matching.Very nice proof

Thanks a lot for the detailed explanation.

Isn't this true for general graphs as well?

I guess yeah , i wrote for bipartite graph because that is what i had on my mind when thinking about this problem.