Skip to content

Instantly share code, notes, and snippets.

@carl-mastrangelo
Created March 24, 2023 21:11
Show Gist options
  • Save carl-mastrangelo/9dcde68d0df0216d43598908b5805683 to your computer and use it in GitHub Desktop.
Save carl-mastrangelo/9dcde68d0df0216d43598908b5805683 to your computer and use it in GitHub Desktop.
Find covering positions of a Chess board using a minimum number of queens.
package com.carlmastrangelo;
import java.util.SplittableRandom;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
import java.util.concurrent.atomic.AtomicLong;
public final class Queens {
public static void main(String [] args) throws Exception {
ForkJoinPool.commonPool().submit(new Counter(0, 0, new SplittableRandom(2)));
Thread.sleep(120_000);
}
private static final class Counter extends RecursiveAction {
private final long occupy;
private final long threaten;
private final SplittableRandom rng;
Counter(long occupy, long threaten, SplittableRandom rng) {
this.occupy = occupy;
this.threaten = threaten;
this.rng = rng;
}
private static final AtomicLong best = new AtomicLong();
private static long encodeBest(int count, int queens) {
return (((long)count)<<32) | (Integer.MAX_VALUE - queens);
}
@Override
protected void compute() {
for (int i = 0; i < 64; i++) {
int pos = rng.nextInt(64);
if ((occupy & (1L << pos)) == 0) {
long newThreaten = threaten | board(pos);
int newThreatenCount = Long.bitCount(newThreaten);
if (newThreatenCount > Long.bitCount(threaten)) {
long existingBest = best.get();
long newOccupy = occupy | (1L << pos);
long maybeNewBest = encodeBest(newThreatenCount, Long.bitCount(newOccupy));
if (maybeNewBest > existingBest) {
if (best.compareAndSet(existingBest, maybeNewBest)) {
synchronized (System.out) {
System.out.println("New Best: " + Long.bitCount(newOccupy));
System.out.println(printBoard(newOccupy, newThreaten));
}
}
}
new Counter(newOccupy, newThreaten, rng.split()).fork();
}
}
}
}
}
private static long board(final int queen) {
int xq = queen & 0x7;
int yq = queen >>> 3;
long board = 0;
for (int x = 0; x < 8; x++) {
board |= 1L << ((yq << 3) + x);
}
for (int y = 0; y < 8; y++) {
board |= 1L << ((y << 3) + xq);
}
for (int d = -8; d < 8; d++) {
int x = xq + d;
int y = yq + d;
if (x >= 0 && x < 8 && y >= 0 && y < 8) {
board |= 1L << ((y << 3) + x);
}
y = yq - d;
if (x >= 0 && x < 8 && y >= 0 && y < 8) {
board |= 1L << ((y << 3) + x);
}
}
return board;
}
private static String printBoard(long occupy, long threaten) {
var sb = new StringBuilder();
sb.append("+--------+\n");
for (int y = 0; y < 8; y++) {
sb.append('|');
for (int x = 0; x < 8; x++) {
long mask = (1L << (y * 8 + x));
if ((mask & occupy) != 0) {
sb.append("Q");
} else if ((mask & threaten) != 0) {
sb.append("X");
} else {
sb.append(" ");
}
}
sb.append("|\n");
}
sb.append("+--------+\n");
return sb.toString();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment