引言
拉丁方（Latin Square）是一种古老的数学谜题，其规则要求在一个 n×n 的方阵中填入 n 个不同的符号（通常为数字 1~n），使得每一行和每一列都恰好包含每个符号一次。拉丁方在实验设计、密码学和统计学中有着广泛应用。本文将用 Java 实现一个完整的拉丁方求解器，核心采用回溯搜索（Backtracking）配合约束传播（Constraint Propagation）来高效填充空格。
核心算法思路
1. 问题建模
将拉丁方视为一个约束满足问题（CSP）：
– 变量：每个空格 (r, c) 待填的数字
– 定义域：{1, 2, ..., n} 中尚未在该行/列出现的数字
– 约束：同一行、同一列数字不重复
2. 回溯搜索
从第一个空格开始，依次尝试定义域中的候选值。若当前选择导致后续空格无解，则回退并尝试下一个候选值。这是求解拉丁方最直观的思路。
3. 约束传播（MRV 启发式）
为了加速搜索，引入最小剩余值（Minimum Remaining Values, MRV）启发式：每次优先选择可选值最少的空格进行填充。这样可以尽早暴露矛盾，减少无效搜索分支。
Java 完整实现
import java.util.*;
/**
* 拉丁方求解器
* 使用回溯搜索 + MRV启发式 + 约束传播
*/
public class LatinSquareSolver {
private int n;
private int[][] grid;
private boolean[][] rowUsed; // rowUsed[r][v] 表示第r行是否已使用数字v
private boolean[][] colUsed; // colUsed[c][v] 表示第c列是否已使用数字v
private boolean solved;
public LatinSquareSolver(int n) {
this.n = n;
this.grid = new int[n][n];
this.rowUsed = new boolean[n][n + 1];
this.colUsed = new boolean[n][n + 1];
this.solved = false;
// 初始化为0表示空格
for (int i = 0; i < n; i++) {
Arrays.fill(grid[i], 0);
}
}
/**
* 预填充某些格子（可选）
*/
public void setCell(int row, int col, int value) {
if (value < 1 || value > n) return;
grid[row][col] = value;
rowUsed[row][value] = true;
colUsed[col][value] = true;
}
/**
* 获取某个空格的可选值列表（约束传播）
*/
private List<Integer> getCandidates(int row, int col) {
List<Integer> candidates = new ArrayList<>();
for (int v = 1; v <= n; v++) {
if (!rowUsed[row][v] && !colUsed[col][v]) {
candidates.add(v);
}
}
return candidates;
}
/**
* 使用MRV启发式找到下一个最优空格
* @return int[]{row, col}, 若无空格返回null
*/
private int[] selectNextCell() {
int minCandidates = n + 1;
int[] bestCell = null;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0) {
int count = 0;
for (int v = 1; v <= n; v++) {
if (!rowUsed[r][v] && !colUsed[c][v]) {
count++;
}
}
if (count < minCandidates) {
minCandidates = count;
bestCell = new int[]{r, c};
if (count == 0) return bestCell; // 死胡同，提前返回
}
}
}
}
return bestCell;
}
/**
* 核心回溯求解
*/
private boolean solve() {
int[] cell = selectNextCell();
if (cell == null) {
return true; // 所有格子已填满
}
int r = cell[0], c = cell[1];
List<Integer> candidates = getCandidates(r, c);
for (int v : candidates) {
// 做出选择
grid[r][c] = v;
rowUsed[r][v] = true;
colUsed[c][v] = true;
if (solve()) {
return true;
}
// 撤销选择（回溯）
grid[r][c] = 0;
rowUsed[r][v] = false;
colUsed[c][v] = false;
}
return false; // 所有候选值均失败
}
public boolean solvePuzzle() {
solved = solve();
return solved;
}
public void printGrid() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.printf("%2d ", grid[i][j]);
}
System.out.println();
}
}
public int[][] getGrid() {
return grid;
}
public static void main(String[] args) {
// 示例：求解5阶拉丁方，预填部分数字
LatinSquareSolver solver = new LatinSquareSolver(5);
// 预填一些格子作为初始约束
solver.setCell(0, 0, 1);
solver.setCell(1, 2, 3);
solver.setCell(3, 1, 5);
System.out.println("初始状态：");
solver.printGrid();
System.out.println("\n求解结果：");
long start = System.currentTimeMillis();
if (solver.solvePuzzle()) {
solver.printGrid();
System.out.println("\n耗时：" + (System.currentTimeMillis() - start) + " ms");
} else {
System.out.println("无解！");
}
}
}
算法复杂度分析
- 时间复杂度：最坏情况下为 O(n^(n²))，但 MRV 启发式和约束传播可大幅剪枝。对于 n ≤ 10 的拉丁方，通常在毫秒级求解。
- 空间复杂度：O(n²)，用于存储格子状态和行列使用标记。
扩展思考
- 唯一解判定：可在找到第一个解后，通过继续搜索判断是否存在多解。若需要唯一解，需在生成谜题时确保预填数字足够。
- 数独对比：数独可视为拉丁方的扩展，额外增加了宫（block）约束。理解了拉丁方的求解逻辑，再学习数独的 Dancing Links 算法会事半功倍。
- 随机生成：先生成完整拉丁方，再逐步挖空格子，每次挖空后检查是否仍保持唯一解。
小结
本文通过 Java 实现了拉丁方求解器，核心运用了回溯搜索 + MRV 启发式 + 约束传播三大技术。代码结构清晰，注释详尽，可直接运行并扩展为更复杂的约束满足问题求解器。
