⚠️ Warning: This is a draft ⚠️
This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.
If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.
{{task}} In chess, a queen attacks positions from where it is, in straight lines up-down and left-right as well as on both its diagonals. It attacks only pieces ''not'' of its own colour.
| ⇖ | ⇑ | ⇗ | ||
| ⇐ | ⇐ | ♛ | ⇒ | ⇒ |
| ⇙ | ⇓ | ⇘ | ||
| ⇙ | ⇓ | ⇘ | ||
| ⇓ |
The goal of Peaceful chess queen armies is to arrange m black queens and m white queens on an n-by-n square grid, (the board), so that ''no queen attacks another of a different colour''.
;Task:
Create a routine to represent two-colour queens on a 2-D board. (Alternating black/white background colours, Unicode chess pieces and other embellishments are not necessary, but may be used at your discretion).
Create a routine to generate at least one solution to placing m equal numbers of black and white queens on an n square board.
Display here results for the m=4, n=5 case.
;References:
- [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
D
{{trans|Go}}
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");
}
}
}
{{out}}
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 • ◦ •
Go
This is based on the C# code [https://www.reddit.com/r/coding/comments/b5eu7w/peaceful_chess_queen_armies_new_draft_rosetta/ here].
Textual rather than HTML output. Whilst the unicode symbols for the black and white queens are recognized by the Ubuntu 16.04 terminal, I found it hard to visually distinguish between them so I've used 'B' and 'W' instead.
package main
import "fmt"
const (
empty = iota
black
white
)
const (
bqueen = 'B'
wqueen = 'W'
bbullet = '•'
wbullet = '◦'
)
type position struct{ i, j int }
func iabs(i int) int {
if i < 0 {
return -i
}
return i
}
func place(m, n int, pBlackQueens, pWhiteQueens *[]position) bool {
if m == 0 {
return true
}
placingBlack := true
for i := 0; i < n; i++ {
inner:
for j := 0; j < n; j++ {
pos := position{i, j}
for _, queen := range *pBlackQueens {
if queen == pos || !placingBlack && isAttacking(queen, pos) {
continue inner
}
}
for _, queen := range *pWhiteQueens {
if queen == pos || placingBlack && isAttacking(queen, pos) {
continue inner
}
}
if placingBlack {
*pBlackQueens = append(*pBlackQueens, pos)
placingBlack = false
} else {
*pWhiteQueens = append(*pWhiteQueens, pos)
if place(m-1, n, pBlackQueens, pWhiteQueens) {
return true
}
*pBlackQueens = (*pBlackQueens)[0 : len(*pBlackQueens)-1]
*pWhiteQueens = (*pWhiteQueens)[0 : len(*pWhiteQueens)-1]
placingBlack = true
}
}
}
if !placingBlack {
*pBlackQueens = (*pBlackQueens)[0 : len(*pBlackQueens)-1]
}
return false
}
func isAttacking(queen, pos position) bool {
if queen.i == pos.i {
return true
}
if queen.j == pos.j {
return true
}
if iabs(queen.i-pos.i) == iabs(queen.j-pos.j) {
return true
}
return false
}
func printBoard(n int, blackQueens, whiteQueens []position) {
board := make([]int, n*n)
for _, queen := range blackQueens {
board[queen.i*n+queen.j] = black
}
for _, queen := range whiteQueens {
board[queen.i*n+queen.j] = white
}
for i, b := range board {
if i != 0 && i%n == 0 {
fmt.Println()
}
switch b {
case black:
fmt.Printf("%c ", bqueen)
case white:
fmt.Printf("%c ", wqueen)
case empty:
if i%2 == 0 {
fmt.Printf("%c ", bbullet)
} else {
fmt.Printf("%c ", wbullet)
}
}
}
fmt.Println("\n")
}
func main() {
nms := [][2]int{
{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},
}
for _, nm := range nms {
n, m := nm[0], nm[1]
fmt.Printf("%d black and %d white queens on a %d x %d board:\n", m, m, n, n)
var blackQueens, whiteQueens []position
if place(m, n, &blackQueens, &whiteQueens) {
printBoard(n, blackQueens, whiteQueens)
} else {
fmt.Println("No solution exists.\n")
}
}
}
{{out}}
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 • ◦ •
Julia
GUI version, uses the Gtk library. The place! function is condensed from the C# example.
using Gtk
struct Position
row::Int
col::Int
end
function place!(numeach, bsize, bqueens, wqueens)
isattack(q, pos) = (q.row == pos.row || q.col == pos.col ||
abs(q.row - pos.row) == abs(q.col - pos.col))
noattack(qs, pos) = !any(x -> isattack(x, pos), qs)
positionopen(bqs, wqs, p) = !any(x -> x == p, bqs) && !any(x -> x == p, wqs)
placingbqueens = true
if numeach < 1
return true
end
for i in 1:bsize, j in 1:bsize
bpos = Position(i, j)
if positionopen(bqueens, wqueens, bpos)
if placingbqueens && noattack(wqueens, bpos)
push!(bqueens, bpos)
placingbqueens = false
elseif !placingbqueens && noattack(bqueens, bpos)
push!(wqueens, bpos)
if place!(numeach - 1, bsize, bqueens, wqueens)
return true
end
pop!(bqueens)
pop!(wqueens)
placingbqueens = true
end
end
end
if !placingbqueens
pop!(bqueens)
end
false
end
function peacefulqueenapp()
win = GtkWindow("Peaceful Chess Queen Armies", 800, 800) |> (GtkFrame() |> (box = GtkBox(:v)))
boardsize = 5
numqueenseach = 4
hbox = GtkBox(:h)
boardscale = GtkScale(false, 2:16)
set_gtk_property!(boardscale, :hexpand, true)
blabel = GtkLabel("Choose Board Size")
nqueenscale = GtkScale(false, 1:24)
set_gtk_property!(nqueenscale, :hexpand, true)
qlabel = GtkLabel("Choose Number of Queens Per Side")
solveit = GtkButton("Solve")
set_gtk_property!(solveit, :label, " Solve ")
solvequeens(wid) = (boardsize = Int(GAccessor.value(boardscale));
numqueenseach = Int(GAccessor.value(nqueenscale)); update!())
signal_connect(solvequeens, solveit, :clicked)
map(w->push!(hbox, w),[blabel, boardscale, qlabel, nqueenscale, solveit])
scrwin = GtkScrolledWindow()
grid = GtkGrid()
push!(scrwin, grid)
map(w -> push!(box, w),[hbox, scrwin])
piece = (white = "\u2655", black = "\u265B", blank = " ")
stylist = GtkStyleProvider(Gtk.CssProviderLeaf(data="""
label {background-image: image(cornsilk); font-size: 48px;}
button {background-image: image(tan); font-size: 48px;}"""))
function update!()
bqueens, wqueens = Vector{Position}(), Vector{Position}()
place!(numqueenseach, boardsize, bqueens, wqueens)
if length(bqueens) == 0
warn_dialog("No solution for board size $boardsize and $numqueenseach queens each.", win)
return
end
empty!(grid)
labels = Array{Gtk.GtkLabelLeaf, 2}(undef, (boardsize, boardsize))
buttons = Array{GtkButtonLeaf, 2}(undef, (boardsize, boardsize))
for i in 1:boardsize, j in 1:boardsize
if isodd(i + j)
grid[i, j] = buttons[i, j] = GtkButton(piece.blank)
set_gtk_property!(buttons[i, j], :expand, true)
push!(Gtk.GAccessor.style_context(buttons[i, j]), stylist, 600)
else
grid[i, j] = labels[i, j] = GtkLabel(piece.blank)
set_gtk_property!(labels[i, j], :expand, true)
push!(Gtk.GAccessor.style_context(labels[i, j]), stylist, 600)
end
pos = Position(i, j)
if pos in bqueens
set_gtk_property!(grid[i, j], :label, piece.black)
elseif pos in wqueens
set_gtk_property!(grid[i, j], :label, piece.white)
end
end
showall(win)
end
update!()
cond = Condition()
endit(w) = notify(cond)
signal_connect(endit, win, :destroy)
showall(win)
wait(cond)
end
peacefulqueenapp()
Kotlin
{{trans|D}}
import kotlin.math.abs
enum class Piece {
Empty,
Black,
White,
}
typealias Position = Pair<Int, Int>
fun place(m: Int, n: Int, pBlackQueens: MutableList<Position>, pWhiteQueens: MutableList<Position>): Boolean {
if (m == 0) {
return true
}
var placingBlack = true
for (i in 0 until n) {
inner@
for (j in 0 until n) {
val pos = Position(i, j)
for (queen in pBlackQueens) {
if (queen == pos || !placingBlack && isAttacking(queen, pos)) {
continue@inner
}
}
for (queen in pWhiteQueens) {
if (queen == pos || placingBlack && isAttacking(queen, pos)) {
continue@inner
}
}
placingBlack = if (placingBlack) {
pBlackQueens.add(pos)
false
} else {
pWhiteQueens.add(pos)
if (place(m - 1, n, pBlackQueens, pWhiteQueens)) {
return true
}
pBlackQueens.removeAt(pBlackQueens.lastIndex)
pWhiteQueens.removeAt(pWhiteQueens.lastIndex)
true
}
}
}
if (!placingBlack) {
pBlackQueens.removeAt(pBlackQueens.lastIndex)
}
return false
}
fun isAttacking(queen: Position, pos: Position): Boolean {
return queen.first == pos.first
|| queen.second == pos.second
|| abs(queen.first - pos.first) == abs(queen.second - pos.second)
}
fun printBoard(n: Int, blackQueens: List<Position>, whiteQueens: List<Position>) {
val board = MutableList(n * n) { Piece.Empty }
for (queen in blackQueens) {
board[queen.first * n + queen.second] = Piece.Black
}
for (queen in whiteQueens) {
board[queen.first * n + queen.second] = Piece.White
}
for ((i, b) in board.withIndex()) {
if (i != 0 && i % n == 0) {
println()
}
if (b == Piece.Black) {
print("B ")
} else if (b == Piece.White) {
print("W ")
} else {
val j = i / n
val k = i - j * n
if (j % 2 == k % 2) {
print("• ")
} else {
print("◦ ")
}
}
}
println('\n')
}
fun main() {
val nms = listOf(
Pair(2, 1), Pair(3, 1), Pair(3, 2), Pair(4, 1), Pair(4, 2), Pair(4, 3),
Pair(5, 1), Pair(5, 2), Pair(5, 3), Pair(5, 4), Pair(5, 5),
Pair(6, 1), Pair(6, 2), Pair(6, 3), Pair(6, 4), Pair(6, 5), Pair(6, 6),
Pair(7, 1), Pair(7, 2), Pair(7, 3), Pair(7, 4), Pair(7, 5), Pair(7, 6), Pair(7, 7)
)
for ((n, m) in nms) {
println("$m black and $m white queens on a $n x $n board:")
val blackQueens = mutableListOf<Position>()
val whiteQueens = mutableListOf<Position>()
if (place(m, n, blackQueens, whiteQueens)) {
printBoard(n, blackQueens, whiteQueens)
} else {
println("No solution exists.\n")
}
}
}
{{out}}
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 • ◦ •
Perl
#!/usr/bin/perl
use strict; # http://www.rosettacode.org/wiki/Peaceful_chess_queen_armies
use warnings;
my $m = shift // 4;
my $n = shift // 5;
my %seen;
my $gaps = join '|', qr/-*/, map qr/.{$_}(?:-.{$_})*/sx, $n-1, $n, $n+1;
my $attack = qr/(\w)(?:$gaps)(?!\1)\w/;
place( scalar +('-' x $n . "\n") x $n );
print "No solution to $m $n\n";
sub place
{
local $_ = shift;
$seen{$_}++ || /$attack/ and return; # previously or attack
(my $have = tr/WB//) < $m * 2 or exit !print "Solution to $m $n\n\n$_";
place( s/-\G/ qw(W B)[$have % 2] /er ) while /-/g; # place next queen
}
{{out}}
Solution to 4 5
W---W
--B--
-B-B-
--B--
W---W
Phix
{{trans|Go}} {{trans|Python}}
-- demo\rosetta\Queen_Armies.exw
string html = ""
constant as_html = true
constant queens = {``,
`♛`,
`<font color="green">♕</font>`,
`<span style="color:red">?</span>`}
procedure showboard(integer n, sequence blackqueens, whitequeens)
sequence board = repeat(repeat('-',n),n)
for i=1 to length(blackqueens) do
integer {qi,qj} = blackqueens[i]
board[qi,qj] = 'B'
{qi,qj} = whitequeens[i]
board[qi,qj] = 'W'
end for
if as_html then
string out = sprintf("
<b>## %d black and %d white queens on a %d-by-%d board</b>
\n",
{length(blackqueens),length(whitequeens),n,n}),
tbl = ""
out &= "<table style=\"font-weight:bold\">\n "
for x=1 to n do
for y=1 to n do
if y=1 then tbl &= " </tr>\n <tr valign=\"middle\" align=\"center\">\n" end if
integer xw = find({x,y},blackqueens)!=0,
xb = find({x,y},whitequeens)!=0,
dx = xw+xb*2+1
string ch = queens[dx],
bg = iff(mod(x+y,2)?"":` bgcolor="silver"`)
tbl &= sprintf(" <td style=\"width:14pt; height:14pt;\"%s>%s</td>\n",{bg,ch})
end for
end for
out &= tbl[11..$]
out &= " </tr>\n</table>\n
\n"
html &= out
else
integer b = length(blackqueens),
w = length(whitequeens)
printf(1,"%d black and %d white queens on a %d x %d board:\n", {b, w, n, n})
puts(1,join(board,"\n")&"\n")
-- ?{n,blackqueens, whitequeens}
end if
end procedure
function isAttacking(sequence queen, pos)
integer {qi,qj} = queen, {pi,pj} = pos
return qi=pi or qj=pj or abs(qi-pi)=abs(qj-pj)
end function
function place(integer m, n, sequence blackqueens = {}, whitequeens = {})
if m == 0 then showboard(n,blackqueens,whitequeens) return true end if
bool placingBlack := true
for i=1 to n do
for j=1 to n do
sequence pos := {i, j}
for q=1 to length(blackqueens) do
sequence queen := blackqueens[q]
if queen == pos or ((not placingBlack) and isAttacking(queen, pos)) then
pos = {}
exit
end if
end for
if pos!={} then
for q=1 to length(whitequeens) do
sequence queen := whitequeens[q]
if queen == pos or (placingBlack and isAttacking(queen, pos)) then
pos = {}
exit
end if
end for
if pos!={} then
if placingBlack then
blackqueens = append(blackqueens, pos)
placingBlack = false
else
whitequeens = append(whitequeens, pos)
if place(m-1, n, blackqueens, whitequeens) then return true end if
blackqueens = blackqueens[1..$-1]
whitequeens = whitequeens[1..$-1]
placingBlack = true
end if
end if
end if
end for
end for
return false
end function
for n=2 to 7 do
for m=1 to n-(n<5) do
if not place(m,n) then
string no = sprintf("Cannot place %d+ queen armies on a %d-by-%d board",{m,n,n})
if as_html then
html &= sprintf("<b># %s</b>
\n\n",{no})
else
printf(1,"%s.\n", {no})
end if
end if
end for
end for
constant html_header = """
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>Rosettacode Rank Languages by popularity</title>
</head>
<body>
<h2>queen armies</h2>
""", -- or <div style="overflow:scroll; height:250px;">
html_footer = """
</body>
</html>
""" -- or </div>
if as_html then
integer fn = open("queen_armies.html","w")
puts(fn,html_header)
puts(fn,html)
puts(fn,html_footer)
close(fn)
printf(1,"See queen_armies.html\n")
end if
?"done"
{} = wait_key()
{{out}} with as_html = false
Cannot place 1+ queen armies on a 2-by-2 board.
1 black and 1 white queens on a 3 x 3 board:
B--
--W
---
Cannot place 2+ queen armies on a 3-by-3 board.
<snip>
7 black and 7 white queens on a 7 x 7 board:
-B---B-
-B--B--
-B---B-
----B--
W-W---W
---W---
W-WW---
{{out}} with as_html = true
# Cannot place 1+ queen armies on a 2-by-2 board
## 1 black and 1 white queens on a 3-by-3 board
| ♛ | ||
| ♕ | ||
# Cannot place 2+ queen armies on a 3-by-3 board
<snip>
## 7 black and 7 white queens on a 7-by-7 board
| ♛ | ♛ | |||||
| ♛ | ♛ | |||||
| ♛ | ♛ | |||||
| ♛ | ||||||
| ♕ | ♕ | ♕ | ||||
| ♕ | ||||||
| ♕ | ♕ | ♕ |
Python
Python: Textual output
from itertools import combinations, product, count
from functools import lru_cache, reduce
_bbullet, _wbullet = '\u2022\u25E6'
_or = set.__or__
def place(m, n):
"Place m black and white queens, peacefully, on an n-by-n board"
board = set(product(range(n), repeat=2)) # (x, y) tuples
placements = {frozenset(c) for c in combinations(board, m)}
for blacks in placements:
black_attacks = reduce(_or,
(queen_attacks_from(pos, n) for pos in blacks),
set())
for whites in {frozenset(c) # Never on blsck attacking squares
for c in combinations(board - black_attacks, m)}:
if not black_attacks & whites:
return blacks, whites
return set(), set()
@lru_cache(maxsize=None)
def queen_attacks_from(pos, n):
x0, y0 = pos
a = set([pos]) # Its position
a.update((x, y0) for x in range(n)) # Its row
a.update((x0, y) for y in range(n)) # Its column
# Diagonals
for x1 in range(n):
# l-to-r diag
y1 = y0 -x0 +x1
if 0 <= y1 < n:
a.add((x1, y1))
# r-to-l diag
y1 = y0 +x0 -x1
if 0 <= y1 < n:
a.add((x1, y1))
return a
def pboard(black_white, n):
"Print board"
if black_white is None:
blk, wht = set(), set()
else:
blk, wht = black_white
print(f"## {len(blk)} black and {len(wht)} white queens "
f"on a {n}-by-{n} board:", end='')
for x, y in product(range(n), repeat=2):
if y == 0:
print()
xy = (x, y)
ch = ('?' if xy in blk and xy in wht
else 'B' if xy in blk
else 'W' if xy in wht
else _bbullet if (x + y)%2 else _wbullet)
print('%s' % ch, end='')
print()
if __name__ == '__main__':
n=2
for n in range(2, 7):
print()
for m in count(1):
ans = place(m, n)
if ans[0]:
pboard(ans, n)
else:
print (f"# Can't place {m}+ queens on a {n}-by-{n} board")
break
#
print('\n')
m, n = 5, 7
ans = place(m, n)
pboard(ans, n)
{{out}}
# Can't place 1+ queens on a 2-by-2 board
## 1 black and 1 white queens on a 3-by-3 board:
◦•◦
B◦•
◦•W
# Can't place 2+ queens on a 3-by-3 board
## 1 black and 1 white queens on a 4-by-4 board:
◦•W•
B◦•◦
◦•◦•
•◦•◦
## 2 black and 2 white queens on a 4-by-4 board:
◦B◦•
•B•◦
◦•◦•
W◦W◦
# Can't place 3+ queens on a 4-by-4 board
## 1 black and 1 white queens on a 5-by-5 board:
◦•◦•◦
W◦•◦•
◦•◦•◦
•◦•◦B
◦•◦•◦
## 2 black and 2 white queens on a 5-by-5 board:
◦•◦•W
•◦B◦•
◦•◦•◦
•◦•B•
◦W◦•◦
## 3 black and 3 white queens on a 5-by-5 board:
◦W◦•◦
•◦•◦W
B•B•◦
B◦•◦•
◦•◦W◦
## 4 black and 4 white queens on a 5-by-5 board:
◦•B•B
W◦•◦•
◦W◦W◦
W◦•◦•
◦•B•B
# Can't place 5+ queens on a 5-by-5 board
## 1 black and 1 white queens on a 6-by-6 board:
◦•◦•◦•
W◦•◦•◦
◦•◦•◦•
•◦•◦B◦
◦•◦•◦•
•◦•◦•◦
## 2 black and 2 white queens on a 6-by-6 board:
◦•◦•◦•
•◦B◦•◦
◦•◦•◦•
•◦•B•◦
◦•◦•◦•
W◦•◦W◦
## 3 black and 3 white queens on a 6-by-6 board:
◦•B•◦•
•B•◦•◦
◦•◦W◦W
•◦•◦•◦
W•◦•◦•
•◦•◦B◦
## 4 black and 4 white queens on a 6-by-6 board:
WW◦•W•
•W•◦•◦
◦•◦•◦B
•◦B◦•◦
◦•◦B◦•
•◦•B•◦
## 5 black and 5 white queens on a 6-by-6 board:
◦•W•W•
B◦•◦•◦
◦•W•◦W
B◦•◦•◦
◦•◦•◦W
BB•B•◦
# Can't place 6+ queens on a 6-by-6 board
## 5 black and 5 white queens on a 7-by-7 board:
◦•◦•B•◦
•W•◦•◦W
◦•◦•B•◦
B◦•◦•◦•
◦•B•◦•◦
•◦•B•◦•
◦W◦•◦WW
Python: HTML output
Uses the solver function place from the above textual output case.
from peaceful_queen_armies_simpler import place
from itertools import product, count
_bqueenh, _wqueenh = '♛', '<font color="green">♕</font>'
def hboard(black_white, n):
"HTML board generator"
if black_white is None:
blk, wht = set(), set()
else:
blk, wht = black_white
out = (f"
<b>## {len(blk)} black and {len(wht)} white queens "
f"on a {n}-by-{n} board</b>
\n")
out += '<table style="font-weight:bold">\n '
tbl = ''
for x, y in product(range(n), repeat=2):
if y == 0:
tbl += ' </tr>\n <tr valign="middle" align="center">\n'
xy = (x, y)
ch = ('<span style="color:red">?</span>' if xy in blk and xy in wht
else _bqueenh if xy in blk
else _wqueenh if xy in wht
else "")
bg = "" if (x + y)%2 else ' bgcolor="silver"'
tbl += f' <td style="width:14pt; height:14pt;"{bg}>{ch}</td>\n'
out += tbl[7:]
out += ' </tr>\n</table>\n
\n'
return out
if __name__ == '__main__':
n=2
html = ''
for n in range(2, 7):
print()
for m in count(1):
ans = place(m, n)
if ans[0]:
html += hboard(ans, n)
else:
html += (f"<b># Can't place {m}+ queen armies on a "
f"{n}-by-{n} board</b>
\n\n" )
break
#
html += '
\n'
m, n = 6, 7
ans = place(m, n)
html += hboard(ans, n)
with open('peaceful_queen_armies.htm', 'w') as f:
f.write(html)
{{out}}
# Can't place 1+ queen armies on a 2-by-2 board
## 1 black and 1 white queens on a 3-by-3 board
| ♛ | ||
| ♕ |
# Can't place 2+ queen armies on a 3-by-3 board
## 1 black and 1 white queens on a 4-by-4 board
| ♕ | |||
| ♛ | |||
## 2 black and 2 white queens on a 4-by-4 board
| ♛ | |||
| ♛ | |||
| ♕ | ♕ |
# Can't place 3+ queen armies on a 4-by-4 board
## 1 black and 1 white queens on a 5-by-5 board
| ♕ | ||||
| ♛ | ||||
## 2 black and 2 white queens on a 5-by-5 board
| ♕ | ||||
| ♛ | ||||
| ♛ | ||||
| ♕ |
## 3 black and 3 white queens on a 5-by-5 board
| ♕ | ||||
| ♕ | ||||
| ♛ | ♛ | |||
| ♛ | ||||
| ♕ |
## 4 black and 4 white queens on a 5-by-5 board
| ♛ | ♛ | |||
| ♕ | ||||
| ♕ | ♕ | |||
| ♕ | ||||
| ♛ | ♛ |
# Can't place 5+ queen armies on a 5-by-5 board
## 1 black and 1 white queens on a 6-by-6 board
| ♕ | |||||
| ♛ | |||||
## 2 black and 2 white queens on a 6-by-6 board
| ♛ | |||||
| ♛ | |||||
| ♕ | ♕ |
## 3 black and 3 white queens on a 6-by-6 board
| ♛ | |||||
| ♛ | |||||
| ♕ | ♕ | ||||
| ♕ | |||||
| ♛ |
## 4 black and 4 white queens on a 6-by-6 board
| ♕ | ♕ | ♕ | |||
| ♕ | |||||
| ♛ | |||||
| ♛ | |||||
| ♛ | |||||
| ♛ |
## 5 black and 5 white queens on a 6-by-6 board
| ♕ | ♕ | ||||
| ♛ | |||||
| ♕ | ♕ | ||||
| ♛ | |||||
| ♕ | |||||
| ♛ | ♛ | ♛ |
# Can't place 6+ queen armies on a 6-by-6 board
## 6 black and 6 white queens on a 7-by-7 board
| ♛ | ♛ | |||||
| ♕ | ||||||
| ♕ | ♕ | ♕ | ||||
| ♕ | ||||||
| ♛ | ♛ | |||||
| ♕ | ||||||
| ♛ | ♛ |
zkl
fcn isAttacked(q, x,y) // ( (r,c), x,y ) : is queen at r,c attacked by q@(x,y)?
{ r,c:=q; (r==x or c==y or r+c==x+y or r-c==x-y) }
fcn isSafe(r,c,qs) // queen safe at (r,c)?, qs=( (r,c),(r,c)..)
{ ( not qs.filter1(isAttacked,r,c) ) }
fcn isEmpty(r,c,qs){ (not (qs and qs.filter1('wrap([(x,y)]){ r==x and c==y })) ) }
fcn _peacefulQueens(N,M,qa,qb){ //--> False | (True,((r,c)..),((r,c)..) )
// qa,qb --> // ( (r,c),(r,c).. ), solution so far to last good spot
if(qa.len()==M==qb.len()) return(True,qa,qb);
n, x,y := N, 0,0;
if(qa) x,y = qa[-1]; else n=(N+1)/2; // first queen, first quadrant only
foreach r in ([x..n-1]){
foreach c in ([y..n-1]){
if(isEmpty(r,c,qa) and isSafe(r,c,qb)){
qc,qd := qa.append(T(r,c)), self.fcn(N,M, qb,qc);
if(qd) return( if(qd[0]==True) qd else T(qc,qd) );
}
}
y=0
}
False
}
fcn peacefulQueens(N=5,M=4){ # NxN board, M white and black queens
qs:=_peacefulQueens(N,M, T,T);
println("Solution for %dx%d board with %d black and %d white queens:".fmt(N,N,M,M));
if(not qs)println("None");
else{
z:=Data(Void,"-"*N*N);
foreach r,c in (qs[1]){ z[r*N + c]="W" }
foreach r,c in (qs[2]){ z[r*N + c]="B" }
z.text.pump(Void,T(Void.Read,N-1),"println");
}
}
peacefulQueens();
foreach n in ([4..10]){ peacefulQueens(n,n) }
{{out}}
Solution for 5x5 board with 4 black and 4 white queens:
W---W
--B--
-B-B-
--B--
W---W
Solution for 4x4 board with 4 black and 4 white queens:
None
Solution for 5x5 board with 5 black and 5 white queens:
None
Solution for 6x6 board with 6 black and 6 white queens:
None
Solution for 7x7 board with 7 black and 7 white queens:
W---W-W
--B----
-B-B-B-
--B----
W-----W
--BB---
W-----W
Solution for 8x8 board with 8 black and 8 white queens:
W---W---
--B---BB
W---W---
--B---B-
---B---B
-W---W--
W---W---
--B-----
Solution for 9x9 board with 9 black and 9 white queens:
W---W---W
--B---B--
-B---B---
---W---W-
-B---B---
---W---W-
-B---B---
---W---W-
-B-------
Solution for 10x10 board with 10 black and 10 white queens:
W---W---WW
--B---B---
-B-B------
-----W-W-W
-BBB------
-----W-W-W
-B--------
------B---
---B------
----------