7.11. 骑士巡游问题

7.11. The Knight’s Tour Problem

中文英文

另一个经典问题，我们可以用来说明第二个常见图算法的是“骑士巡游”问题。骑士巡游谜题在棋盘上进行，棋盘上只有一个棋子，即骑士。谜题的目标是找到一系列移动，使得骑士能够访问棋盘上的每个方格一次且仅一次。这样的一系列移动被称为巡游。骑士巡游谜题让国际象棋棋手、数学家和计算机科学家们着迷了超过一千年。对于一个 $8\times 8$ 的棋盘，已知的可能合法巡游的上界为 $1.305\times {10}^{35}$；然而，甚至还有更多可能的死胡同。显然，这是一个需要真正智慧、计算能力，或者两者兼备的问题。

虽然研究人员已经研究了许多不同的算法来解决骑士巡游问题，但图搜索是一种最容易理解和编程的方法。我们将再次通过两个主要步骤来解决这个问题：

• 将骑士在棋盘上的合法移动表示为图。
• 使用图算法找到一条长度为 $rows\times columns-1$ 的路径，使图上的每个顶点都被访问一次且仅一次。

Another classic problem that we can use to illustrate a second common graph algorithm is called the knight’s tour. The knight’s tour puzzle is played on a chess board with a single chess piece, the knight. The object of the puzzle is to find a sequence of moves that allow the knight to visit every square on the board exactly once. One such sequence is called a tour. The knight’s tour puzzle has fascinated chess players, mathematicians, and now, computer scientists, for over a thousand years. The upper bound on the number of possible legal tours for an $8\times 8$ chessboard is known to be $1.305\times {10}^{35}$; however, there are even more possible dead ends. Clearly this is a problem that requires some real brains, some real computing power, or both.

Although researchers have studied many different algorithms to solve the knight’s tour problem, a graph search is one of the easiest to understand and program. Once again we will solve the problem using two main steps:

• Represent the legal moves of a knight on a chessboard as a graph.
• Use a graph algorithm to find a path of length $rows\times columns-1$ where every vertex on the graph is visited exactly once.

---

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