Peaceful chess queen armies: Difference between revisions
Added solution for D
(Added solution for D) |
|||
Line 51:
* [http://www.mathopt.org/Optima-Issues/optima62.pdf Peaceably Coexisting Armies of Queens] (Pdf) by Robert A. Bosch. Optima, the Mathematical Programming Socity newsletter, issue 62.
* [https://oeis.org/A250000 A250000] OEIS
=={{header|D}}==
{{trans|Go}}
<lang d>import std.array;
import std.math;
import std.stdio;
import std.typecons;
enum Piece {
empty,
black,
white,
}
alias position = Tuple!(int, "i", int, "j");
bool place(int m, int n, ref position[] pBlackQueens, ref position[] pWhiteQueens) {
if (m == 0) {
return true;
}
bool placingBlack = true;
foreach (i; 0..n) {
inner:
foreach (j; 0..n) {
auto pos = position(i, j);
foreach (queen; pBlackQueens) {
if (queen == pos || !placingBlack && isAttacking(queen, pos)) {
continue inner;
}
}
foreach (queen; pWhiteQueens) {
if (queen == pos || placingBlack && isAttacking(queen, pos)) {
continue inner;
}
}
if (placingBlack) {
pBlackQueens ~= pos;
placingBlack = false;
} else {
pWhiteQueens ~= pos;
if (place(m - 1, n, pBlackQueens, pWhiteQueens)) {
return true;
}
pBlackQueens.length--;
pWhiteQueens.length--;
placingBlack = true;
}
}
}
if (!placingBlack) {
pBlackQueens.length--;
}
return false;
}
bool isAttacking(position queen, position pos) {
return queen.i == pos.i
|| queen.j == pos.j
|| abs(queen.i - pos.i) == abs(queen.j - pos.j);
}
void printBoard(int n, position[] blackQueens, position[] whiteQueens) {
auto board = uninitializedArray!(Piece[])(n * n);
board[] = Piece.empty;
foreach (queen; blackQueens) {
board[queen.i * n + queen.j] = Piece.black;
}
foreach (queen; whiteQueens) {
board[queen.i * n + queen.j] = Piece.white;
}
foreach (i,b; board) {
if (i != 0 && i % n == 0) {
writeln;
}
final switch (b) {
case Piece.black:
write("B ");
break;
case Piece.white:
write("W ");
break;
case Piece.empty:
int j = i / n;
int k = i - j * n;
if (j % 2 == k % 2) {
write("• "w);
} else {
write("◦ "w);
}
break;
}
}
writeln('\n');
}
void main() {
auto nms = [
[2, 1], [3, 1], [3, 2], [4, 1], [4, 2], [4, 3],
[5, 1], [5, 2], [5, 3], [5, 4], [5, 5],
[6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6],
[7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7],
];
foreach (nm; nms) {
writefln("%d black and %d white queens on a %d x %d board:", nm[1], nm[1], nm[0], nm[0]);
position[] blackQueens;
position[] whiteQueens;
if (place(nm[1], nm[0], blackQueens, whiteQueens)) {
printBoard(nm[0], blackQueens, whiteQueens);
} else {
writeln("No solution exists.\n");
}
}
}</lang>
{{out}}
<pre>1 black and 1 white queens on a 2 x 2 board:
No solution exists.
1 black and 1 white queens on a 3 x 3 board:
B ◦ •
◦ • W
• ◦ •
2 black and 2 white queens on a 3 x 3 board:
No solution exists.
1 black and 1 white queens on a 4 x 4 board:
B ◦ • ◦
◦ • W •
• ◦ • ◦
◦ • ◦ •
2 black and 2 white queens on a 4 x 4 board:
B ◦ • ◦
◦ • W •
B ◦ • ◦
◦ • W •
3 black and 3 white queens on a 4 x 4 board:
No solution exists.
1 black and 1 white queens on a 5 x 5 board:
B ◦ • ◦ •
◦ • W • ◦
• ◦ • ◦ •
◦ • ◦ • ◦
• ◦ • ◦ •
2 black and 2 white queens on a 5 x 5 board:
B ◦ • ◦ B
◦ • W • ◦
• W • ◦ •
◦ • ◦ • ◦
• ◦ • ◦ •
3 black and 3 white queens on a 5 x 5 board:
B ◦ • ◦ B
◦ • W • ◦
• W • ◦ •
◦ • ◦ B ◦
• W • ◦ •
4 black and 4 white queens on a 5 x 5 board:
• B • B •
◦ • ◦ • B
W ◦ W ◦ •
◦ • ◦ • B
W ◦ W ◦ •
5 black and 5 white queens on a 5 x 5 board:
No solution exists.
1 black and 1 white queens on a 6 x 6 board:
B ◦ • ◦ • ◦
◦ • W • ◦ •
• ◦ • ◦ • ◦
◦ • ◦ • ◦ •
• ◦ • ◦ • ◦
◦ • ◦ • ◦ •
2 black and 2 white queens on a 6 x 6 board:
B ◦ • ◦ B ◦
◦ • W • ◦ •
• W • ◦ • ◦
◦ • ◦ • ◦ •
• ◦ • ◦ • ◦
◦ • ◦ • ◦ •
3 black and 3 white queens on a 6 x 6 board:
B ◦ • ◦ B B
◦ • W • ◦ •
• W • ◦ • ◦
◦ • ◦ • ◦ •
• ◦ W ◦ • ◦
◦ • ◦ • ◦ •
4 black and 4 white queens on a 6 x 6 board:
B ◦ • ◦ B B
◦ • W • ◦ •
• W • ◦ • ◦
◦ • ◦ • ◦ B
• ◦ W W • ◦
◦ • ◦ • ◦ •
5 black and 5 white queens on a 6 x 6 board:
• B • ◦ B ◦
◦ • ◦ B ◦ B
W ◦ • ◦ • ◦
W • W • ◦ •
• ◦ • ◦ • B
W • W • ◦ •
6 black and 6 white queens on a 6 x 6 board:
No solution exists.
1 black and 1 white queens on a 7 x 7 board:
B ◦ • ◦ • ◦ •
◦ • W • ◦ • ◦
• ◦ • ◦ • ◦ •
◦ • ◦ • ◦ • ◦
• ◦ • ◦ • ◦ •
◦ • ◦ • ◦ • ◦
• ◦ • ◦ • ◦ •
2 black and 2 white queens on a 7 x 7 board:
B ◦ • ◦ B ◦ •
◦ • W • ◦ • W
• ◦ • ◦ • ◦ •
◦ • ◦ • ◦ • ◦
• ◦ • ◦ • ◦ •
◦ • ◦ • ◦ • ◦
• ◦ • ◦ • ◦ •
3 black and 3 white queens on a 7 x 7 board:
B ◦ • ◦ B ◦ •
◦ • W • ◦ • W
B ◦ • ◦ • ◦ •
◦ • W • ◦ • ◦
• ◦ • ◦ • ◦ •
◦ • ◦ • ◦ • ◦
• ◦ • ◦ • ◦ •
4 black and 4 white queens on a 7 x 7 board:
B ◦ • ◦ B ◦ •
◦ • W • ◦ • W
B ◦ • ◦ B ◦ •
◦ • W • ◦ • W
• ◦ • ◦ • ◦ •
◦ • ◦ • ◦ • ◦
• ◦ • ◦ • ◦ •
5 black and 5 white queens on a 7 x 7 board:
B ◦ • ◦ B ◦ •
◦ • W • ◦ • W
B ◦ • ◦ B ◦ •
◦ • W • ◦ • W
B ◦ • ◦ • ◦ •
◦ • W • ◦ • ◦
• ◦ • ◦ • ◦ •
6 black and 6 white queens on a 7 x 7 board:
B ◦ • ◦ B ◦ •
◦ • W • ◦ • W
B ◦ • ◦ B ◦ •
◦ • W • ◦ • W
B ◦ • ◦ B ◦ •
◦ • W • ◦ • W
• ◦ • ◦ • ◦ •
7 black and 7 white queens on a 7 x 7 board:
• B • ◦ • B •
◦ B ◦ • B • ◦
• B • ◦ • B •
◦ • ◦ • B • ◦
W ◦ W ◦ • ◦ W
◦ • ◦ W ◦ • ◦
W ◦ W W • ◦ • </pre>
=={{header|Go}}==
| |||