Peaceful chess queen armies: Difference between revisions
Content added Content deleted
(Added solution for D) |
|||
Line 51: | 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. |
* [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 |
* [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}}== |
=={{header|Go}}== |