Peaceful chess queen armies

Peaceful chess queen armies is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

1. 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).
2. Create a routine to generate at least one solution to placing m equal numbers of black and white queens on an n square board.
3. 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 • 

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

		♛		♛
						♕
	♕		♕		♕
						♕
		♛		♛
						♕
♛				♛