Algorithms to parse chess board.

Question

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 = Node()
  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 ?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

The number of ways to get from (0,0) to (m,n) only going right or up is (m+n) choose n.

Each way corresponds uniquely to choosing m rights from a total of m+n right + up.

This also corresponds to the number of m+n bit numbers with m zeroes and generating a list of all such numbers is a well known problem, for instance the Art of Computer Programming by Knuth has it (if I remember correctly).

C++ std::next_permutation would work for helping enumerate all such, I believe. Start with an array of m zeroes and n ones.

Answer 5

The answer is a purely mathematical formula, (w + h) Choose w (w is the width, h is the height). This corresponds to picking w moves to the right out of the (w+h) moves that you make. This number grows quite large, so enumerating on a board larger than, say, 20x20, will take you lots and lots of time (in the order of tens of minutes).

If that doesn't scare you off, then you can use the STL's function std::next_permutation() over an array of w zeros followed by h ones - where 0 corresponds to move to the right, and 1 up.

Answer 6

I suggest you to get a beer and recode it

Answer 7

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 ..