Peaceful chess queen armies: Difference between revisions
m (→{{header|zkl}}: opto) |
(→{{header|Go}}: Replaced existing solution with simpler and infinitely faster one.) |
||
Line 53: | Line 53: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
This is based on the C# code [https://www.reddit.com/r/coding/comments/b5eu7w/peaceful_chess_queen_armies_new_draft_rosetta/ here]. |
|||
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. |
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. |
||
Line 75: | Line 73: | ||
) |
) |
||
type position struct{ i, j int } |
|||
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 |
func iabs(i int) int { |
||
if i < 0 { |
|||
return -i |
|||
for i, j := 0, len(ba)-1; i < j; i, j = i+1, j-1 { |
|||
ba[i], ba[j] = ba[j], ba[i] |
|||
} |
} |
||
return |
return i |
||
} |
} |
||
func |
func place(m, n int, pBlackQueens, pWhiteQueens *[]position) bool { |
||
if m == 0 { |
|||
return true |
|||
col2 = white |
|||
} |
} |
||
placingBlack := true |
|||
for i := 0; i < n; i++ { |
|||
inner: |
|||
for _, b := range board { |
|||
for j := 0; j < n; j++ { |
|||
pos := position{i, j} |
|||
for |
for _, queen := range *pBlackQueens { |
||
if queen == pos || !placingBlack && isAttacking(queen, pos) { |
|||
continue inner |
|||
return false |
|||
} |
|||
if board[k] == col { |
|||
break |
|||
} |
} |
||
} |
} |
||
for _, queen := range *pWhiteQueens { |
|||
if queen == pos || placingBlack && isAttacking(queen, pos) { |
|||
continue inner |
|||
if board[k] == col2 { |
|||
return false |
|||
} |
|||
if board[k] == col { |
|||
break |
|||
} |
} |
||
} |
} |
||
if placingBlack { |
|||
*pBlackQueens = append(*pBlackQueens, pos) |
|||
placingBlack = false |
|||
} else { |
|||
*pWhiteQueens = append(*pWhiteQueens, pos) |
|||
if place(m-1, n, pBlackQueens, pWhiteQueens) { |
|||
return true |
|||
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 |
|||
} |
} |
||
*pBlackQueens = (*pBlackQueens)[0 : len(*pBlackQueens)-1] |
|||
*pWhiteQueens = (*pWhiteQueens)[0 : len(*pWhiteQueens)-1] |
|||
placingBlack = true |
|||
} |
} |
||
} |
} |
||
} |
} |
||
if !placingBlack { |
|||
return true |
|||
*pBlackQueens = (*pBlackQueens)[0 : len(*pBlackQueens)-1] |
|||
} |
|||
return false |
|||
} |
} |
||
func |
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 { |
for i, b := range board { |
||
if i != 0 && i%n == 0 { |
if i != 0 && i%n == 0 { |
||
Line 251: | Line 166: | ||
nms := [][2]int{ |
nms := [][2]int{ |
||
{2, 1}, {3, 1}, {3, 2}, {4, 1}, {4, 2}, {4, 3}, |
{2, 1}, {3, 1}, {3, 2}, {4, 1}, {4, 2}, {4, 3}, |
||
{5, 1}, {5, 2}, {5, 3}, {5, 4}, |
{5, 1}, {5, 2}, {5, 3}, {5, 4}, {5, 5}, |
||
{6, 1}, {6, 2}, {6, 3}, {6, 4}, {6, 5}, |
{6, 1}, {6, 2}, {6, 3}, {6, 4}, {6, 5}, {6, 6}, |
||
{7, 1}, {7, 2}, {7, 3}, {7, 4}, {7, 5}, |
{7, 1}, {7, 2}, {7, 3}, {7, 4}, {7, 5}, {7, 6}, {7, 7}, |
||
} |
} |
||
for _, nm := range nms { |
for _, nm := range nms { |
||
n, m := nm[0], nm[1] |
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) |
fmt.Printf("%d black and %d white queens on a %d x %d board:\n", m, m, n, n) |
||
var blackQueens, whiteQueens []position |
|||
// get all combinations of m black queens on n * n squares |
|||
if place(m, n, &blackQueens, &whiteQueens) { |
|||
printBoard(n, blackQueens, whiteQueens) |
|||
} else { |
|||
} |
|||
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") |
fmt.Println("No solution exists.\n") |
||
} |
} |
||
Line 336: | Line 203: | ||
2 black and 2 white queens on a 4 x 4 board: |
2 black and 2 white queens on a 4 x 4 board: |
||
B |
B ◦ • ◦ |
||
• ◦ |
• ◦ W ◦ |
||
B ◦ • ◦ |
|||
• ◦ W ◦ |
• ◦ W ◦ |
||
Line 352: | Line 219: | ||
2 black and 2 white queens on a 5 x 5 board: |
2 black and 2 white queens on a 5 x 5 board: |
||
B |
B ◦ • ◦ B |
||
◦ • |
◦ • W • ◦ |
||
• |
• W • ◦ • |
||
◦ • ◦ • ◦ |
◦ • ◦ • ◦ |
||
• ◦ • ◦ • |
• ◦ • ◦ • |
||
3 black and 3 white queens on a 5 x 5 board: |
3 black and 3 white queens on a 5 x 5 board: |
||
B |
B ◦ • ◦ B |
||
◦ • ◦ • ◦ |
|||
• ◦ • ◦ W |
|||
◦ • W • ◦ |
◦ • W • ◦ |
||
• |
• W • ◦ • |
||
◦ • ◦ B ◦ |
|||
• W • ◦ • |
|||
4 black and 4 white queens on a 5 x 5 board: |
4 black and 4 white queens on a 5 x 5 board: |
||
B |
• 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: |
1 black and 1 white queens on a 6 x 6 board: |
||
Line 381: | Line 251: | ||
2 black and 2 white queens on a 6 x 6 board: |
2 black and 2 white queens on a 6 x 6 board: |
||
B |
B ◦ • ◦ B ◦ |
||
• ◦ |
• ◦ W ◦ • ◦ |
||
• |
• W • ◦ • ◦ |
||
• ◦ • ◦ • ◦ |
• ◦ • ◦ • ◦ |
||
• ◦ • ◦ • ◦ |
• ◦ • ◦ • ◦ |
||
Line 389: | Line 259: | ||
3 black and 3 white queens on a 6 x 6 board: |
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: |
4 black and 4 white queens on a 6 x 6 board: |
||
B ◦ • ◦ B B |
|||
• |
• ◦ W ◦ • ◦ |
||
• |
• W • ◦ • ◦ |
||
• ◦ • ◦ • B |
|||
• ◦ W W • ◦ |
|||
• ◦ • ◦ • ◦ |
• ◦ • ◦ • ◦ |
||
• ◦ • W • ◦ |
|||
• ◦ • W W ◦ |
|||
5 black and 5 white queens on a 6 x 6 board: |
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: |
1 black and 1 white queens on a 7 x 7 board: |
||
Line 422: | Line 295: | ||
2 black and 2 white queens on a 7 x 7 board: |
2 black and 2 white queens on a 7 x 7 board: |
||
B |
B ◦ • ◦ B ◦ • |
||
◦ • |
◦ • W • ◦ • W |
||
• ◦ • ◦ • ◦ • |
• ◦ • ◦ • ◦ • |
||
◦ • ◦ • ◦ • ◦ |
◦ • ◦ • ◦ • ◦ |
||
Line 431: | Line 304: | ||
3 black and 3 white queens on a 7 x 7 board: |
3 black and 3 white queens on a 7 x 7 board: |
||
B |
B ◦ • ◦ B ◦ • |
||
◦ • |
◦ • W • ◦ • W |
||
B ◦ • ◦ • ◦ • |
|||
◦ • |
◦ • W • ◦ • ◦ |
||
• ◦ • ◦ • ◦ • |
• ◦ • ◦ • ◦ • |
||
◦ • ◦ • ◦ • ◦ |
◦ • ◦ • ◦ • ◦ |
||
Line 440: | Line 313: | ||
4 black and 4 white queens on a 7 x 7 board: |
4 black and 4 white queens on a 7 x 7 board: |
||
B |
B ◦ • ◦ B ◦ • |
||
◦ • |
◦ • W • ◦ • W |
||
B ◦ • ◦ B ◦ • |
|||
◦ • W • ◦ • W |
|||
• ◦ • ◦ • ◦ • |
|||
◦ • ◦ • ◦ • ◦ |
◦ • ◦ • ◦ • ◦ |
||
• ◦ • ◦ • ◦ • |
|||
◦ • ◦ • W • ◦ |
|||
• ◦ • ◦ • ◦ • |
• ◦ • ◦ • ◦ • |
||
5 black and 5 white queens on a 7 x 7 board: |
5 black and 5 white queens on a 7 x 7 board: |
||
B |
B ◦ • ◦ B ◦ • |
||
◦ • |
◦ • W • ◦ • W |
||
B ◦ • ◦ B ◦ • |
|||
◦ • |
◦ • W • ◦ • W |
||
B ◦ • ◦ • ◦ • |
|||
◦ • W • ◦ • ◦ |
|||
• ◦ • ◦ • ◦ • |
• ◦ • ◦ • ◦ • |
||
◦ • ◦ • W • ◦ |
|||
6 black and 6 white queens on a 7 x 7 board: |
|||
• ◦ • ◦ W W • |
|||
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> |
</pre> |
||
</div> |
</div> |
Revision as of 17:08, 8 April 2019
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
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(); 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