找到所有的solution解决方案

Question

此代码是一种多线程递归回溯DFS算法，用于寻找solutions问题的所有解决方案。板的大小由BOARD_SIZE表示。CORES指定要使用多少并发线程。

我见过其他Java代码使用相同的DFS算法，但获得的结果要快得多(N= 15的<1秒，因为我的代码大约需要15秒)，尽管它们使用的是完全按位的运算符。

如何进一步提高效率？是同步哈希集还是字符串生成器减慢了代码的速度？

而且，自从我编写Java代码以来已经有几年了，所以所有的评论都是受欢迎的。

package nQueens;
import java.util.*;
public class NQueensRedux implements Runnable {
    public static final int BOARD_SIZE = 15;
    public static final int DISPLAY_LIMIT = 1;
    public static final int CORES = 4;
    private Set<String> solutions;
    private int start, end, n;

    /**
     * 
     * @param n Board size
     * @param solutions HashSet of all valid solutions
     * @param start The first row on the first column to place a queen
     * @param end The last row on the first column to place a queen
     */
    NQueensRedux(int n, Set<String> solutions, int start, int end) {
        this.solutions = solutions;
        this.start = start;
        this.end = end;
        this.n = n;
    }

    public static void main(String args[]) {
        Set<String> solutions = Collections.synchronizedSet(new HashSet<>());
        ArrayList<Thread> threads = new ArrayList<>();

        // Create as many threads as CORES
        long startTime = System.nanoTime();
        for (int i = 0; i < BOARD_SIZE; i += BOARD_SIZE / CORES) {
            Thread t = new Thread(new NQueensRedux(BOARD_SIZE, solutions, i, Math.min(i + BOARD_SIZE / CORES, BOARD_SIZE)));
            t.start();
            threads.add(t);
        }
        // Wait for all threads to finish executing
        try {
            for (int i = 0; i < threads.size(); i++) {
                threads.get(i).join();
            }
        } catch (InterruptedException e) {
            System.out.println("Thread interrupted.");
        }
        long endTime = System.nanoTime();
        long duration = (endTime - startTime) / 1000000;
        System.out.println("found " + solutions.size() + " solutions in " + duration + " milliseconds\n");

        // Print solution(s)
        Iterator i = solutions.iterator();
        int k = 0;
        while (i.hasNext() && k < DISPLAY_LIMIT) {
            String solution = (String) i.next();
            for (int r = 0; r < BOARD_SIZE; r++) {
                for (int c = 0; c < BOARD_SIZE; c++) {
                    if (r == solution.charAt(c)) {
                        System.out.print("Q ");
                    } else {
                        System.out.print(". ");
                    }
                }
                System.out.println("");
            }
            System.out.println("");
            k++;
        }
    }

    public void run() {
        // True indicates a row is occupied with a queen
        BitSet rows = new BitSet(n);

        // Iterate through rows between start and end in the first column placing a queen in each
        for (int r = start; r < end; r++) {
            StringBuilder s = new StringBuilder((char)r + "");
            rows.flip(r);
            bruteForce(1, s, solutions, rows);
            rows.flip(r);
        }
    }

    /**
     * Recursive algorithm to do a DFS on all solutions to n-queens
     * 
     * @param c Column to place a queen in
     * @param solution String representing queen positions so far. Index is column, value is row
     * @param solutions HashSet of valid solutions
     * @param rows BitSet of occupied rows at column c not accounting for diagonals
     */
    public void bruteForce(int c, StringBuilder solution, Set<String> solutions, BitSet rows) {
        // String was chosen instead of array to avoid having to deep copy
        if (c == n) {
            solutions.add(solution.toString());
            return;
        }
        // Go thru every row and if a queen can be placed, recurse for next column
        for (int r = 0; r < n; r++) {
            if (canPutQueen(r, c, solution, rows)) {
                rows.flip(r);
                // cast r to a char and append it to the solution string
                solution.append((char)r);
                bruteForce(c + 1, solution, solutions, rows);
                rows.flip(r);
                solution.setLength(solution.length() - 1);
            }
        }
    }

    public boolean canPutQueen(int r, int c, StringBuilder solution, BitSet rows) {
        int queen;
        // A queen can attack at most 3 squares on a previous column
        // So check those 3 squares to see if a queen is there
        if (rows.get(r)) return false;
        for (int i = 1; i <= c; i++) {
            queen = solution.charAt(c - i);
            if (queen == (r - i) || queen == (r + i)) return false;
        }
        return true;
    }
}

Answer 1

• row传递了从solution轻松获得的信息，因此看起来是多余的。考虑公共布尔值canPutQueen(int r，int c，StringBuilder解决方案){ int皇后；for (int i= 1；i <= c；i++) { queen = solution.charAt(c - i)；if (queen == r_x\皇后== (r - i) \x\女王== (r +i)返回假；}返回真；}您可以完全放弃rows。顺便说一句，rows上的文档注释非常具有误导性：* @param行BitSet在第c列被占用的行，而不是作为审阅者考虑对角线，我很难理解在我们正在处理的列上如何会出现被占用的行。你的意思是攻击。
• 除了solutions之外，线程不竞争任何数据。请注意，解决方案的每线程集合都保证是不相交的(它们在第一列中肯定不同)。考虑每个线程都要处理自己的一组解决方案(同样，不需要有一个Set：该算法不会产生任何陷阱，所以每个线程的List就足够了)，然后让主线程将它们组合起来。
• 我不知道这些建议是否能提高业绩。单线程版本是如何执行的？在任何情况下，当有疑问的时候，侧写。

Answer 2

我建议不要使用StringBuilder作为数据源--它可以替换为List，甚至是普通数组，因为StringBuilder曾经调用charAt，如果将获得的char作为int进行比较的话。

对我来说，使用多个核心(我假设它不会被硬编码，而是从系统道具获得)是一种糟糕的做法。您认为，如果启动的线程数量超过所有这些线程的核心数，并且所有线程都将同时进行计算，那么您将尽快得到结果。这样的假设是不正确的，因为没有考虑到操作系统和硬件级别上的线程调度，这些线程调度确实存在，有时对总体性能的影响要比您编写的代码结构大得多。我强烈建议考虑使用分叉/连接方法，以防您使用了足够现代的Java。