-3

好的，所以我要在 C 中创建一个代码，它输出板的所有可能解决方案。该板是一个 nxn 板，一排看起来像这样（3x3）：AA BA BB。

游戏的目标是通过仅垂直或水平穿过棋盘来访问棋盘中的每个位置。另外，如果第一个或第二个字母相同，则只能转到下一个位置，因此我可以从 AA 转到 BA，但不能从 AA 转到 BB，并且每个位置只能访问一次。起始位置始终是左上角或 00 位置。

无论如何，我想到了一种算法，计算机从 00 开始并检查下一个有效位置，比如说 01。然后计算机使用 00 和 01 链作为起始位置检查所有可能的解决方案。当没有更多时，计算机检查一个新链，比如 00、10 等等。你怎么知道不重复以前的解决方案？我在想一些递归的东西。除了我的，还有更有效的寻路算法吗？

4

2 回答 2

0

回复：你怎么知道不重复以前的解决方案？

深度优先搜索算法的一部分涉及标记访问过的节点，以免访问它们两次。这可以通过多种方式完成：节点本身的备用位，在每次搜索之前初始化，或者在被搜索的图外部的动态集合数据结构。

顺便说一下，这个问题与格雷码有关，格雷码是一种排列二进制字的代码的方式，以便在连续代码之间只有一位变化。例如 000 001 011 010 110 100 101 111。

这意味着在您的板上，当且仅当它是两位格雷码后继或前任时，您​​才能导航到相邻的方格。

但是格雷码形成一个序列。所以这个问题是同构的，其中有一个从 0 到 3 的简单编号，并且允许您从 N 到 N+1 后继或 N-1 前驱。

这可以帮助你思考问题。

于 2012-04-10T02:11:53.803 回答
0

这是 Python 中一个非常低效的解决方案。你应该能够跟上。我不想只是用你自己的语言给出答案：P

class Finder:
    def __init__(self, board, n, x, y):
        self.board = board
        self.n = n

        # Create a copy of the board.
        self.copy = []
        for i in range(n):
            row = []
            self.copy += [row]
            for j in range(n):
                row += [False]

        # The best move sequence (longest).
        self.best = []
        # The current move sequence.
        self.move = []

        self.find(x, y)

    def valid_move(self,x1, y1, x2, y2):
        # Don't move off the board!
        if x2 < 0 or x2 > self.n - 1 or y2 < 0 or y2 > self.n - 1:
            return False

        # Don't go somewhere we've gone before!
        if self.copy[y2][x2]:
            return False

        # See if this is a valid move.
        a = self.board[y1][x1]
        b = self.board[y2][x2]
        return a[0] == b[0] or \
               a[0] == b[1] or \
               a[1] == b[0] or \
               a[1] == b[1] 

    def find(self,x, y):
        self.move += [(x, y, board[y][x])]
        self.copy[y][x] = True

        # If this is the best path, then create a copy.
        if len(self.move) > len(self.best):
            self.best = list(self.move)

        # Short-circuit if the optimal route is found.
        if len(self.best) == self.n * self.n:
            return

        newX = x - 1
        newY = y
        if self.valid_move(x, y, newX, newY):
            self.find(newX, newY)

        newX = x
        newY = y - 1
        if self.valid_move(x, y, newX, newY):
            self.find(newX, newY)

        newX = x + 1
        newY = y
        if self.valid_move(x, y, newX, newY):
            self.find(newX, newY)

        newX = x
        newY = y + 1
        if self.valid_move(x, y, newX, newY):
            self.find(newX, newY)

        # Clean up by removing the last move.
        self.move = self.move[:-1]
        self.copy[y][x] = False

 # The board
board = \
[["AB", "XX", "DE"],
 ["BB", "FE", "DD"],
 ["BC", "CC", "CD"],
 ]

# The size of the board.
n = 3

# Find!!
finder = Finder(board, n, 0, 0)

for row in board:
    print(row)

# Print empty line.
print()

for move in finder.best:
    print(move)

这是输出：

['AB', 'XX', 'DE']
['BB', 'FE', 'DD']
['BC', 'CC', 'CD']

(0, 0, 'AB')
(0, 1, 'BB')
(0, 2, 'BC')
(1, 2, 'CC')
(2, 2, 'CD')
(2, 1, 'DD')
(2, 0, 'DE')
于 2012-04-10T02:53:16.513 回答