How to enumerate unique paths reaching top right (h8) square starting from bottom left (a1) square of a chess board given some move rules?

I was asked a few weeks ago, to find all the different and unique ways to reach the top right of a chess board, with x, y > 3, starting from (0, 0), knowing that you can only increase x and y by +1.

I still haven't been able to find algorithms that would explain how to navigate over a chessboard, so I was wondering if you guys had anything to recommend ?

In other words :

How would you list all the unique ways to reach the top right (x, y) of a chessboard with a pin, starting from bottom left (0, 0). You can only move your pin up or right ?

Update 10/16/2010 :

Okay so I did a bit of research in DFS, and wasn't sure where to start from, and then looked up PreOrder Traversal of a Tree, and I came up with this, since basically a chessboard is a tree :

#!/usr/bin/python

class Node(object):

  value = None
  left = None
  right = None

  def SetValue(self, value):
    self.value = value

  def SetLeftNode(self, node):
    self.left = node

  def SetRightNode(self, node):
    self.right = node

def main():
  a = Node()
  a.SetValue((0,0))

  b = Node()
  b.SetValue((1,0))

  c = Node()
  c.SetValue((2,0))

  d = Node()
  d.SetValue((0,1))

  e = N开发者_开发百科ode()
  e.SetValue((1,1))

  f = Node()
  f.SetValue((2,1))

  g = Node()
  g.SetValue((0,2))

  h = Node()
  h.SetValue((1,2))

  i = Node()
  i.SetValue((2,2))

  a.SetLeftNode(b)
  a.SetRightNode(d)

  b.SetLeftNode(g)
  b.SetRightNode(e)

  c.SetLeftNode(f)
  c.SetRightNode(None)

  d.SetLeftNode(e)
  d.SetRightNode(c)

  e.SetLeftNode(h)
  e.SetRightNode(f)

  f.SetLeftNode(i)
  f.SetRightNode(None)

  g.SetLeftNode(None)
  g.SetRightNode(h)

  h.SetLeftNode(None)
  h.SetRightNode(i)

  i.SetLeftNode(None)
  i.SetRightNode(None)

  PreOrderTraversal(a)

def PreOrderTraversal(node):
  if not node:
    return None
  print node.value
  if node.value == (2,2):
    print 'Reached i' 
  PreOrderTraversal(node.left)
  PreOrderTraversal(node.right)

main() 

The output of this is the following :

(0, 0)
(1, 0)
(0, 2)
(1, 2)
(2, 2)
Reached i
(1, 1)
(1, 2)
(2, 2)
Reached i
(2, 1)
(2, 2)
Reached i
(0, 1)
(1, 1)
(1, 2)
(2, 2)
Reached i
(2, 1)
(2, 2)
Reached i
(2, 0)
(2, 1)
(2, 2)
Reached i

It definitely goes through all the unique path, but I am sure there's a way to improve this to actually print out the complete path. For some reason I can't find a way to do this using recursion. Any idea ?

I'd suggest you look into depth-first search and breadth-first search. Your search is successful when x & y are both greater than 3, and each successful search path down the tree would be a valid path.

there are (x+y)!/x!/y! (_x+yC_x )ways to get there. the number of ways to reach each point is simply the sum of the number of ways to get to the point directly beside/below it.

Yes, as was mentioned by Bryan, use DFS. In this case, you don't need to keep a stack to record the ways you went, just a counter, and a position, and a good algorithm. For example:

int count = 0;
int x = 0;
int y = 0;
int to_x[3] = {0, 0, 0};
for(; to_x[2] < 8; counter++)
{
    for(int arridx = 0; arridx < 2; arridx++)
    {
        if(to_x[arridx] == 8)
        {
            to_x[arridx] = 0;
            to_x[arridx+1] += 1;
        }
    }
/*
    for(int arridx2 = 0; arridx2 < 3; arridx2++)
    {
        //for(; x < to_x[arridx2]; x++);
        x = to_x[arridx2];

        y++;
    }
*/
}

This is really just a math problem, but if you don't want your head to hurt too much, just do this.

Okay so after a bit of research I came up with this :

#!/usr/bin/python

chess_board = {'A': ['B', 'C'],
               'B': ['D', 'E'],
               'C': ['E', 'F'],
               'D': ['G'],
               'E': ['G', 'H'],
               'F': ['H'],
               'G': ['I'],
               'H': ['I'],
               'I': []} 


def find_all_paths(graph, start, end, path=[]):
  path = path + [start]
  if start == end:
    return [path]
  paths = []
  for node in graph[start]:
    if node not in path:
      new_paths = find_all_paths(graph, node, end, path)
      for new_path in new_paths:
        paths.append(new_path)
  return paths

all_path =  find_all_paths(chess_board, 'A', 'I')
for path in all_path:
  print path

And this would be the output :

>> python chess_bfs.py 
['A', 'B', 'D', 'G', 'I']
['A', 'B', 'E', 'G', 'I']
['A', 'B', 'E', 'H', 'I']
['A', 'C', 'E', 'G', 'I']
['A', 'C', 'E', 'H', 'I']
['A', 'C', 'F', 'H', 'I']

Seams to work fine, my only issue is, if I need to add some more nodes to my chessboard, then I have to do it manually ..