给定一些移动规则，如何枚举从棋盘左下角（a1）方块开始到达右上角（h8）方块的唯一路径？

几周前，我被要求找到所有不同且独特的方法来到达棋盘的右上角，其中 x, y > 3，从 (0, 0) 开始，知道你只能增加 x 和 y通过+1。

我仍然无法找到可以解释如何在棋盘上导航的算法，所以我想知道你们是否有什么可以推荐的？

换句话说 ：

您会如何列出从左下角 (0, 0) 开始，用图钉到达棋盘右上角 (x, y) 的所有独特方法。您只能将图钉向上或向右移动吗？

2010 年 10 月 16 日更新：

好吧，我在 DFS 中做了一些研究，不确定从哪里开始，然后查找了树的预序遍历，我想出了这个，因为基本上棋盘是一棵树：

#!/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() 

其输出如下：

(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

它肯定会经历所有独特的路径，但我确信有一种方法可以改进它以实际打印出完整的路径。由于某种原因，我找不到使用递归来执行此操作的方法。任何想法 ？

我建议你看看深度优先搜索 http://en.wikipedia.org/wiki/Depth-first_search and 广度优先搜索。 http://en.wikipedia.org/wiki/Breadth-first_search当 x 和 y 都大于 3 时，搜索成功，并且沿着树向下的每个成功搜索路径都将是有效路径。