N-queens problem: Difference between revisions
Add Ecstasy example
m (→{{header|Wren}}: Changed to Wren S/H) |
(Add Ecstasy example) |
||
Line 4,807:
12 ♕ 14200 solutions
</pre>
=={{header|Ecstasy}}==
<syntaxhighlight lang="Ecstasy">/**
* 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();
}
}
}</syntaxhighlight>
<b>Output:</b>
<code><pre>
8 |q|_|_|_|_|_|_|_|
7 |_|_|_|_|_|_|q|_|
6 |_|_|_|_|q|_|_|_|
5 |_|_|_|_|_|_|_|q|
4 |_|q|_|_|_|_|_|_|
3 |_|_|_|q|_|_|_|_|
2 |_|_|_|_|_|q|_|_|
1 |_|_|q|_|_|_|_|_|
A B C D E F G H
8 |q|_|_|_|_|_|_|_|
7 |_|_|_|_|_|_|q|_|
6 |_|_|_|q|_|_|_|_|
5 |_|_|_|_|_|q|_|_|
4 |_|_|_|_|_|_|_|q|
3 |_|q|_|_|_|_|_|_|
2 |_|_|_|_|q|_|_|_|
1 |_|_|q|_|_|_|_|_|
A B C D E F G H
(...)
8 |_|_|q|_|_|_|_|_|
7 |_|_|_|_|_|q|_|_|
6 |_|_|_|q|_|_|_|_|
5 |_|q|_|_|_|_|_|_|
4 |_|_|_|_|_|_|_|q|
3 |_|_|_|_|q|_|_|_|
2 |_|_|_|_|_|_|q|_|
1 |q|_|_|_|_|_|_|_|
A B C D E F G H
92 solutions found
</pre></code>
=={{header|Eiffel}}==
| |||