Find covering positions of a Chess board using a minimum number of queens.

Queens.java

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();
  }
}