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


use strict;
use warnings;
 
my $m = shift // 4;
my $n = shift // 5;
my %seen;
my $gaps = join '|', qr/-*/, map qr/.{$_}(?:-.{$_})*/s, $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
  }