7.12. 构建骑士巡游图¶

7.12. Building the Knight’s Tour Graph

中文英文

为了将骑士巡游问题表示为图，我们将使用以下两个概念：棋盘上的每个方格可以表示为图中的一个节点，而骑士的每一次合法移动可以表示为图中的一条边。图1 说明了骑士的合法移动及其在图中的对应边。

要构建一个 n × n 棋盘的完整图，我们可以使用 Listing 1 中显示的 Python 函数。knight_graph 函数对整个棋盘进行一次遍历。在棋盘上的每个方格上，knight_graph 函数调用一个辅助函数 gen_legal_moves 来创建该位置的合法移动列表。所有合法移动随后被转换为图中的边。棋盘上的每个位置都被转换为类似于 图1 中所示的线性顶点编号。

Listing 1

from pythonds3.graphs import Graph


def knight_graph(board_size):
    kt_graph = Graph()
    for row in range(board_size):
        for col in range(board_size):
            node_id = row * board_size + col
            new_positions = gen_legal_moves(row, col, board_size)
            for row2, col2 in new_positions:
                other_node_id = row2 * board_size + col2
                kt_graph.add_edge(node_id, other_node_id)
    return kt_graph

gen_legal_moves 函数 (Listing 2) 获取骑士在棋盘上的位置并生成所有八个可能的移动，确保这些移动仍然在棋盘内。

Listing 2

def gen_legal_moves(row, col, board_size):
    new_moves = []
    move_offsets = [
        (-1, -2),  # 左下下
        (-1, 2),   # 左上上
        (-2, -1),  # 左左下
        (-2, 1),   # 左左上
        (1, -2),   # 右下下
        (1, 2),    # 右上上
        (2, -1),   # 右右下
        (2, 1),    # 右右上
    ]
    for r_off, c_off in move_offsets:
        if 0 <= row + r_off < board_size and 0 <= col + c_off < board_size:
            new_moves.append((row + r_off, col + c_off))
    return new_moves

图2 显示了一个 $8 \times 8$ 棋盘上所有可能的骑士移动的完整图。图中总共有336条边。注意，棋盘边缘上的顶点比棋盘中间的顶点有更少的连接（合法移动）。再次可以看到图的稀疏性。如果图是完全连接的，将有4096条边。由于只有336条边，邻接矩阵将仅有8.2%的填充率。

To represent the knight’s tour problem as a graph we will use the following two ideas: each square on the chessboard can be represented as a node in the graph and each legal move by the knight can be represented as an edge in the graph. Figure 1 illustrates the legal moves by a knight and the corresponding edges in a graph.

To build the full graph for an n-by-n board, we can use the Python function shown in Listing 1. The knight_graph function makes one pass over the entire board. At each square on the board the knight_graph function calls a helper, gen_legal_moves, to create a list of legal moves for that position on the board. All legal moves are then converted into edges in the graph. Each location on the board is converted into a linear vertex number similar to the vertex numbers shown in Figure 1.

Listing 1

from pythonds3.graphs import Graph


def knight_graph(board_size):
    kt_graph = Graph()
    for row in range(board_size):
        for col in range(board_size):
            node_id = row * board_size + col
            new_positions = gen_legal_moves(row, col, board_size)
            for row2, col2 in new_positions:
                other_node_id = row2 * board_size + col2
                kt_graph.add_edge(node_id, other_node_id)
    return kt_graph

The gen_legal_moves function (Listing 2) takes the position of the knight on the board and generates each of the eight possible moves, making sure those moves are still within the board.

Listing 2

def gen_legal_moves(row, col, board_size):
    new_moves = []
    move_offsets = [
        (-1, -2),  # left-down-down
        (-1, 2),   # left-up-up
        (-2, -1),  # left-left-down
        (-2, 1),   # left-left-up
        (1, -2),   # right-down-down
        (1, 2),    # right-up-up
        (2, -1),   # right-right-down 
        (2, 1),    # right-right-up
    ]
    for r_off, c_off in move_offsets:
        if 0 <= row + r_off < board_size and 0 <= col + c_off < board_size:
            new_moves.append((row + r_off, col + c_off))
    return new_moves

Figure 2 shows the complete graph of possible moves on an $8 \times 8$ board. There are exactly 336 edges in the graph. Notice that the vertices corresponding to the edges of the board have fewer connections (legal moves) than the vertices in the middle of the board. Once again we can see how sparse the graph is. If the graph was fully connected there would be 4,096 edges. Since there are only 336 edges, the adjacency matrix would be only 8.2 percent full.

最后更新: 2024年9月13日
创建日期: 2024年9月9日