95 lines
2.8 KiB
Text
95 lines
2.8 KiB
Text
module NQueens {
|
|
inherits {
|
|
Heron.Windows.Console;
|
|
}
|
|
fields {
|
|
n : Int = 4;
|
|
sols : List = new List();
|
|
}
|
|
methods {
|
|
PosToString(row : Int, col : Int) : String {
|
|
return "row " + row.ToString() + ", col " + col.ToString();
|
|
}
|
|
AddQueen(b : Board, row : Int, col : Int)
|
|
{
|
|
if (!b.TryAddQueen(row, col))
|
|
return;
|
|
if (row < n - 1)
|
|
foreach (i in 0..n-1)
|
|
AddQueen(new Board(b), row + 1, i);
|
|
else
|
|
sols.Add(b);
|
|
}
|
|
Main() {
|
|
foreach (i in 0..n-1)
|
|
AddQueen(new Board(), 0, i);
|
|
foreach (b in sols) {
|
|
b.Output();
|
|
WriteLine("");
|
|
}
|
|
WriteLine("Found " + sols.Count().ToString() + " solutions");
|
|
}
|
|
}
|
|
}
|
|
|
|
class Board {
|
|
fields {
|
|
rows = new List();
|
|
}
|
|
methods {
|
|
Constructor() {
|
|
foreach (r in 0..n-1) {
|
|
var col = new List();
|
|
foreach (c in 0..n-1)
|
|
col.Add(false);
|
|
rows.Add(col);
|
|
}
|
|
}
|
|
Constructor(b : Board) {
|
|
Constructor();
|
|
foreach (r in 0..n-1)
|
|
foreach (c in 0..n-1)
|
|
SetSpaceOccupied(r, c, b.SpaceOccupied(r, c));
|
|
}
|
|
SpaceOccupied(row : Int, col : Int) : Bool {
|
|
return rows[row][col];
|
|
}
|
|
SetSpaceOccupied(row : Int, col : Int, b : Bool) {
|
|
rows[row][col] = b;
|
|
}
|
|
ValidPos(row : Int, col : Int) : Bool {
|
|
return ((row >= 0) && (row < n)) && ((col >= 0) && (col < n));
|
|
}
|
|
VectorOccupied(row : Int, col : Int, rowDir : Int, colDir : Int) : Bool {
|
|
var nextRow = row + rowDir;
|
|
var nextCol = col + colDir;
|
|
if (!ValidPos(nextRow, nextCol))
|
|
return false;
|
|
if (SpaceOccupied(nextRow, nextCol))
|
|
return true;
|
|
return VectorOccupied(nextRow, nextCol, rowDir, colDir);
|
|
}
|
|
TryAddQueen(row : Int, col : Int) : Bool {
|
|
foreach (rowDir in -1..1)
|
|
foreach (colDir in -1..1)
|
|
if (rowDir != 0 || colDir != 0)
|
|
if (VectorOccupied(row, col, rowDir, colDir))
|
|
return false;
|
|
SetSpaceOccupied(row, col, true);
|
|
return true;
|
|
}
|
|
Output() {
|
|
foreach (row in 0..n-1) {
|
|
foreach (col in 0..n-1) {
|
|
if (SpaceOccupied(row, col)) {
|
|
Write("Q");
|
|
}
|
|
else {
|
|
Write(".");
|
|
}
|
|
}
|
|
WriteLine("");
|
|
}
|
|
}
|
|
}
|
|
}
|