Peaceful chess queen armies
You are encouraged to solve this task according to the task description, using any language you may know.
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.
- Detail
- 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
mequal numbers of black and white queens on annsquare board. - Display here results for the
m=4, n=5case.
- Ref.
- Peaceably Coexisting Armies of Queens (Pdf) by Robert A. Bosch. Optima, the Mathematical Programming Socity newsletter, issue 62.
- A250000 OEIS
Go
This is based on the C# code 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. <lang go>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")
}
}
}</lang>
- Output:
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
<lang 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
}</lang>
- Output:
Solution to 4 5 W---W --B-- -B-B- --B-- W---W
Python
Python: Textual output
<lang python>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)</lang>
- Output:
# 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.
<lang python>from peaceful_queen_armies_simpler import place
from itertools import product, count
_bqueenh, _wqueenh = '♛', '♕'
def hboard(black_white, n):
"HTML board generator"
if black_white is None:
blk, wht = set(), set()
else:
blk, wht = black_white
out = (f"
## {len(blk)} black and {len(wht)} white queens "
f"on a {n}-by-{n} board
\n")
out += '
\n ' tbl = for x, y in product(range(n), repeat=2): if y == 0: tbl += ' \n \n' xy = (x, y) ch = ('?' 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' \n'out += tbl[7:]out += ' \n
| {ch} |
\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"# Can't place {m}+ queen armies on a "
f"{n}-by-{n} board
\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)</lang>
- Output:
# 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
<lang 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");
}
}</lang> <lang zkl>peacefulQueens(); foreach n in ([4..10]){ peacefulQueens(n,n) }</lang>
- Output:
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------ ----------