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.



Task

 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 an n square board.
 Display here results for the m=4, n=5 case.


References

 Peaceably Coexisting Armies of Queens (Pdf) by Robert A. Bosch. Optima, the Mathematical Programming Socity newsletter, issue 62.
 A250000 OEIS


T.enum Piece
   EMPTY
   BLACK
   WHITE
 
F isAttacking(queen, pos)
   R queen.x == pos.x
   | queen.y == pos.y
   | abs(queen.x - pos.x) == abs(queen.y - pos.y)
 
F place(m, n, &pBlackQueens, &pWhiteQueens)
   I m == 0
      R 1B
 
   V placingBlack = 1B
   L(i) 0 .< n
      L(j) 0 .< n
         V pos = (i, j)
         L(queen) pBlackQueens
            I queen == pos | (!placingBlack & isAttacking(queen, pos))
               L.break
         L.was_no_break
            L(queen) pWhiteQueens
               I queen == pos | (placingBlack & isAttacking(queen, pos))
                  L.break
            L.was_no_break
               I placingBlack
                  pBlackQueens [+]= pos
                  placingBlack = 0B
               E
                  pWhiteQueens [+]= pos
                  I place(m - 1, n, &pBlackQueens, &pWhiteQueens)
                     R 1B
                  pBlackQueens.pop()
                  pWhiteQueens.pop()
                  placingBlack = 1B
 
   I !placingBlack
      pBlackQueens.pop()
   R 0B
 
F printBoard(n, blackQueens, whiteQueens)
   V board = [Piece.EMPTY] * (n * n)
 
   L(queen) blackQueens
      board[queen.x * n + queen.y] = Piece.BLACK
 
   L(queen) whiteQueens
      board[queen.x * n + queen.y] = Piece.WHITE
 
   L(b) board
      V i = L.index
      I i != 0 & i % n == 0
         print()
      I b == BLACK
         print(‘B ’, end' ‘’)
      E I b == WHITE
         print(‘W ’, end' ‘’)
      E
         V j = i I/ n
         V k = i - j * n
         I j % 2 == k % 2
            print(‘x ’, end' ‘’)
         E
            print(‘o ’, end' ‘’)
   print("\n")
 
V nms = [
          (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)
        ]
 
L(nm) nms
   print(‘#. black and #. white queens on a #. x #. board:’.format(nm[1], nm[1], nm[0], nm[0]))
   [(Int, Int)] blackQueens, whiteQueens
   I place(nm[1], nm[0], &blackQueens, &whiteQueens)
      printBoard(nm[0], blackQueens, whiteQueens)
   E
      print("No solution exists.\n")