Peaceful chess queen armies
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
m
equal numbers of black and white queens on ann
square board. - Display here results for the
m=4, n=5
case.
- Ref.
- Peaceably Coexisting Armies of Queens (Pdf) by Robert A. Bosch. Optima, the Mathematical Programming Socity newsletter, issue 62.
- A250000 OEIS
Go
Basically a brute force approach but adjusted to remove duplicate (or mirror image) combinations of black queens from consideration. A similar adjustment including the white queens was found to be too costly to implement.
Not very quick when an exhaustive search is required to show that a particular case has no solution. Accordingly, the cases {m = 5, n = 5} and {m = 6, n = 6} have been omitted as they take several minutes to run on my modest machine and are not part of the task requirements in any case.
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 = '◦'
)
var bcombos [][]int var wcombos [][]int
func combinations(in []int, k, start, col int, out []int) {
if k == 0 { combo := make([]int, len(out)) copy(combo, out) if col == black { bcombos = append(bcombos, combo) } else { wcombos = append(wcombos, combo) } return } n := len(in) for i := start; i+k <= n; i++ { out[len(out)-k] = in[i] combinations(in, k-1, i+1, col, out) }
}
func board2String(in []int) string {
le := len(in) ba := make([]byte, le) for i := 0; i < le; i++ { ba[i] = byte(in[i] + 48) } return string(ba)
}
func reverse(s string) string {
ba := []byte(s) for i, j := 0, len(ba)-1; i < j; i, j = i+1, j-1 { ba[i], ba[j] = ba[j], ba[i] } return string(ba)
}
func isPeaceful(n, pos, col int, board []int) bool {
col2 := black if col == black { col2 = white } r := pos / n c := pos - r*n for _, b := range board { if b != empty { // center right direction for j := c + 1; j < n; j++ { k := r*n + j if board[k] == col2 { return false } if board[k] == col { break } } // center left direction for j := c - 1; j >= 0; j-- { k := r*n + j if board[k] == col2 { return false } if board[k] == col { break } } // bottom right direction l := c for j := r + 1; j < n; j++ { l++ if l == n { break } k := j*n + l if board[k] == col2 { return false } if board[k] == col { break } } // bottom center direction for j := r + 1; j < n; j++ { k := j*n + c if board[k] == col2 { return false } if board[k] == col { break } } // bottom left direction l = c for j := r + 1; j < n; j++ { l-- if l == -1 { break } k := j*n + l if board[k] == col2 { return false } if board[k] == col { break } } // top right direction l = c for j := r - 1; j >= 0; j-- { l++ if l == n { break } k := j*n + l if board[k] == col2 { return false } if board[k] == col { break } } // top center direction for j := r - 1; j >= 0; j-- { k := j*n + c if board[k] == col2 { return false } if board[k] == col { break } } // top left direction l = c for j := r - 1; j >= 0; j-- { l-- if l == -1 { break } k := j*n + l if board[k] == col2 { return false } if board[k] == col { break } } } } return true
}
func printBoard(n int, board []int) {
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}, {6, 1}, {6, 2}, {6, 3}, {6, 4}, {6, 5}, {7, 1}, {7, 2}, {7, 3}, {7, 4}, {7, 5}, } for _, nm := range nms { n, m := nm[0], nm[1] n2 := n * n success := false fmt.Printf("%d black and %d white queens on a %d x %d board:\n", m, m, n, n) // get all combinations of m black queens on n * n squares in := make([]int, n2) for i := 0; i < n2; i++ { in[i] = i } out := make([]int, m) bcombos = nil combinations(in, m, 0, black, out) bmap := make(map[string]bool) outer: for _, bcombo := range bcombos { bboard := make([]int, n2) for _, c := range bcombo { bboard[c] = black } s := board2String(bboard) if bmap[s] || bmap[reverse(s)] { continue } bmap[s] = true // now get all combinations of m white queens in remaining squares in = in[:0] for i, c := range bboard { if c == empty { in = append(in, i) } } wboard := make([]int, n2) wcombos = nil combinations(in, m, 0, white, out) for _, wcombo := range wcombos { copy(wboard, bboard) for _, c := range wcombo { wboard[c] = white } allPeaceful := true for i, c := range wboard { if c != empty && !isPeaceful(n, i, c, wboard) { allPeaceful = false break } } if allPeaceful { printBoard(n, wboard) success = true break outer } } } if !success { 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 B • ◦ • ◦ • W • ◦ • ◦ • ◦ 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 • B • ◦ • ◦ • ◦ • ◦ • ◦ W ◦ • W • ◦ • ◦ W ◦ • 4 black and 4 white queens on a 5 x 5 board: B ◦ B ◦ • ◦ • ◦ • W B ◦ B ◦ • ◦ • ◦ • W • W • W • 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 ◦ • ◦ • B • ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • W W ◦ 5 black and 5 white queens on a 6 x 6 board: B B B ◦ • ◦ • ◦ • ◦ W W • ◦ B ◦ • ◦ B ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • W W ◦ 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 B ◦ • ◦ • ◦ • ◦ • W W W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 4 black and 4 white queens on a 7 x 7 board: B B B B • ◦ • ◦ • ◦ • ◦ W W • ◦ • ◦ • ◦ W ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • 5 black and 5 white queens on a 7 x 7 board: B B B B • ◦ • ◦ • ◦ • ◦ W W • ◦ B ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 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(); peacefulQueens(4,4); peacefulQueens(6,5); peacefulQueens(6,6); peacefulQueens(7,7);</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 6x6 board with 5 black and 5 white queens: W----- --B--B ----BB ----B- WW---- W--W-- 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