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


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");
   }   
}