Peaceful chess queen armies

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

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

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------
----------