A game relevant to maze

Question

A and B play a game as follows:

For maze represented by matrix has size n × n, the cell contains character "." represents the movable land and the cell contains character "#" character represents an obstacle that cannot be stepped on. Starting from the cell (n, n), each person takes turns choosing a next position to move. The new position must be on the left or upward the current cell (Move as the rook in the chess). There are no obstacles in the middle of the current position and the new location. If you can't find a new position, that person will lose. A is the one who go first. Determine who is the winner.

For examples:

• With n = 2 and the maze:

 . .
 . .

The result is B, because initially at coordinates (2,2), A will go left or upward so there will be coordinates (1,2) or (2,1). Then B will move to the coordinates (1,1). A can't move anymore so he loses and B wins.

• With n = 5 and the maze:

. . # . .
# . . . #
. . # . .
# . . . .
. . . . .

Explaining similarly, we have A will be the winner.

This is my attempt: I tried to use recursive programming to determine who is the winner, but it takes too long when n is large, and I've tried to build dynamic-programming for this problem.

Edit:

So, the main of this problem to how we can determine who is the winner in this game. Suppose that initially at coordinates (n,n), we have a stone. A and B take turns playing a game as follows: A will choose a new position to move this stone (we can image that the stone like a rook in a chess), this new position must be on the left or above the current cell, after then B also choose a new position to move this stone. Until, the person who can't move this stone will be loser.

Note that: The char "." represents the movable land and the char "#" represents an obstacle!

And my purpose when post this problem is I want to try a dynamic-programming or recursion to determine who is the winner in this game.

Answer 1

Well you can just apply Sprague-Grundy theorem to find out the winner.

So calculating grundy numbers would be something like this:

1. Mark sure-loss cells with 0 (cells where we cant go up or left)

0 . # 0 .
# . . . #
0 . # . .
# . . . .
0 . . . .

2. Loop through remaining cells and for each unknown cell (marked .) find all reachable cells in one move
3. Now MEX of those cells will be value of unknown cell
4. After filling all cells we will have something like this:

0 1 # 0 1
# 0 1 2 #
0 2 # 1 0
# 3 0 4 1
0 4 1 3 2

5. So player will win if starting cell (n,n) is not 0

Sample code (C++), O(n^3):

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<string>A = {
                "..#..",
                "#...#",
                "..#..",
                "#....",
                "....."};

    int n = A.size();
    int Grundy[n][n]={};

    for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
        if(A[i][j]!='#')
        {
            int can[2*n+1]={};

            int left = j-1;
            while(left>=0 && A[i][left]!='#')
            {
                can[Grundy[i][left]]++;
                left--;
            }

            int up = i-1;
            while(up>=0 && A[up][j]!='#')
            {
                can[Grundy[up][j]]++;
                up--;
            }

            while(can[Grundy[i][j]])Grundy[i][j]++;
        }

    cout<<(Grundy[n-1][n-1] ? "Player 1 wins\n" : "Player 2 wins\n");
}

---

This results in O(n^3) solution, though we can still optimize to O(n^2) as follows:

1. Because we only play one game board at a time, we don't really need all those grundy numbers, it's enough to know if there's grundy number 0 reachable from current cell
2. Let's call those cells with grundy value 0 losing cells, so now we can win from cell (i,j) if and only if we can move to some losing cell.
3. searching for reachable cells will still result in O(n^3) if we use for/while loop for this
4. To get O(n^2) we need to use prefix arrays for rows and columns.
5. so win[i][j] - stores if we can win from cell (i,j)
6. loseRow[i][j] - stores if we have any losing cells in row i that can be reached from cell (i,j)
7. loseCol[i][j] - stores if we have any losing cells in column j that can be reached from cell (i,j)

Sample code (C++), O(n^2):

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<string>A = {
                "..#..",
                "#...#",
                "..#..",
                "#....",
                "....."};

    int n = A.size();
    int win[n][n]={};
    int loseRow[n][n]={};
    int loseCol[n][n]={};

    for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
        if(A[i][j]!='#')
        {
            if(j-1>=0 && A[i][j-1]!='#')
                {
                    win[i][j]|=loseRow[i][j-1];
                    loseRow[i][j]=loseRow[i][j-1];
                }

            if(i-1>=0 && A[i-1][j]!='#')
                {
                    win[i][j]|=loseCol[i-1][j];
                    loseCol[i][j]=loseCol[i-1][j];
                }

            loseRow[i][j]|=!win[i][j];
            loseCol[i][j]|=!win[i][j];
        }

    cout<<(win[n-1][n-1] ? "Player 1 wins\n" : "Player 2 wins\n");
}

Answer 2

We can classify coordinates in the matrix as winning (i.e. the side to move wins with correct play) or losing (i.e. the side to move loses with correct play).

A coordinate (r,c) corresponding to movable land is

• losing if there are no legal moves;
• losing if all legal moves go to winning coordinates;
• winning if at least one legal move goes to losing coordinates.

Note that, according to the first rule, (1,1) is losing and therefore according to the last rule, whoever can move the stone to (1,1) wins.

The classification of your second matrix is:

L W # L W
# L W W #
L W # W L
# W L W W
L W W W W

Since the value of a coordinate depends only on values to the left and above, we can compute the values in top-to-bottom, left-to-right order. You don't really need recursion or dynamic programming. Something like

for r in 1...n
  for c in 1...n
    look left and up until the edge of the board or the first # sign
    if there are any L values, then mark (r,c) as winning
    otherwise mark (r,c) as losing

This naive approach takes O(n) time per coordinate, so O(n³) total time. This can be improved to O(n²) by maintaining some boolean flags as we scan the matrix:

• One row flag indicating whether we can make a leftwards move from the current position to a losing position. A value of L will set the flag to true, while a # sign will reset it to false.
• N column flags where f_i indicates whether we can make an upwards move on column i to a losing position. Each flag changes values as described above.