T28050: 骑士周游
Warnsdorff, 回溯, http://cs101.openjudge.cn/practice/28050/
在一个国际象棋棋盘上，一个棋子“马”（骑士），按照“马走日”的规则，从一个格子出发，要走遍所有棋盘格恰好一次。把一个这样的走棋序列称为一次“周游“。在 8 × 8 的国际象棋棋盘上，合格的“周游”数量有 1.305×10^35这么多，走棋过程中失败的周游就更多了。
采用图搜索算法，是解决骑士周游问题最容易理解和编程的方案之一，解决方案分为两步： 首先用图表示骑士在棋盘上的合理走法； 采用图搜索算法搜寻一个长度为（行 × 列-1）的路径，路径上包含每个顶点恰一次。
输入
两行。 第一行是一个整数n，表示正方形棋盘边长，3 <= n <= 19。
第二行是空格分隔的两个整数sr, sc，表示骑士的起始位置坐标。棋盘左上角坐标是 0 0。0 <= sr <= n-1, 0 <= sc <= n-1。
输出
如果是合格的周游，输出 success，否则输出 fail。
样例输入
5
0 0样例输出
success来源
https://runestone.academy/ns/books/published/pythonds3/Graphs/KnightsTourAnalysis.html
和马走日思路一样，不过需要优化搜索算法，先找到当前点能够走的所有下一个点，然后计算每个下一个点能走的下下一个点数量，优先搜索数量少的，一旦发现一条周游路径就返回True。
采用 Warnsdorff’s Rule 进行搜索，优先选择出度最小的下一步路径，从而提高找到完整骑士周游路径的成功率。需要回溯的功能来确保即使某个方向走不通，仍然可以回到上一步，尝试其他可能的路径。结合了 Warnsdorff 规则 和 回溯，确保最大程度提高找到骑士周游的概率
import sys
def is_valid_move(x, y, board, n):
return 0 <= x < n and 0 <= y < n and board[x][y] == -1
def get_degree(x, y, board, n, moves):
count = 0
for dx, dy in moves:
if is_valid_move(x + dx, y + dy, board, n):
count += 1
return count
def knights_tour_warnsdorff(n, sr, sc):
moves = [(2, 1), (1, 2), (-1, 2), (-2, 1),
(-2, -1), (-1, -2), (1, -2), (2, -1)]
board = [[-1 for _ in range(n)] for _ in range(n)]
board[sr][sc] = 0
def backtrack(x, y, move_count):
if move_count == n * n:
return True
next_moves = []
for dx, dy in moves:
nx, ny = x + dx, y + dy
if is_valid_move(nx, ny, board, n):
degree = get_degree(nx, ny, board, n, moves)
next_moves.append((degree, nx, ny))
next_moves.sort() # 按 Warnsdorff 规则选择最少可行移动的方向
for _, nx, ny in next_moves:
board[nx][ny] = move_count
if backtrack(nx, ny, move_count + 1):
return True
board[nx][ny] = -1 # 回溯
return False
if backtrack(sr, sc, 1):
print("success")
else:
print("fail")
if __name__ == "__main__":
n = int(sys.stdin.readline().strip())
sr, sc = map(int, sys.stdin.readline().strip().split())
knights_tour_warnsdorff(n, sr, sc)import sys
class Graph:
def __init__(self):
self.vertices = {}
self.num_vertices = 0
def add_vertex(self, key):
self.num_vertices = self.num_vertices + 1
new_ertex = Vertex(key)
self.vertices[key] = new_ertex
return new_ertex
def get_vertex(self, n):
if n in self.vertices:
return self.vertices[n]
else:
return None
def __len__(self):
return self.num_vertices
def __contains__(self, n):
return n in self.vertices
def add_edge(self, f, t, cost=0):
if f not in self.vertices:
nv = self.add_vertex(f)
if t not in self.vertices:
nv = self.add_vertex(t)
self.vertices[f].add_neighbor(self.vertices[t], cost)
#self.vertices[t].add_neighbor(self.vertices[f], cost)
def getVertices(self):
return list(self.vertices.keys())
def __iter__(self):
return iter(self.vertices.values())
class Vertex:
def __init__(self, num):
self.key = num
self.connectedTo = {}
self.color = 'white'
self.distance = sys.maxsize
self.previous = None
self.disc = 0
self.fin = 0
def __lt__(self,o):
return self.key < o.key
def add_neighbor(self, nbr, weight=0):
self.connectedTo[nbr] = weight
# def setDiscovery(self, dtime):
# self.disc = dtime
#
# def setFinish(self, ftime):
# self.fin = ftime
#
# def getFinish(self):
# return self.fin
#
# def getDiscovery(self):
# return self.disc
def get_neighbors(self):
return self.connectedTo.keys()
# def getWeight(self, nbr):
# return self.connectedTo[nbr]
def __str__(self):
return str(self.key) + ":color " + self.color + ":disc " + str(self.disc) + ":fin " + str(
self.fin) + ":dist " + str(self.distance) + ":pred \n\t[" + str(self.previous) + "]\n"
def knight_graph(board_size):
kt_graph = Graph()
for row in range(board_size): #遍历每一行
for col in range(board_size): #遍历行上的每一个格子
node_id = pos_to_node_id(row, col, board_size) #把行、列号转为格子ID
new_positions = gen_legal_moves(row, col, board_size) #按照 马走日，返回下一步可能位置
for row2, col2 in new_positions:
other_node_id = pos_to_node_id(row2, col2, board_size) #下一步的格子ID
kt_graph.add_edge(node_id, other_node_id) #在骑士周游图中为两个格子加一条边
return kt_graph
def pos_to_node_id(x, y, bdSize):
return x * bdSize + y
def gen_legal_moves(row, col, board_size):
new_moves = []
move_offsets = [ # 马走日的8种走法
(-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
# def legal_coord(row, col, board_size):
# return 0 <= row < board_size and 0 <= col < board_size
def knight_tour(n, path, u, limit):
u.color = "gray"
path.append(u) #当前顶点涂色并加入路径
if n < limit:
neighbors = ordered_by_avail(u) #对所有的合法移动依次深入
#neighbors = sorted(list(u.get_neighbors()))
i = 0
for nbr in neighbors:
if nbr.color == "white" and \
knight_tour(n + 1, path, nbr, limit): #选择“白色”未经深入的点，层次加一，递归深入
return True
else: #所有的“下一步”都试了走不通
path.pop() #回溯，从路径中删除当前顶点
u.color = "white" #当前顶点改回白色
return False
else:
return True
def ordered_by_avail(n):
res_list = []
for v in n.get_neighbors():
if v.color == "white":
c = 0
for w in v.get_neighbors():
if w.color == "white":
c += 1
res_list.append((c,v))
res_list.sort(key = lambda x: x[0])
return [y[1] for y in res_list]
# class DFSGraph(Graph):
# def __init__(self):
# super().__init__()
# self.time = 0 #不是物理世界，而是算法执行步数
#
# def dfs(self):
# for vertex in self:
# vertex.color = "white" #颜色初始化
# vertex.previous = -1
# for vertex in self: #从每个顶点开始遍历
# if vertex.color == "white":
# self.dfs_visit(vertex) #第一次运行后还有未包括的顶点
# # 则建立森林
#
# def dfs_visit(self, start_vertex):
# start_vertex.color = "gray"
# self.time = self.time + 1 #记录算法的步骤
# start_vertex.discovery_time = self.time
# for next_vertex in start_vertex.get_neighbors():
# if next_vertex.color == "white":
# next_vertex.previous = start_vertex
# self.dfs_visit(next_vertex) #深度优先递归访问
# start_vertex.color = "black"
# self.time = self.time + 1
# start_vertex.closing_time = self.time
def main():
def NodeToPos(id):
return ((id//8, id%8))
bdSize = int(input()) # 棋盘大小
*start_pos, = map(int, input().split()) # 起始位置
g = knight_graph(bdSize)
start_vertex = g.get_vertex(pos_to_node_id(start_pos[0], start_pos[1], bdSize))
if start_vertex is None:
print("fail")
exit(0)
tour_path = []
done = knight_tour(0, tour_path, start_vertex, bdSize * bdSize-1)
if done:
print("success")
else:
print("fail")
exit(0)
# 打印路径
cnt = 0
for vertex in tour_path:
cnt += 1
if cnt % bdSize == 0:
print()
else:
print(vertex.key, end=" ")
#print(NodeToPos(vertex.key), end=" ") # 打印坐标
if __name__ == '__main__':
main()王镜廷，数学学院，发现了不能周游的规律。
Q: 在一个类似国际象棋棋盘上，一个棋子“马”（骑士），按照“马走日”的规则，从一个格子出发，要走遍所有棋盘格恰好一次。把一个这样的走棋序列称为一次“周游“。
如何证明：整数n，表示正方形棋盘边长。如果n是奇数，骑士出发点坐标是(x,y)，x + y也是奇数，这样的周游不存在。
A: 证明这个问题的方法主要基于对棋盘的二分色彩与骑士跳跃特性的分析。我们可以将这个问题简化如下：
棋盘的着色: 首先，我们可以将一个 n x n 的棋盘视为黑白相间的格子，类似于国际象棋棋盘。如果 n 是奇数，棋盘会有 (n^2) 个格子，因为 n^2 也是奇数，所以黑白格子数量不相等。具体来说，其中一种颜色的格子将比另一种多一个。
骑士的跳跃: 骑士（马）的移动可以看作是在这样的格子间的跳跃。每次移动，骑士从一个颜色的格子跳到另一个颜色的格子。具体来说，如果它在一个黑色格子上，下一步必然是白色格子，反之亦然。
起始点的颜色与奇数特性: 如果骑士起始点的坐标 (x, y) 满足 x + y 为奇数，在标准黑白棋盘上，这意味着骑士位于一种特定颜色的格子上（比如说白格）。由于总格子数为奇数，且黑白格子数目不相等，假设黑格比白格多一个。因此，如果骑士始终从白格跳到黑格，那么它无法再次跳回到黑格，因为最终会有一个黑格没有白格可供跳转。
周游的可能性: 周游意味着每个格子都恰好走一次，没有遗漏也没有重复。如果棋盘的一个颜色的格子比另一个多，那么从总格数为奇数的格子颜色开始的周游是不可能的，因为骑士将无法找到足够的跳转点完成最后一步。
结合以上几点，可以得出结论：在一个奇数边长的棋盘上，如果骑士起始点的坐标 (x, y) 使得 x + y 为奇数，那么无法实现一个完整的周游，因为从颜色较少的格子开始，最终将无法匹配到足够的颜色格子完成最后一跳。因此，这样的周游不存在。
为了更好地理解这一概念，让我们考虑一个具体的例子，以 5x5 的棋盘为例。5x5 棋盘的着色，B 代表黑色格，W 代表白色格
B W B W B
W B W B W
B W B W B
W B W B W
B W B W B一个不可能完成周游的例子，骑士的起始点到 (3, 2)：颜色：白色（W），坐标和 (x + y)：3 + 2 = 5 (奇数)
在这种情况下，因为 5 是奇数，我们预计无法完成周游。理由是起始于白色格子，并且由于黑色格子（13个）比白色格子（12个）多一个，所以最终将会有一个黑色格子无法被访问完成最后一步跳跃。
验证理论
尝试规划一个从 (3, 2) 开始的骑士周游路径会发现，由于棋盘的不对称性（黑格多于白格），骑士最终将被迫尝试从一个黑格跳至另一个黑格，这违反了骑士的跳跃规则（每次跳跃必须从一种颜色的格子跳到另一种颜色的格子），从而导致周游失败。
此理论和例子展示了如何使用棋盘的二分色彩性质以及格子数量的奇偶性来分析和判断骑士周游的可能性。在任何边长为奇数的棋盘上，如果起始点的坐标和为奇数，则无法完成周游，因为总会有多出的一个同色格子无法被合规跳跃覆盖。
Q: 如何判断是否存在哈密顿通路？
A: 判断是否存在哈密顿通路（一条通过图中每个顶点恰好一次的路径）是一个在图论中广泛研究的问题，尤其是在国际象棋棋盘中骑士的移动规则下。这个问题属于NP-完全问题，即没有已知的能在多项式时间内解决的算法。尽管如此，有一些启发式方法和特殊情况下的理论可以帮助判断某些图是否存在哈密顿通路。
对于骑士周游问题，特别是在 n x n 棋盘上的骑士的移动，可以使用以下方法或考虑以下条件来估计或判断哈密顿通路的存在：
图的结构和大小：
- 对于某些特定大小的棋盘，如 8x8 棋盘，已经通过计算机算法证明可以找到哈密顿通路（即完整的骑士周游）。
- 对于较小或不规则大小的棋盘，情况可能会变得复杂，例如 3x3、4x4 和部分偶数棋盘，已知是不可能的。
计算机搜索算法：
- 使用回溯法、深度优先搜索（DFS）或启发式搜索（如A*搜索算法）来尝试构建通路。这些方法可能需要大量的计算时间，尤其是当棋盘较大时。
- 对于大棋盘，通常需要利用某些启发式方法来减少搜索空间，例如优先考虑边缘或难以达到的格子。
数学定理和规则：
- 存在一些定理，如Dirac定理和Ore定理，它们提供了判断一般图是否存在哈密顿回路的充分条件，但这些通常难以直接应用于国际象棋棋盘上的骑士移动问题。
- 对于特定的起点和棋盘布局，可以进行数学归纳或构造性证明来判断哈密顿通路的存在。
实验和模拟：
- 对不同的棋盘配置进行实验模拟，尝试找到通路。实际上，许多现存的哈密顿通路是通过计算机模拟和实验发现的。
理论上的限制：
- 如上文中提到的，对于奇数x奇数的棋盘以及某些起始点条件，可以数学上证明骑士周游问题的解不存在。
综上所述，判断骑士的哈密顿通路存在与否需要依赖具体情况和实验，对于大型棋盘通常依赖计算机算法和启发式搜索。针对特定棋盘和条件，可能需要定制特定的算法或利用已有的理论成果。
【李炳锋 24 级】观察到，随着棋盘总格数的增加，需要搜索的分支总数呈指数级增长。这意味着在较大的棋盘上，尝试搜完所有可能的分支必然导致时间超限（TLE）。基于这一点，我们可以得出一个结论：当无法通过简单的判据来确定某一情形是否有解时，该情形实际上是可解的。否则，我们将不得不依赖于逐一分支搜索的方法来证明其无解，而这在规定的时间内是不可行的。
一种简便有效的判别方式是对棋盘进行交叉染色处理。骑士每走一步都会从一种颜色的格子跳到另一种颜色的格子。因此，如果棋盘上某一种颜色的格子比另一种多出一个，则骑士必须从较多的那种颜色的格子开始才能完成周游；若某一种颜色的格子比另一种多出超过一个，则可以断定无法完成周游。
# 李炳锋24级
n = int(input()) # 输入棋盘的大小 n x n
p, q = map(int, input().split()) # 输入骑士的起始位置 (p, q)
if n < 5:
print("fail") # 如果棋盘大小小于5x5，直接判断为失败
else:
if n % 2 == 1: # 如果棋盘大小是奇数
if (p + q) % 2 == 0:
print("success") # 如果起始位置的坐标和为偶数，可以成功
else:
print("fail") # 否则失败
else:
print("success") # 如果棋盘大小是偶数，总是可以成功