# How to do Fairy Chess problem in O(N^3)?

https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c88e0dec8a

Fairy Chess (35 Points)

You have a $N \times N$ chess board. An $S$-leaper is a chess piece which can move from square $(x_1,y_1)$ on the board to any other square $(x_2,y_2)$ if $|x_1 - x_2| + |y_1 - y_2| \le S$. The chess board may also contain some pawns. The leaper cannot land on the same square as a pawn. In how many ways can a leaper move $M$ times on the board?

Input: The first line contains the number of test cases $T$. $T$ cases follow. Each case contains integers $N$, $M$ and $S$ on the first line. The next $N$ lines contains $N$ characters each. The $i$th character on the $j$th line is a . if the corresponding chess square is empty, P if there is a pawn, or L if the leaper is situated on that square.

Output: For each case, output the number of ways the leaper can make $M$ moves. Output each answer modulo 1000000007.

Constraints: $$\begin{gather} 1 \le T \le 10 \\ 1 \le S \le N \le 200 \\ 1 \le M \le 200 \\ \end{gather}$$ There will be exactly one L character on the board.

Sample Input:

3
4 1 1
....
.L..
.P..
....
3 2 1
...
...
..L
4 3 2
....
...L
..P.
P...


Sample Output:

4
11
385


I wrote a DP solution but with O(N^5).

Psuedocode for ways function:

Memoize[Xmax][Ymax][Nmax];

ways(int X, int Y, int M) // (X,Y) current co-ordinates and M is number of moves to make
{
if(Memoize[X][Y][M] != -1) // != -1 means we already have the result
return Memoize[X][Y][M];
sum=0;
for all (u,v) such that |X-u| + |Y-v| <= S
sum += ways(u, v, M-1);

Memoize[X][Y][M] = sum;
return sum;

}


Code:

/* Enter your code here. Read input from STDIN. Print output to STDOUT */

#include <stdio.h>
#include <stdlib.h>

long ways(long ***DP, char **Chess, int X, int Y, int S, int N, int M);

int main()
{
int T;
scanf("%d", &T);
while(T>0)
{
int N, M, S;
scanf("%d", &N);
scanf("%d", &M);
scanf("%d", &S);
long ***DP = (long ***) malloc(sizeof(long **) * N);
int i,j,k;
char **Chess = (char **)malloc(sizeof(char *) *N);
int Xstart;
int Ystart; //printf("N=%dM=%dS=%d\n", N, M, S);
for(i=0;i<N;i++)
{
Chess[i] = (char *)malloc(sizeof(char) *N);
DP[i] = (long **)malloc(sizeof(long *) * N);
for(j=0;j<N;j++)
{   //printf("i=%dj=%d\n", i, j);
DP[i][j] = (long *)malloc(sizeof(long) *(M+1));
char a;
scanf(" %c", &a);
if(a=='L')
{
Xstart = i;
Ystart = j;
}
Chess[i][j] = a;
//printf("jf=%d\n", j);
}
}

for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
for(k=1;k<M+1;k++)
{
DP[i][j][k] = -1;
}
DP[i][j][0] = 1;
}
}

printf("%ld\n", ways(DP, Chess, Xstart, Ystart, S, N, M));
T--;
}
}

long ways(long ***DP, char **Chess, int X, int Y, int s, int N, int M)
{
if(DP[X][Y][M] !=-1)
{
//printf("X=%d Y=%d M=%d Val=%ld\n", X, Y, M, DP[X][Y][M]);
return DP[X][Y][M];
}
else
{
long sum1 = 0;

int S,k;
sum1 += ways(DP, Chess, X, Y, s, N, M-1);

for(S=1;S<=s;S++)
{
for(k=0;k<=S;k++)
{
if(k!=0 && (S-k)!=0)
{
if(X+k<N && Y+(S-k) <N && Chess[X+k][Y+(S-k)] != 'P')
{
Chess[X+k][Y+(S-k)] = 'L';
Chess[X][Y] = '.';
sum1 += ways(DP, Chess, X+k, Y+(S-k), s, N, M-1);
Chess[X+k][Y+(S-k)] = '.';
Chess[X][Y] = 'L';
}
if(X+k<N && Y-(S-k)>=0 && Chess[X+k][Y-(S-k)] != 'P')
{
Chess[X+k][Y-(S-k)] = 'L';
Chess[X][Y] = '.';
sum1 += ways(DP, Chess, X+k, Y-(S-k), s, N, M-1);
Chess[X+k][Y-(S-k)] = '.';
Chess[X][Y] = 'L';
}
if(X-k>=0 && Y+(S-k) <N && Chess[X-k][Y+(S-k)] != 'P')
{
Chess[X-k][Y+(S-k)] = 'L';
Chess[X][Y] = '.';
sum1 += ways(DP, Chess, X-k, Y+(S-k), s, N, M-1);
Chess[X-k][Y+(S-k)] = '.';
Chess[X][Y] = 'L';
}
if(X-k>=0 && Y-(S-k) >=0 && Chess[X-k][Y-(S-k)] != 'P')
{
Chess[X-k][Y-(S-k)] = 'L';
Chess[X][Y] = '.';
sum1 += ways(DP, Chess, X-k, Y-(S-k), s, N, M-1);
Chess[X-k][Y-(S-k)] = '.';
Chess[X][Y] = 'L';
}

}
else if(k==0 && (S-k)!=0)
{
if(Y+(S-k)<N && Chess[X][Y+(S-k)] != 'P')
{
Chess[X][Y+(S-k)] = 'L';
Chess[X][Y] = '.';
sum1 += ways(DP, Chess, X, Y+(S-k), s, N, M-1);
Chess[X][Y+(S-k)] = '.';
Chess[X][Y] = 'L';
}
if(Y-(S-k)>=0 && Chess[X][Y-(S-k)] != 'P')
{
Chess[X][Y-(S-k)] = 'L';
Chess[X][Y] = '.';
sum1 += ways(DP, Chess, X, Y-(S-k), s, N, M-1);
Chess[X][Y-(S-k)] = '.';
Chess[X][Y] = 'L';
}

}
else if(k!=0 && (S-k)==0)
{
if(X+k<N && Chess[X+k][Y] != 'P')
{
Chess[X+k][Y] = 'L';
Chess[X][Y] = '.';
sum1 += ways(DP, Chess, X+k, Y, s, N, M-1);
Chess[X+k][Y] = '.';
Chess[X][Y] = 'L';
}
if(X-k>=0 && Chess[X-k][Y] != 'P')
{
Chess[X-k][Y] = 'L';
Chess[X][Y] = '.';
sum1 += ways(DP, Chess, X-k, Y, s, N, M-1);
Chess[X-k][Y] = '.';
Chess[X][Y] = 'L';
}

}
}
}
//printf("X=%d Y=%d M=%d Val=%ld\n", X, Y, M, sum);
DP[X][Y][M] = sum1;
return sum1;
}
}

– Juho
Commented Oct 19, 2012 at 16:31
• Sorry dude, I'm new to stackexchage. Commented Oct 19, 2012 at 16:33
• (Thank you for adding the ways function - but it would still help us immensely if you explained what you were trying to do in your code!) Commented Oct 19, 2012 at 16:45
• DP[X][Y][M] means 'number of ways in which the S-leaper can move M steps'. For calculating the number of ways in which a S-leaper can move, I'm generating all (x,y) pairs such that x+y<=S. Generating all such pairs itself takes O(N^2). Commented Oct 19, 2012 at 16:53
• That's a large piece of code, and this is not a programming site. This is definitely the right site to help you with the algorithm, but please meet us part of the way and explain your current solution with English word or ideally readable pseudocode. Commented Oct 19, 2012 at 18:35

A big hint, since this is 'homework' of a sort: this (obviously?) isn't actually anything resembling a chess problem; instead, it's a graph theory problem in disguise. Consider the graph with $n^2-P$ nodes, one for each cell of the board, and an edge between two nodes if they're a leaper-distance away; then the question is asking for the number of paths of length $M$ on this graph starting from a given point. Now, think about a representation that uses an $n\times n$ array representing the number of paths (of a specific length) from the starting point to the given point. Because the degree of the graph is small (there are roughly $2S^2$ individual moves from any given point), a single iteration (going from the length-$b$ paths to the length-$(b+1)$ paths) should take $O(n^2S^2)$ time and the full algorithm should run in time $O(n^2S^2M)$.
Note that the current algorithm as given by the code is much worse than this: each call to the ways() function is a recursive call, meaning that some values are being recomputed many, many times; its running time is, at first glance, roughly $O(S^{2M})$ (since a call to ways($M$) makes $S^2$ calls to ways($M-1$) and thus the running time $w(M) = S^2\cdot w(M-1)$). Replacing that with an iterative approach where one loops $m$ from $1\ldots M$ and stores the number of paths of length $m$ to each cell, then uses the previous iteration's results to find all the paths of length $m+1$, should make a huge difference.
• DFS isn't the most efficient way to do it in this case - while it's good at finding paths, it's lousy at counting paths. Calculating the nodes that are within distance $S$ isn't $O(N^2)$, it's $O(S^2)$ - which, yes, could be $O(N^2)$ if $S$ is large, but should be tracked independently of $N$. Commented Oct 19, 2012 at 17:48
• As for b), that's a straight-up error on my part; I'm used to the traditional definition of a leaper in fairy chess as a piece which moves specific distances (e.g., the knight is a (1,2) leaper) and missed that this was moving within a 'circle' of length $S$. I've corrected my answer. Commented Oct 19, 2012 at 17:51
• While it's accurate to call the algorithm $O(N^5)$, it's also misleading: $S$ is an independent parameter and should be treated as such in the analysis. Commented Oct 19, 2012 at 19:06