如何在多线程求解八皇后问题时，找到首个解后终止所有线程？

我正在开发一个解决八皇后问题的程序。程序会提示用户输入棋盘维度n，调用HillClimbingSearch类的runSearch()方法计算解并输出结果。为提升效率，我用100个线程并发执行runSearch()方法，但目前程序会输出所有100个线程各自找到的解。我需要实现仅输出第一个找到解的线程的结果，且只能修改Main类或runSearch()方法，特此求助。

以下是我的代码：

Main类代码 #

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int n = 0;
        try (Scanner s = new Scanner(System.in)) {
            while (true) {
                System.out.println("Enter the number of Queens :");
                n = s.nextInt();
                if (n == 2 || n == 3) {
                    System.out.println("No Solution possible for " + n + " Queens. Please enter another number");
                } else {
                    break;
                }
            }
        }
        long timestamp1 = System.currentTimeMillis();

        System.out.println("Solution to " + n + " queens using hill climbing search:");

        // 创建100个线程用于爬山搜索
        ThreadGroup threadGroup = new ThreadGroup("HillClimbingGroup");

        // 创建100个线程用于爬山搜索
        for (int i = 0; i < 100; i++) {
            HillClimbingSearch h = new HillClimbingSearch(n);
            Thread t = new Thread(threadGroup, h);
            t.start();
            h.runSearch();
        }

        // 等待所有线程完成
        while (threadGroup.activeCount() > 0) {
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        // 输出执行时间
        long timestamp2 = System.currentTimeMillis();
        long timeDiff = timestamp2 - timestamp1;
        System.out.println("Execution Time: " + timeDiff + " ms");
    }
}

HillClimbingSearch类代码 #

// 基于随机重启爬山法解决N皇后问题的程序
import java.util.Random;

public class HillClimbingSearch extends Thread {
    private int n;
    private int heuristic = 0;
    private int presentHeuristic;
    private NQueen[] finalSolution;

    public HillClimbingSearch(int size) {
        n = size;
        finalSolution = null;
    }

    public NQueen[] getFinalSolution() {
        return finalSolution;
    }

    // 生成随机初始棋盘
    public NQueen[] generateBoard() {
        NQueen[] startBoard = new NQueen[n];
        Random rndm = new Random();
        for (int i = 0; i < n; i++) {
            startBoard[i] = new NQueen(rndm.nextInt(n), i);
        }
        return startBoard;
    }

    // 打印当前棋盘状态
    public void printState(NQueen[] state) {
        // 根据当前棋盘创建临时二维数组
        int[][] tempBoard = new int[n][n];
        for (int i = 0; i < n; i++) {
            // 将皇后位置标记为1
            tempBoard[state[i].getRow()][state[i].getColumn()] = 1;
        }
        System.out.println();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(tempBoard[i][j] + " ");
            }
            System.out.println();
        }
    }

    // 计算当前状态的启发值（冲突数）
    public int findHeuristic(NQueen[] state) {
        int heuristic = 0;
        for (int i = 0; i < state.length; i++) {
            for (int j = i + 1; j < state.length; j++) {
                if (state[i].ifConflict(state[j])) {
                    heuristic++;
                }
            }
        }
        return heuristic;
    }

    // 获取启发值更低的下一个棋盘状态
    public NQueen[] nextBoard(NQueen[] presentBoard) {
        NQueen[] nextBoard = new NQueen[n];
        NQueen[] tmpBoard = new NQueen[n];
        int presentHeuristic = findHeuristic(presentBoard);
        int bestHeuristic = presentHeuristic;
        int tempH;

        // 复制当前棋盘作为最优候选和临时棋盘
        for (int i = 0; i < n; i++) {
            nextBoard[i] = new NQueen(presentBoard[i].getRow(), presentBoard[i].getColumn());
            tmpBoard[i] = nextBoard[i];
        }

        // 遍历每一列
        for (int i = 0; i < n; i++) {
            if (i > 0)
                tmpBoard[i - 1] = new NQueen(presentBoard[i - 1].getRow(), presentBoard[i - 1].getColumn());
            tmpBoard[i] = new NQueen(0, tmpBoard[i].getColumn());

            // 遍历每一行
            for (int j = 0; j < n; j++) {
                // 计算临时棋盘的启发值
                tempH = findHeuristic(tmpBoard);
                // 如果临时棋盘更优，更新最优候选
                if (tempH < bestHeuristic) {
                    bestHeuristic = tempH;
                    for (int k = 0; k < n; k++) {
                        nextBoard[k] = new NQueen(tmpBoard[k].getRow(), tmpBoard[k].getColumn());
                    }
                }
                // 移动当前皇后到下一行
                if (tmpBoard[i].getRow() != n - 1)
                    tmpBoard[i].move();
            }
        }

        // 如果没有找到更优状态，随机生成新棋盘
        if (bestHeuristic == presentHeuristic) {
            nextBoard = generateBoard();
            heuristic = findHeuristic(nextBoard);
        } else
            heuristic = bestHeuristic;
        return nextBoard;
    }

    public void runSearch() {
        NQueen[] presentBoard = generateBoard();
        presentHeuristic = findHeuristic(presentBoard);
        // 循环直到找到解或线程被中断
        while (presentHeuristic != 0 && !Thread.currentThread().isInterrupted()) {
            presentBoard = nextBoard(presentBoard);
            presentHeuristic = findHeuristic(presentBoard);
        }
        if (!Thread.currentThread().isInterrupted()) {
            finalSolution = presentBoard;
            printState(finalSolution);
        }
    }
}

NQueen类代码 #

// N皇后问题的皇后类
public class NQueen {
    private int row;
    private int column;

    public NQueen(int row, int column) {
        this.row = row;
        this.column = column;
    }

    // 将皇后向下移动一行
    public void move() {
        row++;
    }

    // 判断当前皇后与另一皇后是否存在冲突
    public boolean ifConflict(NQueen q) {
        // 检查行或列冲突
        if (row == q.getRow() || column == q.getColumn())
            return true;
        // 检查对角线冲突
        else if (Math.abs(column - q.getColumn()) == Math.abs(row - q.getRow()))
            return true;
        return false;
    }

    public int getRow() {
        return row;
    }

    public int getColumn() {
        return column;
    }
}

解决方案 #

1. 修复Main类的线程执行错误

原代码中启动线程后直接调用h.runSearch()，会导致主线程同步执行该方法，而非由新线程处理。删除这一行：

for (int i = 0; i < 100; i++) {
    HillClimbingSearch h = new HillClimbingSearch(n);
    Thread t = new Thread(threadGroup, h);
    t.start();
    // 删除此行：h.runSearch();
}

2. 修改HillClimbingSearch类实现全局控制

添加线程安全的全局标记，确保只有第一个找到解的线程输出结果，并中断其他线程：

import java.util.concurrent.atomic.AtomicBoolean;

public class HillClimbingSearch extends Thread {
    // 全局标记：是否已找到解，原子类保证线程安全
    private static final AtomicBoolean solutionFound = new AtomicBoolean(false);
    private int n;
    // 其他原有变量保持不变

    public void runSearch() {
        // 已有解则直接返回
        if (solutionFound.get()) {
            return;
        }
        NQueen[] presentBoard = generateBoard();
        presentHeuristic = findHeuristic(presentBoard);
        
        // 循环条件新增解是否已找到的判断
        while (presentHeuristic != 0 && !Thread.currentThread().isInterrupted() && !solutionFound.get()) {
            presentBoard = nextBoard(presentBoard);
            presentHeuristic = findHeuristic(presentBoard);
        }
        
        // 只有第一个成功设置标记的线程执行输出
        if (!Thread.currentThread().isInterrupted() && solutionFound.compareAndSet(false, true)) {
            finalSolution = presentBoard;
            printState(finalSolution);
            // 中断线程组内所有其他线程，停止无效计算
            Thread.currentThread().getThreadGroup().interrupt();
        }
    }
}

核心逻辑 #

• AtomicBoolean的compareAndSet方法确保只有第一个线程能将标记从false改为true，避免多个线程同时输出。
• 找到解的线程会中断整个线程组，终止其他未完成的计算，提升效率。
• 修复了原代码中线程未真正并发的错误，让100个线程真正并行执行搜索。

内容的提问来源于stack exchange，提问作者metsys