133 lines
4.1 KiB
Text
133 lines
4.1 KiB
Text
/**
|
|
* A solver for the classic 8-queens problem.
|
|
*
|
|
* @see https://rosettacode.org/wiki/N-queens_problem
|
|
*/
|
|
module eightQueens {
|
|
void run() {
|
|
@Inject Console console;
|
|
Int count = new Board().solve(b -> console.print($"{b}\n"));
|
|
console.print($"{count} solutions found");
|
|
}
|
|
|
|
/**
|
|
* `Board` represents a chess board that holds only queens. The board
|
|
* is organized as columns 0 ("A") to 7 ("H"), and rows 0 (rank "1")
|
|
* to 7 (rank "8").
|
|
*/
|
|
const Board {
|
|
/**
|
|
* Construct an empty board.
|
|
*/
|
|
construct() {}
|
|
|
|
/**
|
|
* Internal: Construct a specifically-populated board.
|
|
*/
|
|
private construct(Int queens, Int claimed) {
|
|
this.queens = queens;
|
|
this.claimed = claimed;
|
|
}
|
|
|
|
/**
|
|
* Each bit of this 64-bit integer represents a queen.
|
|
*/
|
|
private Int queens;
|
|
/**
|
|
* Each bit of this 64-bit integer represents a queen or a threat.
|
|
*/
|
|
private Int claimed;
|
|
|
|
/**
|
|
* Translate a column and row to a bit-mask, used with the
|
|
* [queens] and [claimed] properties. Examples:
|
|
* * A1 is (0,0) => 0x0000000000000001
|
|
* * H8 is (7,7) => 0x8000000000000000
|
|
*/
|
|
private Int mask(Int col, Int row) = 1 << (row << 3) + col;
|
|
|
|
/**
|
|
* Determine if the specified square has a queen in it.
|
|
*/
|
|
Boolean occupied(Int col, Int row) {
|
|
return queens & mask(col, row) != 0;
|
|
}
|
|
|
|
/**
|
|
* Determine if the specified square is safe from the queens.
|
|
*/
|
|
Boolean safe(Int col, Int row) {
|
|
return claimed & mask(col, row) == 0;
|
|
}
|
|
|
|
/**
|
|
* Attempt to place a queen in a specified square.
|
|
*
|
|
* @return True iff a queen can be safely placed in the square
|
|
* @return (conditional) the new Board with the new queen on it
|
|
*/
|
|
conditional Board placeQueen(Int col, Int row) {
|
|
assert 0 <= col < 8 && 0 <= row < 8;
|
|
if (!safe(col, row)) {
|
|
return False;
|
|
}
|
|
|
|
Int newQueens = queens | mask(col, row);
|
|
Int newClaimed = claimed | queens;
|
|
// claim all threatened spaces
|
|
for (Int i : 0..7) {
|
|
newClaimed |= mask(i, row) | mask(col, i);
|
|
val diagDownRow = row + i - col;
|
|
if (0 <= diagDownRow < 8) {
|
|
newClaimed |= mask(i, diagDownRow);
|
|
}
|
|
val diagUpRow = row - i + col;
|
|
if (0 <= diagUpRow < 8) {
|
|
newClaimed |= mask(i, diagUpRow);
|
|
}
|
|
}
|
|
return True, new Board(newQueens, newClaimed);
|
|
}
|
|
|
|
/**
|
|
* Attempt to find all solutions to the n-queens problem.
|
|
*/
|
|
Int solve(function void(Board) yield) = solve(yield, 0);
|
|
|
|
/**
|
|
* Internal: Attempt to find all solutions to the n-queens problem,
|
|
* starting with the specified column and recursively solving by
|
|
* moving to the next column for each potential solution found in
|
|
* the specified column.
|
|
*/
|
|
private Int solve(function void(Board) yield, Int col) {
|
|
if (col == 8) {
|
|
// there is no column 8; we've found a solution
|
|
yield(this);
|
|
return 1;
|
|
}
|
|
|
|
Int count = 0;
|
|
for (Int rank : 8..1) {
|
|
val row = 8-rank;
|
|
if (Board afterPlacing := placeQueen(col, row)) {
|
|
count += afterPlacing.solve(yield, col + 1);
|
|
}
|
|
}
|
|
return count;
|
|
}
|
|
|
|
@Override String toString() {
|
|
val buf = new StringBuffer();
|
|
for (Int rank : 8..1) {
|
|
buf.append($"{rank} |");
|
|
val row = 8-rank;
|
|
for (Int col : 0..7) {
|
|
buf.add(occupied(col, row) ? 'q' : '_').add('|');
|
|
}
|
|
buf.add('\n');
|
|
}
|
|
return buf.append(" A B C D E F G H").toString();
|
|
}
|
|
}
|
|
}
|