引言
八皇后问题是由国际象棋棋手马克斯·贝塞尔于1848年提出的经典组合优化问题：在8×8的国际象棋棋盘上放置8个皇后，使得任意两个皇后都不能在同一行、同一列或同一对角线上互相攻击。该问题共有92个不同的解。传统的回溯法可以系统地枚举所有解，但当棋盘规模增大时，搜索空间呈指数级增长。本文将使用Java实现基于遗传算法（Genetic Algorithm, GA）的八皇后问题求解器，通过模拟生物进化过程高效搜索可行解。
核心算法思路
1. 编码方案
采用一维数组编码：第i个元素表示第i行皇后所在的列号。例如[0, 4, 7, 5, 2, 6, 1, 3]表示第0行皇后在第0列，第1行皇后在第4列，以此类推。这种编码天然保证每行恰好一个皇后，将搜索空间从8^8缩小到8!。
2. 适应度函数设计
适应度函数衡量个体接近解的程度。定义冲突数为互相攻击的皇后对数（范围为0到28）。适应度值为：fitness = 28 - conflicts。当fitness=28时，即为完美解。
3. 遗传算子
- 选择：采用锦标赛选择（Tournament Selection），每次随机选取k个个体，选择其中适应度最高的进入下一代；
- 交叉：使用部分映射交叉（PMX, Partially Mapped Crossover），保持排列的合法性；
- 变异：采用交换变异（Swap Mutation），随机交换两个位置的列号。
4. 精英保留策略
每代保留最优个体直接进入下一代，防止优秀基因在交叉和变异中丢失。
完整Java实现
import java.util.*;
/**
* 八皇后问题求解器：遗传算法进化搜索
*/
public class NQueensGA {
private static final int N = 8;
private static final int POP_SIZE = 100;
private static final int MAX_GENERATIONS = 10000;
private static final double CROSSOVER_RATE = 0.85;
private static final double MUTATION_RATE = 0.15;
private static final int TOURNAMENT_SIZE = 5;
private static final int ELITE_COUNT = 2;
private Random random;
private List<Individual> population;
private int generation;
private Individual bestEver;
public NQueensGA() {
this.random = new Random();
this.population = new ArrayList<>();
initializePopulation();
}
/**
* 初始化种群：随机生成合法排列
*/
private void initializePopulation() {
for (int i = 0; i < POP_SIZE; i++) {
int[] chromosome = new int[N];
List<Integer> cols = new ArrayList<>();
for (int j = 0; j < N; j++) cols.add(j);
Collections.shuffle(cols, random);
for (int j = 0; j < N; j++) chromosome[j] = cols.get(j);
population.add(new Individual(chromosome));
}
bestEver = Collections.max(population, Comparator.comparingInt(a -> a.fitness));
}
/**
* 个体类：包含染色体和适应度
*/
static class Individual {
int[] chromosome;
int fitness;
int conflicts;
Individual(int[] chromo) {
this.chromosome = chromo.clone();
calculateFitness();
}
/**
* 计算适应度：28 - 冲突对数
*/
void calculateFitness() {
this.conflicts = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
// 同一列
if (chromosome[i] == chromosome[j]) conflicts++;
// 同一对角线
if (Math.abs(chromosome[i] - chromosome[j]) == Math.abs(i - j)) conflicts++;
}
}
this.fitness = 28 - conflicts;
}
Individual copy() {
return new Individual(chromosome);
}
@Override
public String toString() {
return "Fitness=" + fitness + ", Conflicts=" + conflicts +
", Chromo=" + Arrays.toString(chromosome);
}
}
/**
* 锦标赛选择
*/
private Individual tournamentSelection() {
Individual best = null;
for (int i = 0; i < TOURNAMENT_SIZE; i++) {
Individual candidate = population.get(random.nextInt(POP_SIZE));
if (best == null || candidate.fitness > best.fitness) {
best = candidate;
}
}
return best.copy();
}
/**
* 部分映射交叉（PMX）
*/
private Individual[] pmxCrossover(Individual p1, Individual p2) {
if (random.nextDouble() > CROSSOVER_RATE) {
return new Individual[]{p1.copy(), p2.copy()};
}
int[] c1 = new int[N];
int[] c2 = new int[N];
Arrays.fill(c1, -1);
Arrays.fill(c2, -1);
// 选择交叉点
int point1 = random.nextInt(N);
int point2 = random.nextInt(N);
if (point1 > point2) {
int tmp = point1; point1 = point2; point2 = tmp;
}
// 复制映射段
for (int i = point1; i <= point2; i++) {
c1[i] = p2.chromosome[i];
c2[i] = p1.chromosome[i];
}
// 填充剩余位置，解决冲突
fillPmxChild(c1, p1.chromosome, point1, point2);
fillPmxChild(c2, p2.chromosome, point1, point2);
return new Individual[]{new Individual(c1), new Individual(c2)};
}
private void fillPmxChild(int[] child, int[] parent, int p1, int p2) {
Set<Integer> used = new HashSet<>();
for (int i = p1; i <= p2; i++) used.add(child[i]);
for (int i = 0; i < N; i++) {
if (i >= p1 && i <= p2) continue;
int val = parent[i];
while (used.contains(val)) {
// 查找映射
for (int j = p1; j <= p2; j++) {
if (child[j] == val) {
val = parent[j];
break;
}
}
}
child[i] = val;
used.add(val);
}
}
/**
* 交换变异
*/
private void mutate(Individual ind) {
if (random.nextDouble() > MUTATION_RATE) return;
int idx1 = random.nextInt(N);
int idx2 = random.nextInt(N);
int tmp = ind.chromosome[idx1];
ind.chromosome[idx1] = ind.chromosome[idx2];
ind.chromosome[idx2] = tmp;
ind.calculateFitness();
}
/**
* 进化一代
*/
private void evolveOneGeneration() {
List<Individual> newPopulation = new ArrayList<>();
// 精英保留
population.sort((a, b) -> b.fitness - a.fitness);
for (int i = 0; i < ELITE_COUNT && i < population.size(); i++) {
newPopulation.add(population.get(i).copy());
}
// 生成新个体
while (newPopulation.size() < POP_SIZE) {
Individual parent1 = tournamentSelection();
Individual parent2 = tournamentSelection();
Individual[] children = pmxCrossover(parent1, parent2);
mutate(children[0]);
mutate(children[1]);
newPopulation.add(children[0]);
if (newPopulation.size() < POP_SIZE) {
newPopulation.add(children[1]);
}
}
population = newPopulation;
generation++;
// 更新历史最优
Individual currentBest = Collections.max(population, Comparator.comparingInt(a -> a.fitness));
if (currentBest.fitness > bestEver.fitness) {
bestEver = currentBest.copy();
}
}
/**
* 运行遗传算法直到找到解或达到最大代数
*/
public Individual solve() {
long startTime = System.currentTimeMillis();
while (generation < MAX_GENERATIONS) {
evolveOneGeneration();
if (bestEver.fitness == 28) {
long elapsed = System.currentTimeMillis() - startTime;
System.out.println("Solution found at generation " + generation +
" in " + elapsed + "ms");
return bestEver;
}
if (generation % 500 == 0) {
System.out.println("Gen " + generation + ": Best fitness = " +
bestEver.fitness + ", Conflicts = " + bestEver.conflicts);
}
}
System.out.println("Max generations reached. Best fitness = " + bestEver.fitness);
return bestEver;
}
/**
* 可视化打印棋盘
*/
public void printBoard(Individual solution) {
System.out.println("\nSolution: " + Arrays.toString(solution.chromosome));
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
System.out.print(solution.chromosome[row] == col ? "Q " : ". ");
}
System.out.println();
}
}
/**
* 统计并打印所有不同解（运行多次）
*/
public void findAllSolutions(int attempts) {
Set<String> uniqueSolutions = new HashSet<>();
int totalGenerations = 0;
for (int i = 0; i < attempts; i++) {
NQueensGA ga = new NQueensGA();
Individual sol = ga.solve();
if (sol.fitness == 28) {
String key = Arrays.toString(sol.chromosome);
uniqueSolutions.add(key);
totalGenerations += ga.generation;
}
}
System.out.println("\n=== Summary ===");
System.out.println("Attempts: " + attempts);
System.out.println("Unique solutions found: " + uniqueSolutions.size());
System.out.println("Avg generations per solution: " +
(uniqueSolutions.size() > 0 ? totalGenerations / uniqueSolutions.size() : 0));
}
public static void main(String[] args) {
// 单次求解
System.out.println("=== Single Run ===");
NQueensGA ga = new NQueensGA();
Individual solution = ga.solve();
ga.printBoard(solution);
// 多次运行寻找不同解
System.out.println("\n=== Finding Multiple Solutions ===");
ga.findAllSolutions(50);
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 适应度计算 | O(N²) | O(1) |
| 锦标赛选择 | O(K) = O(1) | O(1) |
| PMX交叉 | O(N²) | O(N) |
| 交换变异 | O(1) | O(1) |
| 单代进化 | O(P × N²) | O(P × N) |
| 完整求解 | O(G × P × N²) | O(P × N) |
其中N=8为皇后数量，P=100为种群大小，G为实际进化代数（通常几百到几千代），K=5为锦标赛规模。
策略总结
本文通过遗传算法求解八皇后问题，核心设计要点包括：
- 排列编码：使用一维数组编码，天然满足每行一个皇后的约束，将搜索空间从16,777,216缩小到40,320；
- 冲突最小化适应度：以28减去互相攻击的皇后对数作为适应度，目标明确且计算高效；
- PMX交叉算子：保持排列合法性，避免传统交叉产生的重复列号；
- 精英保留：每代保留最优个体，确保优秀基因不会丢失；
- 交换变异：维持排列性质的同时引入局部扰动，帮助跳出局部最优。
遗传算法的优势在于不依赖问题的梯度信息，通过种群并行搜索多个区域。在八皇后问题上，通常能在数百代内找到最优解，平均耗时仅几十毫秒。相比回溯法的系统性枚举，遗传算法更适合大规模N皇后问题（如N=100以上），此时回溯法已无法在合理时间内求解。
