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


enum Piece {
  case empty, black, white
}
 
typealias Position = (Int, Int)
 
func place(_ m: Int, _ n: Int, pBlackQueens: inout [Position], pWhiteQueens: inout [Position]) -> Bool {
  guard m != 0 else {
    return true
  }
 
  var placingBlack = true
 
  for i in 0..<n {
    inner: for j in 0..<n {
      let pos = (i, j)
 
      for queen in pBlackQueens where queen == pos || !placingBlack && isAttacking(queen, pos) {
        continue inner
      }
 
      for queen in pWhiteQueens where queen == pos || placingBlack && isAttacking(queen, pos) {
        continue inner
      }
 
      if placingBlack {
        pBlackQueens.append(pos)
        placingBlack = false
      } else {
        placingBlack = true
 
        pWhiteQueens.append(pos)
 
        if place(m - 1, n, pBlackQueens: &pBlackQueens, pWhiteQueens: &pWhiteQueens) {
          return true
        } else {
          pBlackQueens.removeLast()
          pWhiteQueens.removeLast()
        }
      }
    }
  }
 
  if !placingBlack {
    pBlackQueens.removeLast()
  }
 
  return false
}
 
func isAttacking(_ queen: Position, _ pos: Position) -> Bool {
  queen.0 == pos.0 || queen.1 == pos.1 || abs(queen.0 - pos.0) == abs(queen.1 - pos.1)
}
 
func printBoard(n: Int, pBlackQueens: [Position], pWhiteQueens: [Position]) {
  var board = Array(repeating: Piece.empty, count: n * n)
 
  for queen in pBlackQueens {
    board[queen.0 * n + queen.1] = .black
  }
 
  for queen in pWhiteQueens {
    board[queen.0 * n + queen.1] = .white
  }
 
  for (i, p) in board.enumerated() {
    if i != 0 && i % n == 0 {
      print()
    }
 
    switch p {
    case .black:
      print("B ", terminator: "")
    case .white:
      print("W ", terminator: "")
    case .empty:
      let j = i / n
      let k = i - j * n
 
      if j % 2 == k % 2 {
        print("• ", terminator: "")
      } else {
        print("◦ ", terminator: "")
      }
    }
  }
 
  print("\n")
}
 
let 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)
]
 
for (n, m) in nms {
  print("\(m) black and white queens on \(n) x \(n) board")
 
  var blackQueens = [Position]()
  var whiteQueens = [Position]()
 
  if place(m, n, pBlackQueens: &blackQueens, pWhiteQueens: &whiteQueens) {
    printBoard(n: n, pBlackQueens: blackQueens, pWhiteQueens: whiteQueens)
  } else {
    print("No solution")
  }
}