Gfrktyl

This code is a multi-threading recursive backtracking DFS algorithm to find all solutions to the N-Queens problem. The board size is indicated by BOARD_SIZE. CORES dictate how many concurrent threads to use.

I've seen other Java code utilising the same DFS algorithm but getting far faster results (< 1 sec for N = 15 where as my code takes about 15 secs), though they used completely bitwise operators.

How can I improve efficiency further? Is the synchronised hash set or the stringbuilder slowing the code down?

Also it's been several years since I actually coded Java so all critiques are welcome.

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 + " millisecondsn");



        // 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;

    }

}

• 
  

  The row conveys the information easily obtained from solution, and therefore looks redundant. Consider

  
  
  

      public boolean canPutQueen(int r, int c, StringBuilder solutions) {
  
          int queen;
  
          for (int i = 1; i <= c; i++) {
  
              queen = solution.charAt(c - i);
  
              if (queen == r || queen == (r - i) || queen == (r + i))
  
                  return false;
  
          }
  
          return true;
  
      }
  
  

  
  
  

  and you may abandon rows altogether.

  
  
  

  BTW, the doc comment on rows is very misleading:

  
  
  

   * @param rows BitSet of occupied rows at column c not accounting for diagonals
  
  

  
  
  

  As a reviewer I had very hard time trying to understand how there might be an occupied row at the column we are working at. You surely meant attacked.

  
  



• The threads do not compete for any data, except solutions. Notice that the per-thread sets of solutions are guaranteed to be disjoint (they surely differ at the first column). Consider each thread to work on its own set of solutions (again, there is no need to have a Set: the algorithm produces no dupes, so a per-thread List suffices), and let the main thread to combine them.



• 
  

  I don't know whether these recommendations would enhance the performance. How does a single-threaded version perform?

  
  
  

  In any case, when in doubt, profile.

  
  

I'd suggest to do not use StringBuilder as a source of data - it could be replaced with List or even plain arrays because StringBuilder-s used to invoke charAt(idx) and then some if comparing obtained char as int.

For me usage of number of CORES (I assume it will not be hardcoded but obtained from system props) is a kind of bad practice. You think that if you start as many threads as number of cores than all these threads will run in parallel and all of them will do calculations at the same time and you will get the result as soon as possible. Such assumptions are not correct because does not take into account thread scheduling on OS and hardware level which indeed exists and sometimes has much bigger impact on overall performance than code constructions you wrote. I strongly suggest to consider Fork/Join methodology in case you use Java modern enough.