# Parallel solutions to N Queens Puzzle

I'm trying to increase the performance of my N Queens Puzzle solution. I'd find some threads on SO already but they don't appear to help me to increase performance.

My best solution, however, is a strategy with a constant amount of working threads. I also tried to implement a solution with RecursiveTasks. But it appears that the first solution overcomes all my other tries. I think that is because the computer receives too many Tasks and looks for completion of working tasks most of the time.

However, I'd come up with two solutions:

First, the slow one with an implementation of RecursiveTask which needs 2449 ms for the calculation of N = 14:

public class DamenProblemFork extends RecursiveTask<Integer>{
private static final long serialVersionUID = -6502127276625965624L;
static int N = 14;

public static void main(String[] args) throws InterruptedException {

if (args.length == 1) {
N = Integer.parseInt(args);
}
long start = System.currentTimeMillis();
DamenProblemFork dpf_root = new DamenProblemFork(0L, 0L, 0L, N - 1);
Integer result = dpf_root.fork().join();

System.out.println("End time: " + (System.currentTimeMillis() - start) + " ms");
System.out.println("Result for " + N + ": " + result);

}

private long diagR;
private long diagL;
private long mid;
private int depth;

public DamenProblemFork(long diagR, long diagL, long mid, int depth) {
this.diagR = diagR;
this.diagL = diagL;
this.mid = mid;
this.depth = depth;
}

@Override
protected Integer compute() {

List<DamenProblemFork> ldpf = new ArrayList<>();

long valid = mid | diagL | diagR;
int resBuffer = 0;

for (int i = 0; i < N; i++) {
int pos = 1 << i;
if ((valid & pos) > 0) {
continue;
}
if (depth == 0) {
resBuffer++;
continue;
}

long n_mid = mid | pos;
long n_diagL = (diagL | pos) >> 1;
long n_diagR = (diagR | pos) << 1;

DamenProblemFork dpf = new DamenProblemFork(n_diagR, n_diagL, n_mid, depth - 1);
}

if(depth == 0) {
return resBuffer;
}

return ldpf.stream().parallel().map(d -> d.fork()).mapToInt(x -> x.join()).sum();
}
}


The next solution I'd come up with is with a dedicated thread pool with thread number equal to processor count. This, however, just needs 124ms for the calculation of 14:

public class DamenProblem {
static AtomicInteger result = new AtomicInteger(0);
static int N = 14;

public static void main(String[] args) throws InterruptedException {

if (args.length == 1) {
N = Integer.parseInt(args);
}

int processors = Runtime.getRuntime().availableProcessors();
int availableProcessors = processors < N ? processors : N;

BlockingQueue<Runnable> workQueue = new ArrayBlockingQueue<>(N);
TimeUnit.MILLISECONDS, workQueue);
Semaphore sem = new Semaphore(0);

long start = System.currentTimeMillis();

if(N%2 == 0) {

for (int i = 0; i < N/2; i++) {
int pos = 1 << i;
tpe.execute(() -> {
int res = run(pos << 1, pos >> 1, pos, N - 2);
sem.release();
});
}
sem.acquire(N/2);

System.out.println("End time: " + (System.currentTimeMillis() - start) + " ms");
System.out.println("Result for " + N + ": " + result.get()*2);

}
else {
for (int i = 0; i < N; i++) {
int pos = 1 << i;
tpe.execute(() -> {
int res = run(pos << 1, pos >> 1, pos, N - 2);
sem.release();
});
}
sem.acquire(N);

System.out.println("End time: " + (System.currentTimeMillis() - start) + " ms");
System.out.println("Result for " + N + ": " + result.get());
}
System.exit(0);
}

static int run(long diagR, long diagL, long mid, int depth) {
long valid = mid | diagL | diagR;
int resBuffer = 0;

for (int i = 0; i < N; i++) {
int pos = 1 << i;
if ((valid & pos) > 0) {
continue;
}
if (depth == 0) {
resBuffer++;
continue;
}
long n_mid = mid | pos;
long n_diagL = (diagL | pos) >> 1;
long n_diagR = (diagR | pos) << 1;

resBuffer += run(n_diagR, n_diagL, n_mid, depth - 1);
}
return resBuffer;
}
}


My CPU is an AMD ryzen 5 2600K with 12 cores.

Do you guys have an idea how to improve this code to make it even faster? I thought something of including symmetry. But does this work? I think using symmetry just increases performance if N is greater than the number of processors times two.

What do you think?

• Welcome to Code Review! I hope you get some great answers. – Phrancis Jun 14 '18 at 19:22
• Thank you! :) I'm trying to improve my programming skills and my thinking. :) – Noixes Jun 14 '18 at 19:23
• I agree to you that symmetry could improve performance. Might try for (int i = 0; i < N / 2; i++) { in main and then double result and run again with int i = Math.ceil(N / 2) if N is uneven – Jonas Wilms Jun 14 '18 at 19:42
• @JonasW. nice point, but the Math.ceil is not required :), i update the code in the question – Noixes Jun 14 '18 at 20:34
• @noixes yeah im from Javascript :) and did it effect performance? Im curious... – Jonas Wilms Jun 14 '18 at 20:37