引言
Futoshiki（不等号数独）是一种起源于日本的逻辑谜题。与标准数独不同，Futoshiki 在 n×n 的棋盘中加入了不等号约束（> 和 <），要求相邻格子之间满足大小关系。本文将用 Java 实现一个完整的 Futoshiki 求解器，核心采用约束传播（Constraint Propagation）与拓扑排序（Topological Sort）来高效求解。
核心算法思路
1. 问题建模
Futoshiki 的约束包括：
– 每行、每列必须恰好包含 1~n 各一次（拉丁方约束）
– 相邻格子间的不等号约束（如 A > B 表示 A 的值必须大于 B）
2. 约束传播
为每个空格维护候选数集合。通过以下规则排除：
– 行/列排除：同行/列已出现的数字不可再用
– 不等号传播：若 A > B，则 A 的候选数必须大于 B 的候选数最小值；B 的候选数必须小于 A 的候选数最大值
3. 拓扑排序检测环路
若不等号约束形成环路（如 A > B > C > A），则谜题无解。可通过构建有向图并检测环路来提前排除矛盾状态。
Java 完整实现
import java.util.*;
/**
* Futoshiki（不等号数独）求解器
* 使用约束传播 + 拓扑排序环路检测 + 回溯搜索
*/
public class FutoshikiSolver {
private int n;
private int[][] grid; // 0表示空格
private boolean[][][] candidates; // candidates[r][c][v]
// 不等号约束: inequalities[r][c] 存储从(r,c)出发的约束
// 每个约束为 int[]{nr, nc, type}, type=1 表示 grid[r][c] > grid[nr][nc], type=-1 表示 <
private List<int[]>[][] inequalities;
public FutoshikiSolver(int n) {
this.n = n;
this.grid = new int[n][n];
this.candidates = new boolean[n][n][n + 1];
this.inequalities = new ArrayList[n][n];
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
grid[r][c] = 0;
for (int v = 1; v <= n; v++) candidates[r][c][v] = true;
inequalities[r][c] = new ArrayList<>();
}
}
}
public void setCell(int r, int c, int v) {
if (v >= 1 && v <= n) {
grid[r][c] = v;
for (int i = 0; i < n; i++) {
candidates[r][i][v] = false;
candidates[i][c][v] = false;
}
}
}
/**
* 添加不等号约束
* @param type 1表示(r1,c1)>(r2,c2), -1表示(r1,c1)<(r2,c2)
*/
public void addInequality(int r1, int c1, int r2, int c2, int type) {
inequalities[r1][c1].add(new int[]{r2, c2, type});
inequalities[r2][c2].add(new int[]{r1, c1, -type});
}
/**
* 根据不等号约束排除候选数
*/
private boolean propagateInequalities() {
boolean changed = false;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] != 0) continue;
for (int[] ineq : inequalities[r][c]) {
int nr = ineq[0], nc = ineq[1], type = ineq[2];
// type=1: grid[r][c] > grid[nr][nc]
// type=-1: grid[r][c] < grid[nr][nc]
int otherMin = getMinCandidate(nr, nc);
int otherMax = getMaxCandidate(nr, nc);
if (type == 1) {
// 当前格必须大于对方，排除 <= otherMax 的候选值
for (int v = 1; v <= otherMax; v++) {
if (candidates[r][c][v]) {
candidates[r][c][v] = false;
changed = true;
}
}
} else {
// 当前格必须小于对方，排除 >= otherMin 的候选值
for (int v = otherMin; v <= n; v++) {
if (candidates[r][c][v]) {
candidates[r][c][v] = false;
changed = true;
}
}
}
}
}
}
return changed;
}
private int getMinCandidate(int r, int c) {
if (grid[r][c] > 0) return grid[r][c];
for (int v = 1; v <= n; v++) {
if (candidates[r][c][v]) return v;
}
return n + 1;
}
private int getMaxCandidate(int r, int c) {
if (grid[r][c] > 0) return grid[r][c];
for (int v = n; v >= 1; v--) {
if (candidates[r][c][v]) return v;
}
return 0;
}
/**
* 检测不等号约束图中是否存在环路
* 若存在环路则无解
*/
private boolean hasCycle() {
// 为每个未填格子建立节点，进行拓扑排序
// 简化：仅对涉及未填格子的约束建图
Map<String, Integer> nodeId = new HashMap<>();
List<String> nodes = new ArrayList<>();
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0) {
String key = r + "," + c;
nodeId.put(key, nodes.size());
nodes.add(key);
}
}
}
int m = nodes.size();
if (m == 0) return false;
List<Integer>[] graph = new ArrayList[m];
int[] inDegree = new int[m];
for (int i = 0; i < m; i++) graph[i] = new ArrayList<>();
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
for (int[] ineq : inequalities[r][c]) {
int nr = ineq[0], nc = ineq[1], type = ineq[2];
if (grid[r][c] == 0 && grid[nr][nc] == 0) {
String from = r + "," + c;
String to = nr + "," + nc;
// type=1: from > to, 即 to -> from 的有向边（to要先确定上限）
// 实际上我们建"必须小于"的边
if (type == 1) {
// from > to, 所以 to 的候选值影响 from 的下界
// 简化为：to 必须在 from 之前考虑
int u = nodeId.get(to);
int v = nodeId.get(from);
graph[u].add(v);
inDegree[v]++;
} else {
int u = nodeId.get(from);
int v = nodeId.get(to);
graph[u].add(v);
inDegree[v]++;
}
}
}
}
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < m; i++) {
if (inDegree[i] == 0) q.add(i);
}
int count = 0;
while (!q.isEmpty()) {
int u = q.poll();
count++;
for (int v : graph[u]) {
inDegree[v]--;
if (inDegree[v] == 0) q.add(v);
}
}
return count != m; // 若无法遍历所有节点，说明有环
}
private boolean applyNakedSingles() {
boolean changed = false;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] != 0) continue;
int count = 0, val = -1;
for (int v = 1; v <= n; v++) {
if (candidates[r][c][v]) {
count++;
val = v;
}
}
if (count == 1) {
fillCell(r, c, val);
changed = true;
} else if (count == 0) {
return false; // 矛盾
}
}
}
return changed;
}
private void fillCell(int r, int c, int v) {
grid[r][c] = v;
for (int i = 0; i < n; i++) {
candidates[r][i][v] = false;
candidates[i][c][v] = false;
}
}
private boolean propagate() {
while (true) {
boolean changed = false;
if (applyNakedSingles()) changed = true;
if (!isValid()) return false;
if (propagateInequalities()) changed = true;
if (!isValid()) return false;
if (hasCycle()) return false;
if (!changed) break;
}
return true;
}
private boolean isValid() {
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0) {
boolean has = false;
for (int v = 1; v <= n; v++) {
if (candidates[r][c][v]) {
has = true;
break;
}
}
if (!has) return false;
}
}
}
return true;
}
private boolean isComplete() {
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0) return false;
}
}
return true;
}
private boolean solve() {
if (isComplete()) return true;
int[] best = null;
int minCount = n + 1;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] != 0) continue;
int count = 0;
for (int v = 1; v <= n; v++) {
if (candidates[r][c][v]) count++;
}
if (count < minCount) {
minCount = count;
best = new int[]{r, c};
}
}
}
if (best == null || minCount == 0) return false;
int r = best[0], c = best[1];
int[][] gridBackup = new int[n][n];
boolean[][][] candBackup = new boolean[n][n][n + 1];
for (int i = 0; i < n; i++) {
System.arraycopy(grid[i], 0, gridBackup[i], 0, n);
for (int j = 0; j < n; j++) {
System.arraycopy(candidates[i][j], 0, candBackup[i][j], n + 1);
}
}
for (int v = 1; v <= n; v++) {
if (!candidates[r][c][v]) continue;
fillCell(r, c, v);
if (propagate() && solve()) return true;
// 恢复
for (int i = 0; i < n; i++) {
System.arraycopy(gridBackup[i], 0, grid[i], 0, n);
for (int j = 0; j < n; j++) {
System.arraycopy(candBackup[i][j], 0, candidates[i][j], n + 1);
}
}
}
return false;
}
public boolean solvePuzzle() {
if (!propagate()) return false;
return solve();
}
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 static void main(String[] args) {
FutoshikiSolver solver = new FutoshikiSolver(5);
// 预填部分数字
solver.setCell(0, 0, 1);
solver.setCell(4, 4, 5);
// 添加不等号约束: (r1,c1) > (r2,c2)
solver.addInequality(0, 0, 0, 1, 1); // (0,0) > (0,1)
solver.addInequality(1, 2, 1, 1, 1); // (1,2) > (1,1)
solver.addInequality(2, 3, 2, 2, 1); // (2,3) > (2,2)
solver.addInequality(3, 1, 3, 0, -1); // (3,1) < (3,0)
System.out.println("初始棋盘：");
solver.printGrid();
long start = System.currentTimeMillis();
if (solver.solvePuzzle()) {
System.out.println("\n求解结果：");
solver.printGrid();
System.out.println("\n耗时：" + (System.currentTimeMillis() - start) + " ms");
} else {
System.out.println("无解！");
}
}
}
算法复杂度分析
- 约束传播：每次循环 O(n² × k)，k 为不等号数量。
- 拓扑排序检测：O(n² + k)。
- 回溯搜索：最坏 O(n^(n²))，但约束传播大幅剪枝。
- 空间复杂度：O(n³ + k)。
扩展思考
- 不等号链推导：A > B > C 可进一步推出 A > C，增强传播能力。
- X-Wing / Swordfish：数独中的高级技巧同样适用于 Futoshiki 的行/列约束。
- 随机生成：先生成完整拉丁方，再随机添加不等号约束并挖空，确保唯一解。
小结
本文通过 Java 实现了 Futoshiki 求解器，核心采用约束传播、拓扑排序环路检测与回溯搜索。不等号约束的加入使得问题比标准数独更具挑战性，代码中展示了如何将图论算法（拓扑排序）融入逻辑谜题求解。
