马踏棋盘（Knight’s Tour）是国际象棋中的经典数学谜题：给定一个 n × n 的棋盘，骑士从任意起始位置出发，按照”日”字形移动规则（横向走两格纵向走一格，或横向走一格纵向走两格），要求恰好访问棋盘上的每一个格子一次，且每个格子只能访问一次。如果能够最终回到起点，则称为闭合巡游（Closed Tour）；否则称为开放巡游（Open Tour）。
本文将用 Java 完整实现马踏棋盘问题的求解，讲解朴素的回溯搜索算法，以及 Warnsdorff 启发式规则如何大幅提升搜索效率，最后给出支持可视化输出的工程级代码。
问题分析与建模
骑士在国际象棋中的走法固定为 8 种可能方向。设当前位置为 (row, col)，则下一步的候选位置为：
(row-2, col-1), (row-2, col+1), (row-1, col-2), (row-1, col+2),
(row+1, col-2), (row+1, col+2), (row+2, col-1), (row+2, col+1)
我们将棋盘建模为二维整数数组 board[n][n]，初始值为 0 表示未访问。每走一步，将当前步数（从 1 开始）写入对应格子。当步数达到 n × n 时，即找到一组可行解。
算法一：朴素回溯搜索
回溯法的核心思想是深度优先遍历解空间树：从起点出发，枚举所有合法的下一步，递归尝试每一种可能；若某条路径走不通（死胡同），则撤销当前选择（回溯），尝试其他分支。
/**
* 朴素回溯法求解马踏棋盘
* 时间复杂度：O(8^(n^2))，指数级，仅适用于小棋盘
*/
public class KnightTourBacktracking {
// 骑士的8种移动方向：{行偏移, 列偏移}
private static final int[][] MOVES = {
{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
{1, -2}, {1, 2}, {2, -1}, {2, 1}
};
private int n; // 棋盘大小
private int[][] board; // 棋盘状态，0表示未访问
private int totalSteps; // 总步数 n*n
private boolean found; // 是否已找到解
public KnightTourBacktracking(int n) {
this.n = n;
this.board = new int[n][n];
this.totalSteps = n * n;
this.found = false;
}
/**
* 从指定起点开始搜索
* @param startRow 起始行
* @param startCol 起始列
* @return 若找到解返回true，board数组中存放完整路径
*/
public boolean solve(int startRow, int startCol) {
// 初始化棋盘
for (int i = 0; i < n; i++) {
java.util.Arrays.fill(board[i], 0);
}
found = false;
// 从第1步开始深度优先搜索
backtrack(startRow, startCol, 1);
return found;
}
/**
* 回溯核心方法
* @param row 当前行
* @param col 当前列
* @param step 当前步数（从1开始计数）
*/
private void backtrack(int row, int col, int step) {
// 记录当前步数到棋盘
board[row][col] = step;
// 终止条件：已走满所有格子
if (step == totalSteps) {
found = true;
return;
}
// 枚举8个候选方向
for (int[] move : MOVES) {
int nextRow = row + move[0];
int nextCol = col + move[1];
// 剪枝：检查边界和是否已访问
if (isValid(nextRow, nextCol)) {
backtrack(nextRow, nextCol, step + 1);
if (found) {
return; // 已找到解，不再继续搜索
}
}
}
// 回溯：撤销当前选择，恢复棋盘状态
board[row][col] = 0;
}
/**
* 检查坐标是否合法且未访问
*/
private boolean isValid(int row, int col) {
return row >= 0 && row < n && col >= 0 && col < n && board[row][col] == 0;
}
/**
* 打印棋盘，展示骑士的行走路线
*/
public void printBoard() {
int maxDigits = String.valueOf(totalSteps).length();
String format = "%" + maxDigits + "d ";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.printf(format, board[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
// 5x5 棋盘为例，从左上角出发
KnightTourBacktracking solver = new KnightTourBacktracking(5);
long start = System.currentTimeMillis();
boolean solved = solver.solve(0, 0);
long cost = System.currentTimeMillis() - start;
if (solved) {
System.out.println("找到解（耗时 " + cost + " ms）：");
solver.printBoard();
} else {
System.out.println("无解（耗时 " + cost + " ms）");
}
}
}
朴素回溯法的时间复杂度高达 O(8^(n²))，因为每步最多有 8 种选择。对于 5 × 5 棋盘尚可在毫秒级求解，但 8 × 8 标准棋盘往往需要数小时甚至更久。这正是我们需要引入启发式策略的原因。
算法二：Warnsdorff 启发式规则
1823 年，数学家 H.C. von Warnsdorff 提出了一条简单而高效的启发式规则：每一步都选择”后续可走步数最少”的那个方向。直观理解是：优先走那些”选择余地小”的格子（如角落、边缘），把自由度高的中心位置留到后期，从而减少过早陷入死胡同的概率。
这一策略将 8 × 8 棋盘的求解时间从数小时降低到毫秒级，且通常无需回溯即可直接构造出解。
Warnsdorff 规则的核心步骤
- 从当前位置出发，枚举所有合法的下一步候选位置；
- 对每个候选位置，计算其合法的后续可走步数（degree）；
- 选择 degree 最小的候选位置作为下一步；
- 若存在多个相同最小 degree 的候选，引入 secondary heuristic（如到棋盘中心距离的平方）进行打破平局。
import java.util.*;
/**
* Warnsdorff 启发式规则求解马踏棋盘
* 时间复杂度：O(n^2 * log n)，实际运行极快
*/
public class KnightTourWarnsdorff {
private static final int[][] MOVES = {
{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
{1, -2}, {1, 2}, {2, -1}, {2, 1}
};
private int n;
private int[][] board;
private int totalSteps;
public KnightTourWarnsdorff(int n) {
this.n = n;
this.board = new int[n][n];
this.totalSteps = n * n;
}
public boolean solve(int startRow, int startCol) {
for (int i = 0; i < n; i++) {
Arrays.fill(board[i], 0);
}
return warnsdorff(startRow, startCol);
}
/**
* Warnsdorff 主算法
*/
private boolean warnsdorff(int startRow, int startCol) {
int row = startRow;
int col = startCol;
for (int step = 1; step <= totalSteps; step++) {
board[row][col] = step;
if (step == totalSteps) {
return true; // 完成巡游
}
// 获取所有合法下一步并按 Warnsdorff 规则排序
List<Candidate> candidates = getSortedCandidates(row, col);
if (candidates.isEmpty()) {
return false; // 陷入死胡同，无解
}
// 选择最优候选（degree 最小）
Candidate best = candidates.get(0);
row = best.row;
col = best.col;
}
return true;
}
/**
* 获取当前位置的所有合法下一步，并按 Warnsdorff 规则排序
*/
private List<Candidate> getSortedCandidates(int row, int col) {
List<Candidate> list = new ArrayList<>();
for (int[] move : MOVES) {
int nr = row + move[0];
int nc = col + move[1];
if (isValid(nr, nc)) {
int degree = countValidMoves(nr, nc);
// 距离中心的平方距离作为平局打破策略
double dist = distanceToCenter(nr, nc);
list.add(new Candidate(nr, nc, degree, dist));
}
}
// 排序：degree 升序，degree 相同时 dist 降序（优先远离中心）
list.sort(Comparator
.comparingInt((Candidate c) -> c.degree)
.thenComparing((Candidate c) -> -c.distToCenter));
return list;
}
/**
* 计算指定位置有多少个合法的后续可走步数
*/
private int countValidMoves(int row, int col) {
int count = 0;
for (int[] move : MOVES) {
int nr = row + move[0];
int nc = col + move[1];
if (isValid(nr, nc)) {
count++;
}
}
return count;
}
/**
* 计算到棋盘中心的平方距离
*/
private double distanceToCenter(int row, int col) {
double center = (n - 1) / 2.0;
return Math.pow(row - center, 2) + Math.pow(col - center, 2);
}
private boolean isValid(int row, int col) {
return row >= 0 && row < n && col >= 0 && col < n && board[row][col] == 0;
}
/**
* 候选位置数据结构
*/
private static class Candidate {
final int row;
final int col;
final int degree; // 后续可走步数
final double distToCenter; // 到中心的平方距离
Candidate(int row, int col, int degree, double distToCenter) {
this.row = row;
this.col = col;
this.degree = degree;
this.distToCenter = distToCenter;
}
}
public void printBoard() {
int maxDigits = String.valueOf(totalSteps).length();
String format = "%" + maxDigits + "d ";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.printf(format, board[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
// 标准 8x8 国际象棋棋盘
KnightTourWarnsdorff solver = new KnightTourWarnsdorff(8);
long start = System.currentTimeMillis();
boolean solved = solver.solve(0, 0);
long cost = System.currentTimeMillis() - start;
if (solved) {
System.out.println("8x8 马踏棋盘解（Warnsdorff，耗时 " + cost + " ms）：");
solver.printBoard();
} else {
System.out.println("未找到解（耗时 " + cost + " ms）");
}
}
}
算法三：支持闭合巡游的增强回溯
闭合巡游要求最后一步恰好能跳回起点。我们可以在回溯的基础上增加闭合条件判断。由于 Warnsdorff 规则通常直接构造出开放巡游，若需要闭合巡游，一种有效策略是：先用 Warnsdorff 得到开放巡游，再检查最后位置与起点是否构成合法骑士步；若不满足，则以回溯方式微调路径。
下面给出一个简洁的闭合巡游检测与搜索框架：
/**
* 检查两个位置是否为合法的骑士移动关系
*/
private boolean isKnightMove(int r1, int c1, int r2, int c2) {
int dr = Math.abs(r1 - r2);
int dc = Math.abs(c1 - c2);
return (dr == 2 && dc == 1) || (dr == 1 && dc == 2);
}
/**
* 在回溯求解过程中加入闭合条件剪枝
* 当 step == totalSteps 时，额外检查能否跳回起点
*/
private void backtrackClosed(int row, int col, int step, int startRow, int startCol) {
board[row][col] = step;
if (step == totalSteps) {
// 闭合条件：最后位置必须能跳回起点
if (isKnightMove(row, col, startRow, startCol)) {
found = true;
}
board[row][col] = 0; // 注意：即使满足也要回溯清理
return;
}
// 获取按 Warnsdorff 排序的候选，优先搜索更优分支
List<int[]> candidates = getWarnsdorffCandidates(row, col);
for (int[] cand : candidates) {
backtrackClosed(cand[0], cand[1], step + 1, startRow, startCol);
if (found) return;
}
board[row][col] = 0; // 回溯
}
复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 朴素回溯 | O(8^(n²)) | O(n²) | 理解原理，n ≤ 5 |
| Warnsdorff 启发式 | O(n² log n) | O(n²) | 实际求解，n ≤ 1000 |
| 增强回溯（闭合巡游） | O(8^(n²))（最坏） | O(n²) | 寻找特殊结构解 |
Warnsdorff 规则之所以高效，是因为它将解空间树的盲目遍历转化为贪心构造，每一步的局部最优选择大幅降低了分支因子。虽然它不能保证 100% 找到解（存在极少数反例），但在实际应用中成功率极高，是工程实现的首选方案。
完整项目结构与运行指南
knight-tour/
├── src/
│ ├── KnightTourBacktracking.java # 朴素回溯教学版
│ ├── KnightTourWarnsdorff.java # Warnsdorff 高效版
│ └── KnightTourClosed.java # 闭合巡游检测版（基于回溯扩展）
└── README.md
编译与运行：
javac src/KnightTourWarnsdorff.java
java -cp src KnightTourWarnsdorff
总结
马踏棋盘问题虽然规则简单，却完美展现了搜索算法与启发式策略的结合力量。朴素的回溯法告诉我们问题的本质复杂度，而 Warnsdorff 规则则证明了：一个好的启发式策略，能够将指数级难题转化为多项式时间的可行问题。在实际工程开发中，面对组合爆炸类的 NP 难题，设计合理的剪枝策略与启发式规则，往往是比暴力搜索更务实的选择。
