/usr/share/doc/libconcurrent-java-doc/taskDemo/NQueens.java is in libconcurrent-java-doc 1.3.4-4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | // Adapted from a cilk demo
import EDU.oswego.cs.dl.util.concurrent.*;
class NQueens extends FJTask {
static int boardSize;
public static void main(String[] args) {
try {
int procs;
try {
procs = Integer.parseInt(args[0]);
boardSize = Integer.parseInt(args[1]);
}
catch (Exception e) {
System.out.println("Usage: java NQueens <threads> <boardSize>");
return;
}
if (boardSize <= 3) {
System.out.println("There is no solution for board size <= 3");
return;
}
FJTaskRunnerGroup g = new FJTaskRunnerGroup(procs);
NQueens f = new NQueens(new int[0]);
g.execute(f);
int[] board = result.await();
g.stats();
System.out.print("Result:");
for (int i = 0; i < board.length; ++i) {
System.out.print(" " + board[i]);
}
System.out.println();
}
catch (InterruptedException ex) {}
}
/**
* Global variable holding the result of search.
* FJTasks check this to see if it is nonnull,
* if so, returning early because a result has been found.
* In a more serious program, we might use a fancier scheme
* to reduce read/write pressure on this variable.
**/
static final class Result {
private int[] board = null;
synchronized int[] get() { return board; }
synchronized void set(int[] b) {
if (board == null) { board = b; notifyAll(); }
}
synchronized int[] await() throws InterruptedException {
while (board == null) { wait(); }
return board;
}
}
static final Result result = new Result();
// Boards are represented as arrays where each cell
// holds the column number of the queen in that row
final int[] sofar;
NQueens(int[] a) { this.sofar = a; }
public void run() {
if (result.get() == null) { // check if already solved
int row = sofar.length;
if (row >= boardSize) // done
result.set(sofar);
else {
for (int q = 0; q < boardSize; ++q) {
// Check if can place queen in column q of next row
boolean attacked = false;
for (int i = 0; i < row; i++) {
int p = sofar[i];
if (q == p || q == p - (row - i) || q == p + (row - i)) {
attacked = true;
break;
}
}
// Fork to explore moves from new configuration
if (!attacked) {
int[] next = new int[row+1];
for (int k = 0; k < row; ++k) next[k] = sofar[k];
next[row] = q;
new NQueens(next).fork();
}
}
}
}
}
}
|