Find a recurrence relation problem...

Question

Well... I am stuck with the recurrence problem...

Find a recurrence relation for the number Queen walks from the lower-left corner of an arbitrary-size chess board to the square $(n,n)$. (A Queen can move any number of squares horizantally, vertically, or diagonally. Assume that the Queen always move to the right,up, or up-right.) Find the corresponding generating function.

I think I have to split the cases with the movements(right, up, or up-right.)

It becomes tricky with that a Queen can move any number of squares...

Can I get some clue to start?

Answer 1

See, that from position $(a,b)$ the queen can move right in $n-b$ ways, up in $n-a$ ways and 'right-up' in $\min(n-a, n-b)$ ways.

Therefore the recursive function can be written as

public int count=0;
public int n;
public void main()
{
  n=8; //here you can set your n
  count =0;
  movements(1,1);
  Console.WriteLine(count.ToString());
}
public void movements(int a, int b)
{
  if(a==n && b==n)
  {
    count++;
    return;
  }
  for(int i=a+1; i<=n; ++i)
    movements(i, b);
  for(int i=b+1; i<=n; ++i)
    movements(a, i);
  for(int i=1 ; i<=Math.Min(n-a, n-b); ++i)
    movements(a+i, b+i);
}

or, in mathematical way:

$f(a,b,n) = \begin{cases}1 &, (a,b)=(n,n);\\ \sum\limits_{i=a+1}^nf(i,b,n)+\sum\limits_{i=b+1}^n f(a,i,n) + \sum\limits_{i=1}^{\min(n-a,n-b)}f(a+i,b+i,n) &, (a,b)\neq (n,n); \end{cases}$