Как перечислить уникальные пути, достигающие верхнего правого (h8) квадрата, начиная с нижнего левого (a1) квадрата шахматной доски, учитывая некоторые правила движения?

Question

Несколько недель назад меня попросили найти все разные и уникальные способы достижения правой верхней части шахматной доски, с x, y> 3, начиная с (0, 0), зная, что вы можете только увеличить х и у на +1.

Я до сих пор не смог найти алгоритмы, которые объясняли бы, как перемещаться по шахматной доске, поэтому мне было интересно, есть ли у вас, ребята, что-нибудь порекомендовать?

Другими словами:

Как бы вы перечислили все уникальные способы достижения верхней правой (x, y) шахматной доски с булавкой, начиная с нижнего левого (0, 0). Вы можете только переместить свою булавку вверх или вправо?

#

Обновление от 16.10.2010:

Хорошо, поэтому я провел небольшое исследование в DFS и не был уверен, с чего начать, а потом посмотрел PreOrder Traversal a Tree, и я придумал это, поскольку в основном шахматная доска - это дерево: 1011 *

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

Это определенно проходит через весь уникальный путь, но я уверен, что есть способ улучшить это, чтобы фактически распечатать полный путь. По какой-то причине я не могу найти способ сделать это с помощью рекурсии. Есть идеи?

Answer 1

Я бы посоветовал вам поискать поиск в глубину и поиск в ширину. Ваш поиск успешен, если x & y больше 3 и каждый успешный поиск путь вниз по дереву будет правильным путем.

Answer 2

есть (х + у)! / Х! / У! ( _{x + y} C _x ) способов туда добраться. количество способов добраться до каждой точки - это просто сумма количества способов добраться до точки непосредственно рядом с ней или под ней.

Answer 3

Да, как упоминал Брайан, используйте DFS. В этом случае вам не нужно хранить стек для записи пройденных вами путей, только счетчик, позицию и хороший алгоритм. Например:

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++;
    }
*/
}

Это действительно просто математическая задача, но если вы не хотите, чтобы ваша голова болела слишком сильно, просто сделайте это.

Answer 4

Хорошо, после небольшого исследования я придумал следующее:

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

И это будет вывод:

>> 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']

Швы работают нормально, моя единственная проблема в том, что если мне нужно добавить еще несколько узлов на шахматную доску, я должен сделать это вручную ...