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


--
-- demo\rosetta\Queen_Armies.exw
-- =============================
--
with javascript_semantics
requires("1.0.2") -- (puts(fn,x,false) for p2js.js)
string html = ""
constant as_html = true
constant queens = {``,
                   `♛`, 
                   `<font color="green">♕</font>`,
                   `<span style="color:red">?</span>`}

procedure showboard(integer n, sequence blackqueens, whitequeens)
    sequence board = repeat(repeat('-',n),n)
    for i=1 to length(blackqueens) do
        integer {qi,qj} = blackqueens[i]
        board[qi,qj] = 'B'
        {qi,qj} = whitequeens[i]
        board[qi,qj] = 'W'
    end for
    if as_html then
        string out = sprintf("<br><b>## %d black and %d white queens on a %d-by-%d board</b><br>\n",
                             {length(blackqueens),length(whitequeens),n,n}),
               tbl = ""
        out &= "<table style=\"font-weight:bold\">\n  "
        for x=1 to n do
            for y=1 to n do
                if y=1 then tbl &= "  </tr>\n  <tr valign=\"middle\" align=\"center\">\n" end if
                integer xw = find({x,y},blackqueens)!=0,
                        xb = find({x,y},whitequeens)!=0,
                        dx = xw+xb*2+1
                string ch = queens[dx],
                       bg = iff(mod(x+y,2)?"":` bgcolor="silver"`)
                tbl &= sprintf("    <td style=\"width:14pt; height:14pt;\"%s>%s</td>\n",{bg,ch})
            end for
        end for
        out &= tbl[11..$]
        out &= "  </tr>\n</table>\n<br>\n"
        html &= out
    else
        integer b = length(blackqueens),
                w = length(whitequeens)
        printf(1,"%d black and %d white queens on a %d x %d board:\n", {b, w, n, n})
        puts(1,join(board,"\n")&"\n")
--      ?{n,blackqueens, whitequeens}
    end if
end procedure 

function isAttacking(sequence queen, pos)
    integer {qi,qj} = queen, {pi,pj} = pos
    return qi=pi or qj=pj or abs(qi-pi)=abs(qj-pj)
end function

function place(integer m, n, sequence blackqueens = {}, whitequeens = {})
    if m == 0 then showboard(n,blackqueens,whitequeens) return true end if
    bool placingBlack := true
    for i=1 to n do
        for j=1 to n do
            sequence pos := {i, j}
            for q=1 to length(blackqueens) do
                sequence queen := blackqueens[q]
                if queen == pos or ((not placingBlack) and isAttacking(queen, pos)) then
                    pos = {}
                    exit
                end if
            end for
            if pos!={} then
                for q=1 to length(whitequeens) do
                    sequence queen := whitequeens[q]
                    if queen == pos or (placingBlack and isAttacking(queen, pos)) then
                        pos = {}
                        exit
                    end if
                end for
                if pos!={} then
                    if placingBlack then
                        blackqueens = append(deep_copy(blackqueens), pos)
                        placingBlack = false
                    else
                        whitequeens = append(deep_copy(whitequeens), pos)
                        if place(m-1, n, blackqueens, whitequeens) then return true end if
                        blackqueens = blackqueens[1..$-1]
                        whitequeens = whitequeens[1..$-1]
                        placingBlack = true
                    end if
                end if
            end if
        end for
    end for
    return false
end function

for n=2 to 7 do
    for m=1 to n-(n<5) do
        if not place(m,n) then
            string no = sprintf("Cannot place %d+ queen armies on a %d-by-%d board",{m,n,n})
            if as_html then
                html &= sprintf("<b># %s</b><br><br>\n\n",{no})
            else
                printf(1,"%s.\n", {no})
            end if
        end if
    end for
end for

constant html_header = """
<!DOCTYPE html>
<html lang="en">
 <head>
  <meta charset="utf-8" />
  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
  <title>Queen Armies</title>
 </head>
 <body>
  <h2>queen armies</h2>
""", -- or <div style="overflow:scroll; height:250px;">
         html_footer = """
 </body>
</html>
""" -- or </div>

if as_html then
    if platform()=JS then
        puts(1,html,false)
    else
        integer fn = open("queen_armies.html","w")
        puts(fn,html_header)
        puts(fn,html)
        puts(fn,html_footer)
        close(fn)
        printf(1,"See queen_armies.html\n")
    end if
end if

?"done"
{} = wait_key()
