N-queens minimum and knights and bishops

From Rosetta Code
N-queens minimum and knights and bishops is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

N-Queens: you've been there; done that; have the T-shirt. It is time to find the minimum number of Queens, Bishops or Knights that can be placed on an NxN board such that no piece attacks another but every unoccupied square is attacked.

For N=1 to 10 discover the minimum number of Queens, Bishops, and Knights required to fulfill the above requirement. For N=8 print out a possible solution for Queens and Bishops.

Links



F#

// Minimum knights to attack all squares not occupied on an NxN chess board. Nigel Galloway: May 12th., 2022
type att={n:uint64; g:uint64}
         static member att n g=let g=g|>Seq.fold(fun n g->n ||| (1UL<<<g)) 0UL in {n=n|>Seq.fold(fun n g->n ||| (1UL<<<g)) 0UL; g=g}
         static member (+) (n,g)=let x=n.g ||| g.g in {n=n.n ||| g.n; g=x}
let     fN g=let fG n g=[n-g-g-1;n-g-g+1;n-g+2;n-g-2;n+g+g-1;n+g+g+1;n+g-2;n+g+2]|>List.filter(fun x->0<=x && x<g*g && abs(x%g-n%g)+abs(x/g-n/g)=3)|>List.distinct|>List.map(fun n->n/2)
             let n,g=Array.init(g*g)(fun n->att.att [n/2] (fG n g)), Array.init(g*g)(fun n->att.att (fG n g) [n/2]) in (fun g->n.[g]),(fun n->g.[n])
type cand={att:att; n:int; g:int}
type Solver={n:cand seq; i:int[]; g:(int -> att) * (int -> att); e:att; l:int[]}
            member this.test()=let rec test n i g e l=match g with 0UL->(if i=this.e then Some(n,e) else None)|g when g%2UL=1UL->test n (i+((snd this.g)(this.i.[l])))(g/2UL)(e+1)(l+1) |_->test n i (g/2UL) e (l+1)
                               let n=this.n|>Seq.choose(fun n->test n n.att (this.e.g^^^n.att.g) 0 0) in if Seq.isEmpty n then None else Some(n|>Seq.minBy snd)
            member this.xP()  ={this with n=this.n|>Seq.collect(fun n->[for g in n.n..n.g do let att=n.att+((fst this.g)(this.l.[g])) in yield {n with att=att; n=g}])}
let rec slvK (n:Solver) i g l = match n.test() with Some(r,ta)->match min l (g+ta) with t when t>2*(g+1) || l<t->slvK (n.xP()) (if t<l then Some(r,ta) else i) (g+1) (min t l) |t->Some(min t l,r)
                                                   |_->slvK (n.xP()) i (g+1) l
let tC bw s (att:att)=let n=Array2D.init s s (fun n g->if (n+g)%2=bw then (if att.n &&& pown 2UL ((n*s+g)/2) > 0UL then "X" else ".") else (if att.g &&& pown 2UL ((n*s+g)/2) > 0UL then "~" else "o"))
                      for g in 0..s-1 do n.[g,0..s-1]|>Seq.iter(fun g->printf "%s" g); printfn ""
let solveK g=printfn "\nSolving for %dx%d board" g g
             let bs,ws=[|for n in g..g+g..(g*g-1)/2 do for z in 0..g+1..(g*g-1)/2-n->((n+z)/g,(n+z)%g)|],[|for n in 0..g+g..(g*g-1)/2 do for z in 0..g+1..(g*g-1)/2-n->((n+z)/g,(n+z)%g)|]
             let i,l=let n,i=[|for n in 0..g-1 do for g in 0..g-1->(n,g)|]|>Array.partition(fun(n,g)->(n+g)%2=1) in n|>Array.map(fun(n,i)->n*g+i), i|>Array.map(fun(n,i)->n*g+i)
             let t,f=System.DateTime.UtcNow,fN g
             let bK={l=Array.concat[bs|>Array.map(fun(n,i)->n*g+i);i]|>Array.distinct; i=l; e=att.att [0..i.Length-1] [0..l.Length-1]; n=bs|>Array.mapi(fun l (n,e)->let att=((fst f)(n*g+e)) in {att=att; n=l+1; g=i.Length-1}); g=fN g}
             let wK={l=Array.concat[ws|>Array.map(fun(n,i)->n*g+i);l]|>Array.distinct; i=i; e=att.att [0..l.Length-1] [0..i.Length-1]; n=ws|>Array.mapi(fun i (n,e)->let att=((fst f)(n*g+e)) in {att=att; n=i+1; g=l.Length-1}); g=fN g}
             let (rn,rb),tc=match g with 1|2->(slvK wK None 1 (g*g/2+g%2)).Value, tC 0 g
                                       |x when x%2=0->(slvK bK None 1 (g*g/2)).Value, tC 1 g 
                                       |_->let x,y=(slvK bK None 1 (g*g/2)).Value, (slvK wK None 1 (g*g/2+1)).Value in if (fst x)<(fst y) then x,tC 1 g else y,tC 0 g
             printfn "Solution found using %d knights in %A:" rn (System.DateTime.UtcNow-t); tc rb.att
for n in 1..10 do solveK n
Output:
Solving for 1x1 board
Solution found using 1 knights in 00:00:00.0331768:
X

Solving for 2x2 board
Solution found using 2 knights in 00:00:00:
Xo
oX

Solving for 3x3 board
Solution found using 4 knights in 00:00:00.0156191:
Xo.
oX~
.~.

Solving for 4x4 board
Solution found using 4 knights in 00:00:00:
~.~.
XoXo
~.~.
.~.~

Solving for 5x5 board
Solution found using 5 knights in 00:00:00:
.o.~.
~X~.~
.o.~.
~X~.~
.o.~.

Solving for 6x6 board
Solution found using 8 knights in 00:00:00:
~.~.~.
.~.~.~
oX~.oX
Xo.~Xo
~.~.~.
.~.~.~

Solving for 7x7 board
Solution found using 13 knights in 00:00:00.1426817:
X~.~.o.
oX~.~.~
X~.~.o.
~.~.~Xo
.~.~.~.
o.oX~.~
.~.o.~X

Solving for 8x8 board
Solution found using 14 knights in 00:00:00.2655969:
o.~X~.~.
X~.~.~.~
o.~.~Xo.
.~.~.o.~
~.o.~.~.
.oX~.~.o
~.~.~.~X
.~.~X~.o

Solving for 9x9 board
Solution found using 14 knights in 00:00:10.2331055:
.~.~.~.~.
~.o.~.o.~
.~Xo.oX~.
~.~.~.~.~
X~.~.~.~X
~.~.~.~.~
.~Xo.oX~.
~.o.~.o.~
.~.~.~.~.

Solving for 10x10 board
Solution found using 16 knights in 00:04:44.0573668:
~.~.~.~.~.
.~.~.~Xo.~
~Xo.~.oX~.
.oX~.~.~.~
~.~.~.~.~.
.~.~.~.~.~
~.~.~.~Xo.
.~Xo.~.oX~
~.oX~.~.~.
.~.~.~.~.~

Go

This was originally a translation of the Wren entry but was substantially improved by Pete Lomax using suggestions from the talk page and has been improved further since then, resulting in an overall execution time of about 22.4 seconds.

Timing is for an Intel Core i7-8565U machine running Ubuntu 20.04.

package main

import (
    "fmt"
    "math"
    "strings"
    "time"
)

var board [][]bool
var diag1, diag2 [][]int
var diag1Lookup, diag2Lookup []bool
var n, minCount int
var layout string

func isAttacked(piece string, row, col int) bool {
    if piece == "Q" {
        for i := 0; i < n; i++ {
            if board[i][col] || board[row][i] {
                return true
            }
        }
        if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] {
            return true
        }
    } else if piece == "B" {
        if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] {
            return true
        }
    } else { // piece == "K"
        if board[row][col] {
            return true
        }
        if row+2 < n && col-1 >= 0 && board[row+2][col-1] {
            return true
        }
        if row-2 >= 0 && col-1 >= 0 && board[row-2][col-1] {
            return true
        }
        if row+2 < n && col+1 < n && board[row+2][col+1] {
            return true
        }
        if row-2 >= 0 && col+1 < n && board[row-2][col+1] {
            return true
        }
        if row+1 < n && col+2 < n && board[row+1][col+2] {
            return true
        }
        if row-1 >= 0 && col+2 < n && board[row-1][col+2] {
            return true
        }
        if row+1 < n && col-2 >= 0 && board[row+1][col-2] {
            return true
        }
        if row-1 >= 0 && col-2 >= 0 && board[row-1][col-2] {
            return true
        }
    }
    return false
}

func abs(i int) int {
    if i < 0 {
        i = -i
    }
    return i
}

func attacks(piece string, row, col, trow, tcol int) bool {
    if piece == "Q" {
        return row == trow || col == tcol || abs(row-trow) == abs(col-tcol)
    } else if piece == "B" {
        return abs(row-trow) == abs(col-tcol)
    } else { // piece == "K"
        rd := abs(trow - row)
        cd := abs(tcol - col)
        return (rd == 1 && cd == 2) || (rd == 2 && cd == 1)
    }
}

func storeLayout(piece string) {
    var sb strings.Builder
    for _, row := range board {
        for _, cell := range row {
            if cell {
                sb.WriteString(piece + " ")
            } else {
                sb.WriteString(". ")
            }
        }
        sb.WriteString("\n")
    }
    layout = sb.String()
}

func placePiece(piece string, countSoFar, maxCount int) {
    if countSoFar >= minCount {
        return
    }
    allAttacked := true
    ti := 0
    tj := 0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if !isAttacked(piece, i, j) {
                allAttacked = false
                ti = i
                tj = j
                break
            }
        }
        if !allAttacked {
            break
        }
    }
    if allAttacked {
        minCount = countSoFar
        storeLayout(piece)
        return
    }
    if countSoFar <= maxCount {
        si := ti
        sj := tj
        if piece == "K" {
            si = si - 2
            sj = sj - 2
            if si < 0 {
                si = 0
            }
            if sj < 0 {
                sj = 0
            } 
        }
        for i := si; i < n; i++ {
            for j := sj; j < n; j++ {
                if !isAttacked(piece, i, j) {
                    if (i == ti && j == tj) || attacks(piece, i, j, ti, tj) {
                        board[i][j] = true
                        if piece != "K" {
                            diag1Lookup[diag1[i][j]] = true
                            diag2Lookup[diag2[i][j]] = true
                        }
                        placePiece(piece, countSoFar+1, maxCount)
                        board[i][j] = false
                        if piece != "K" {
                            diag1Lookup[diag1[i][j]] = false
                            diag2Lookup[diag2[i][j]] = false
                        }
                    }
                }
            }
        }
    }
}

func main() {
    start := time.Now()
    pieces := []string{"Q", "B", "K"}
    limits := map[string]int{"Q": 10, "B": 10, "K": 10}
    names := map[string]string{"Q": "Queens", "B": "Bishops", "K": "Knights"}
    for _, piece := range pieces {
        fmt.Println(names[piece])
        fmt.Println("=======\n")

        for n = 1; ; n++ {
            board = make([][]bool, n)
            for i := 0; i < n; i++ {
                board[i] = make([]bool, n)
            }
            if piece != "K" {
                diag1 = make([][]int, n)
                for i := 0; i < n; i++ {
                    diag1[i] = make([]int, n)
                    for j := 0; j < n; j++ {
                        diag1[i][j] = i + j
                    }
                }
                diag2 = make([][]int, n)
                for i := 0; i < n; i++ {
                    diag2[i] = make([]int, n)
                    for j := 0; j < n; j++ {
                        diag2[i][j] = i - j + n - 1
                    }
                }
                diag1Lookup = make([]bool, 2*n-1)
                diag2Lookup = make([]bool, 2*n-1)
            }
            minCount = math.MaxInt32
            layout = ""
            for maxCount := 1; maxCount <= n*n; maxCount++ {
                placePiece(piece, 0, maxCount)
                if minCount <= n*n {
                    break
                }
            }
            fmt.Printf("%2d x %-2d : %d\n", n, n, minCount)
            if n == limits[piece] {
                fmt.Printf("\n%s on a %d x %d board:\n", names[piece], n, n)
                fmt.Println("\n" + layout)
                break
            }
        }
    }
    elapsed := time.Now().Sub(start)
    fmt.Printf("Took %s\n", elapsed)
}
Output:
Queens
=======

 1 x 1  : 1
 2 x 2  : 1
 3 x 3  : 1
 4 x 4  : 3
 5 x 5  : 3
 6 x 6  : 4
 7 x 7  : 4
 8 x 8  : 5
 9 x 9  : 5
10 x 10 : 5

Queens on a 10 x 10 board:

. . Q . . . . . . . 
. . . . . . . . . . 
. . . . . . . . Q . 
. . . . . . . . . . 
. . . . Q . . . . . 
. . . . . . . . . . 
Q . . . . . . . . . 
. . . . . . . . . . 
. . . . . . Q . . . 
. . . . . . . . . . 

Bishops
=======

 1 x 1  : 1
 2 x 2  : 2
 3 x 3  : 3
 4 x 4  : 4
 5 x 5  : 5
 6 x 6  : 6
 7 x 7  : 7
 8 x 8  : 8
 9 x 9  : 9
10 x 10 : 10

Bishops on a 10 x 10 board:

. . . . . . . . . B 
. . . . . . . . . . 
. . . B . B . . . . 
. . . B . B . B . . 
B . . . . . . . . . 
. . . . . . . . . . 
. . . . . B . . . . 
. . . . . B . . . . 
. . . . . B . . . . 
. . . . . . . . . . 

Knights
=======

 1 x 1  : 1
 2 x 2  : 4
 3 x 3  : 4
 4 x 4  : 4
 5 x 5  : 5
 6 x 6  : 8
 7 x 7  : 13
 8 x 8  : 14
 9 x 9  : 14
10 x 10 : 16

Knights on a 10 x 10 board:

. . . . . . . . . . 
. . K K . . . . . . 
. . K K . . . K K . 
. . . . . . . K K . 
. . . . . . . . . . 
. . . . . . . . . . 
. K K . . . . . . . 
. K K . . . K K . . 
. . . . . . K K . . 
. . . . . . . . . . 

Took 22.383253365s

J

This is a crude attempt -- brute force search with some minor state space pruning. I am not patient enough to run this for boards larger than 7x7 for knights:

genboard=: {{
  safelen=:2*len=: {.y
  shape=: 2$len
  board=: shape$0
  safeshape=: ,~safelen
  c=:,coords=: safeshape#.shape#:i.shape
  qrow=. i:{.shape-1
  qcol=. qrow*safelen
  qdiag1=. qrow+qcol
  qdiag2=. qrow-qcol
  queen=: ~.qrow,qcol,qdiag1,qdiag2
  k1=. ,(1 _1*safelen)+/2 _2
  k2=. ,(2 _2*safelen)+/1 _1
  knight=: 0,k1,k2
  bishop=: ~.qdiag1,qdiag2
  row=. i.len
  first=: ~.,coords#"1~(row<:>.<:len%2) * >:/~ row
  EMPTY
}}

placebishops=: {{coords #&,~ 1 (<.-:len)} board}}

placequeens=: {{
  N=. 0
  while. N=. N+1 do.
    assert. N<:#c
    for_seq. first do.
      board=. coords e.queen+seq
      if. 0 e.,board do.
         if. 1<N do.
           seq=. board queen place1 N seq 
           if. #seq do.
             assert. N-:#seq
             assert. */c e.,queen+/seq
             seq return.
           end.
         end.
      else.
        seq return.
      end.
    end.
  end.
  EMPTY
}}

placeknights=:{{
  N=. 0
  while. N=. N+1 do.
    assert. N<:#c
    for_seq. c do.
      board=. coords e.knight+seq
      if. 0 e.,board do.
         if. 1<N do.
           seq=. board knight place1 N seq 
           if. #seq do.
             assert. N-:#seq
             assert. */c e.,knight+/seq
             seq return.
           end.
         end.
      else.
        seq return.
      end.
    end.
  end.
  EMPTY
}}
 
NB. x: board with currently attacked locations marked
NB. m: move targets
NB. n: best sequence length so far
NB. y: coords of placed pieces
place1=: {{
  for_seq. y,"1 0(#~ (>./y) < ])(,0=x)#c do.
    board=. x>.coords e.,m+/seq
    if. 0 e.,board do.          NB. further work needed?
       if.n>#seq do.
         seq=. board m place1 n seq
         if.#seq do.seq return.end.
       end.
    else. seq return.
    end.
  end.
  EMPTY
}}
 
task=: {{
  B=:Q=:K=:i.0
  for_order.1+i.y do.
    genboard order
    B=: 1j1#"1'.B'{~coords e.b=. placebishops ''
    Q=: 1j1#"1'.Q'{~coords e.q=. placequeens ''
    if. 8>order do.
      K=: 1j1#"1'.K'{~coords e.k=. placeknights ''
      echo (":B;Q;K),&.|:>(' B: ',":#b);(' Q: ',":#q);' K: ',":#k
    else.
      echo (":B;Q),&.|:>(' B: ',":#b);' Q: ',":#q
    end.
  end.
}}

Task output:

   task 10
+--+--+--+ B: 1
|B |Q |K | Q: 1
+--+--+--+ K: 1
+----+----+----+ B: 2
|. . |Q . |K K | Q: 1
|B B |. . |K K | K: 4
+----+----+----+
+------+------+------+ B: 3
|. . . |. . . |K K K | Q: 1
|B B B |. Q . |. K . | K: 4
|. . . |. . . |. . . |
+------+------+------+
+--------+--------+--------+ B: 4
|. . . . |Q . . . |. K K . | Q: 3
|. . . . |. . Q . |. K K . | K: 4
|B B B B |. . . . |. . . . |
|. . . . |. Q . . |. . . . |
+--------+--------+--------+
+----------+----------+----------+ B: 5
|. . . . . |Q . . . . |K . . . . | Q: 3
|. . . . . |. . . Q . |. . . . . | K: 5
|B B B B B |. . . . . |. . K K . |
|. . . . . |. . Q . . |. . K K . |
|. . . . . |. . . . . |. . . . . |
+----------+----------+----------+
+------------+------------+------------+ B: 6
|. . . . . . |Q . . . . . |K . . . . K | Q: 4
|. . . . . . |. . Q . . . |. . . . . . | K: 8
|. . . . . . |. . . . . Q |. . K K . . |
|B B B B B B |. . . . . . |. . K K . . |
|. . . . . . |. . . . . . |. . . . . . |
|. . . . . . |. Q . . . . |K . . . . K |
+------------+------------+------------+
+--------------+--------------+--------------+ B: 7
|. . . . . . . |. . . . . . . |K K K K . K . | Q: 4
|. . . . . . . |. Q . . . . . |. . . . . . . | K: 13
|. . . . . . . |. . . . Q . . |. . . . . K . |
|B B B B B B B |. . . . . . . |K . . . . K . |
|. . . . . . . |. . . . . . . |. . . . . . . |
|. . . . . . . |Q . . . . . . |K . K K . K . |
|. . . . . . . |. . . Q . . . |. . . . . . K |
+--------------+--------------+--------------+
+----------------+----------------+ B: 8
|. . . . . . . . |Q . . . . . . . | Q: 5
|. . . . . . . . |. . Q . . . . . |
|. . . . . . . . |. . . . Q . . . |
|. . . . . . . . |. Q . . . . . . |
|B B B B B B B B |. . . Q . . . . |
|. . . . . . . . |. . . . . . . . |
|. . . . . . . . |. . . . . . . . |
|. . . . . . . . |. . . . . . . . |
+----------------+----------------+
+------------------+------------------+ B: 9
|. . . . . . . . . |Q . . . . . . . . | Q: 5
|. . . . . . . . . |. . Q . . . . . . |
|. . . . . . . . . |. . . . . . Q . . |
|. . . . . . . . . |. . . . . . . . . |
|B B B B B B B B B |. . . . . . . . . |
|. . . . . . . . . |. Q . . . . . . . |
|. . . . . . . . . |. . . . . Q . . . |
|. . . . . . . . . |. . . . . . . . . |
|. . . . . . . . . |. . . . . . . . . |
+------------------+------------------+
+--------------------+--------------------+ B: 10
|. . . . . . . . . . |Q . . . . . . . . . | Q: 6
|. . . . . . . . . . |. . Q . . . . . . . |
|. . . . . . . . . . |. . . . . . . . Q . |
|. . . . . . . . . . |. . . . . . . . . . |
|. . . . . . . . . . |. . . . . . . . . . |
|B B B B B B B B B B |. . . Q . . . . . . |
|. . . . . . . . . . |. . . . . . . . . Q |
|. . . . . . . . . . |. . . . . . . . . . |
|. . . . . . . . . . |. . . . . Q . . . . |
|. . . . . . . . . . |. . . . . . . . . . |
+--------------------+--------------------+

Julia

Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support.

""" Rosetta code task N-queens_minimum_and_knights_and_bishops """

import Cbc
using JuMP
using LinearAlgebra

""" Make a printable string from a matrix of zeros and ones using a char ch for 1, a period for !=1. """
function smatrix(x, n, ch)
    s = ""
    for i in 1:n, j in 1:n
        s *= lpad(x[i, j] == 1 ? "$ch" : ".", 2) * (j == n ? "\n" : "")
    end
    return s
end

""" N-queens minimum, oeis.org/A075458 """
function queensminimum(N, char = "Q")
    if  N < 4
        a = zeros(Int, N, N)
        a[N ÷ 2 + 1, N ÷ 2 + 1] = 1
        return 1, smatrix(a, N, char)
    end
    model = Model(Cbc.Optimizer)
    @variable(model, x[1:N, 1:N], Bin)

    for i in 1:N
        @constraint(model, sum(x[i, :]) <= 1)
        @constraint(model, sum(x[:, i]) <= 1)
    end
    for i in -(N - 1):(N-1)
        @constraint(model, sum(diag(x, i)) <= 1)
        @constraint(model, sum(diag(reverse(x, dims = 1), i)) <= 1)
    end
    for i in 1:N, j in 1:N
        @constraint(model, sum(x[i, :]) + sum(x[:, j]) +  sum(diag(x, j - i)) +
           sum(diag(rotl90(x), N - j - i + 1)) >= 1)
    end

    set_silent(model)
    @objective(model, Min, sum(x))
    optimize!(model)

    solution = round.(Int, value.(x))
    minresult = sum(solution)
    return minresult, smatrix(solution, N, char)
end

""" N-bishops minimum, same as N """
function bishopsminimum(N, char = "B")
    N == 1 && return 1, "$char"
    N == 2 && return 2, "$char .\n$char .\n"

    model = Model(Cbc.Optimizer)
    @variable(model, x[1:N, 1:N], Bin)

    for i in 1:N, j in 1:N
        @constraint(model, sum(diag(x, j - i)) + sum(diag(rotl90(x), N - j - i + 1)) >= 1)
    end

    set_silent(model)
    @objective(model, Min, sum(x))
    optimize!(model)

    solution = round.(Int, value.(x))
    minresult = sum(solution)
    return minresult, smatrix(solution, N, char)
end

""" N-knights minimum, oeis.org/A342576 """
function knightsminimum(N, char = "N")
    N < 2 && return 1, "$char"

    knightdeltas = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]

    model = Model(Cbc.Optimizer)

    # to simplify the constraints, embed the board of size N inside a board of size n + 4
    @variable(model, x[1:N+4, 1:N+4], Bin)

    @constraint(model, x[:, 1:2] .== 0)
    @constraint(model, x[1:2, :] .== 0)
    @constraint(model, x[:, N+3:N+4] .== 0)
    @constraint(model, x[N+3:N+4, :] .== 0)

    for i in 3:N+2, j in 3:N+2
        @constraint(model, x[i, j] + sum(x[i + d[1], j + d[2]] for d in knightdeltas) >= 1)
        @constraint(model, x[i, j] => {sum(x[i + d[1], j + d[2]] for d in knightdeltas) == 0})
    end

    set_silent(model)
    @objective(model, Min, sum(x))
    optimize!(model)

    solution = round.(Int, value.(x))
    minresult = sum(solution)
    return minresult, smatrix(solution[3:N+2, 3:N+2], N, char)
end

const examples = fill("", 3)
println("   Squares    Queens   Bishops   Knights")
@time for N in 1:10
    print(lpad(N^2, 10))
    i, examples[1] = queensminimum(N)
    print(lpad(i, 10))
    i, examples[2] = bishopsminimum(N)
    print(lpad(i, 10))
    i, examples[3] = knightsminimum(N)
    println(lpad(i, 10))
end

println("\nExamples for N = 10:\n\nQueens:\n", examples[1], "\nBishops:\n", examples[2],
   "\nKnights:\n", examples[3])
Output:
   Squares    Queens   Bishops   Knights
         1         1         1         1
         4         1         2         4
         9         1         3         4
        16         3         4         4
        25         3         5         5
        36         4         6         8
        49         4         7        13
        64         5         8        14
        81         5         9        14
       100         5        10        16
 49.922920 seconds (30.87 M allocations: 1.656 GiB, 2.39% gc time, 65.49% compilation time)

Examples for N = 10:

Queens:
 . . . . . . . . . .
 . . Q . . . . . . .
 . . . . . . . . . .
 . . . . . . . . Q .
 . . . . . . . . . .
 . . . . Q . . . . .
 . . . . . . . . . .
 Q . . . . . . . . .
 . . . . . . . . . .
 . . . . . . Q . . .

Bishops:
 . . . . . . . . . .
 . . . . . B . . . .
 . . . . . B . . . .
 . B . . . . . . . .
 . B . . . . B . . .
 . . . . . . B . . .
 . . B . . . B . . .
 . . . . . . B . . .
 . B . . . . . . . .
 . . . . . . . . . .

Knights:
 . . . . . . . . . .
 . . N N . . . . . .
 . . N N . . . N N .
 . . . . . . . N N .
 . . . . . . . . . .
 . . . . . . . . . .
 . N N . . . . . . .
 . N N . . . N N . .
 . . . . . . N N . .
 . . . . . . . . . .

Nim

Translation of: Go
import std/[monotimes, sequtils, strformat]

type

  Piece {.pure.} = enum Queen, Bishop, Knight
  Solver = object
    n: Natural
    board: seq[seq[bool]]
    diag1, diag2: seq[seq[int]]
    diag1Lookup, diag2Lookup: seq[bool]
    minCount: int
    layout: string

func isAttacked(s: Solver; piece: Piece; row, col: Natural): bool =
  case piece
  of Queen:
    for i in 0..<s.n:
      if s.board[i][col] or s.board[row][i]:
        return true
    result = s.diag1Lookup[s.diag1[row][col]] or s.diag2Lookup[s.diag2[row][col]]
  of Bishop:
    result = s.diag1Lookup[s.diag1[row][col]] or s.diag2Lookup[s.diag2[row][col]]:
  of Knight:
    result = s.board[row][col] or
             row + 2 < s.n and col - 1 >= 0  and s.board[row + 2][col - 1] or
             row - 2 >= 0  and col - 1 >= 0  and s.board[row - 2][col - 1] or
             row + 2 < s.n and col + 1 < s.n and s.board[row + 2][col + 1] or
             row - 2 >= 0  and col + 1 < s.n and s.board[row - 2][col + 1] or
             row + 1 < s.n and col + 2 < s.n and s.board[row + 1][col + 2] or
             row - 1 >= 0  and col + 2 < s.n and s.board[row - 1][col + 2] or
             row + 1 < s.n and col - 2 >= 0  and s.board[row + 1][col - 2] or
             row - 1 >= 0  and col - 2 >= 0  and s.board[row - 1][col - 2]

func attacks(piece: Piece; row, col, trow, tcol: int): bool =
  case piece
  of Queen:
    result = row == trow or col == tcol or abs(row - trow) == abs(col - tcol)
  of Bishop:
    result = abs(row - trow) == abs(col - tcol)
  of Knight:
    let rd = abs(trow - row)
    let cd = abs(tcol - col)
    result = (rd == 1 and cd == 2) or (rd == 2 and cd == 1)

func storeLayout(s: var Solver; piece: Piece) =
  for row in s.board:
    for cell in row:
      s.layout.add if cell: ($piece)[0] & ' ' else: ". "
    s.layout.add '\n'

func placePiece(s: var Solver; piece: Piece; countSoFar, maxCount: int) =
  if countSoFar >= s.minCount: return

  var allAttacked = true
  var ti, tj = 0
  block CheckAttacked:
    for i in 0..<s.n:
      for j in 0..<s.n:
        if not s.isAttacked(piece, i, j):
          allAttacked = false
          ti = i
          tj = j
          break CheckAttacked

  if allAttacked:
    s.minCount = countSoFar
    s.storeLayout(piece)
    return

  if countSoFar <= maxCount:
    var si = ti
    var sj = tj
    if piece == Knight:
      dec si, 2
      dec sj, 2
      if si < 0: si = 0
      if sj < 0: sj = 0

    for i in si..<s.n:
      for j in sj..<s.n:
        if not s.isAttacked(piece, i, j):
          if (i == ti and j == tj) or attacks(piece, i, j, ti, tj):
            s.board[i][j] = true
            if piece != Knight:
              s.diag1Lookup[s.diag1[i][j]] = true
              s.diag2Lookup[s.diag2[i][j]] = true
            s.placePiece(piece, countSoFar + 1, maxCount)
            s.board[i][j] = false
            if piece != Knight:
              s.diag1Lookup[s.diag1[i][j]] = false
              s.diag2Lookup[s.diag2[i][j]] = false

func initSolver(n: Positive; piece: Piece): Solver =
  result.n = n
  result.board = newSeqWith(n, newSeq[bool](n))
  if piece != Knight:
    result.diag1 = newSeqWith(n, newSeq[int](n))
    result.diag2 = newSeqWith(n, newSeq[int](n))
    for i in 0..<n:
      for j in 0..<n:
        result.diag1[i][j] = i + j
        result.diag2[i][j] = i - j + n - 1
    result.diag1Lookup = newSeq[bool](2 * n - 1)
    result.diag2Lookup = newSeq[bool](2 * n - 1)
  result.minCount = int32.high

proc main() =
  let start = getMonoTime()
  const Limits = [Queen: 10, Bishop: 10, Knight: 10]
  for piece in Piece.low..Piece.high:
    echo $piece & 's'
    echo "=======\n"
    var n = 0
    while true:
      inc n
      var solver = initSolver(n , piece)
      for maxCount in 1..(n * n):
        solver.placePiece(piece, 0, maxCount)
        if solver.minCount <= n * n:
          break
      echo &"{n:>2} × {n:<2} : {solver.minCount}"
      if n == Limits[piece]:
        echo &"\n{$piece}s on a {n} × {n} board:"
        echo '\n' & solver.layout
        break
  let elapsed = getMonoTime() - start
  echo "Took: ", elapsed

main()
Output:
Queens
=======

 1 × 1  : 1
 2 × 2  : 1
 3 × 3  : 1
 4 × 4  : 3
 5 × 5  : 3
 6 × 6  : 4
 7 × 7  : 4
 8 × 8  : 5
 9 × 9  : 5
10 × 10 : 5

Queens on a 10 × 10 board:

. . Q . . . . . . . 
. . . . . . . . . . 
. . . . . . . . Q . 
. . . . . . . . . . 
. . . . Q . . . . . 
. . . . . . . . . . 
Q . . . . . . . . . 
. . . . . . . . . . 
. . . . . . Q . . . 
. . . . . . . . . . 

Bishops
=======

 1 × 1  : 1
 2 × 2  : 2
 3 × 3  : 3
 4 × 4  : 4
 5 × 5  : 5
 6 × 6  : 6
 7 × 7  : 7
 8 × 8  : 8
 9 × 9  : 9
10 × 10 : 10

Bishops on a 10 × 10 board:

. . . . . . . . . B 
. . . . . . . . . . 
. . . B . B . . . . 
. . . B . B . B . . 
B . . . . . . . . . 
. . . . . . . . . . 
. . . . . B . . . . 
. . . . . B . . . . 
. . . . . B . . . . 
. . . . . . . . . . 

Knights
=======

 1 × 1  : 1
 2 × 2  : 4
 3 × 3  : 4
 4 × 4  : 4
 5 × 5  : 5
 6 × 6  : 8
 7 × 7  : 13
 8 × 8  : 14
 9 × 9  : 14
10 × 10 : 16

Knights on a 10 × 10 board:

. . . . . . . . . . 
. . K K . . . . . . 
. . K K . . . K K . 
. . . . . . . K K . 
. . . . . . . . . . 
. . . . . . . . . . 
. K K . . . . . . . 
. K K . . . K K . . 
. . . . . . K K . . 
. . . . . . . . . . 

Took: (seconds: 19, nanosecond: 942476699)

Pascal

Free Pascal

The first Q,B in the first row is only placed lmt..mid because of symmetry reasons.
14 Queens takes 2 min @home ~2.5x faster than TIO.RUN

program TestMinimalQueen;
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}

uses
  sysutils;
type
  tDeltaKoor = packed record
                        dRow,
                        dCol : Int8;
                      end;
const
  cKnightAttacks : array[0..7] of tDeltaKoor =
                   ((dRow:-2;dCol:-1),(dRow:-2;dCol:+1),
                    (dRow:-1;dCol:-2),(dRow:-1;dCol:+2),
                    (dRow:+1;dCol:-2),(dRow:+1;dCol:+2),
                    (dRow:+2;dCol:-1),(dRow:+2;dCol:+1));

  KoorCOUNT = 16;

type
  tLimit = 0..KoorCOUNT-1;

  tPlayGround = array[tLimit,tLimit] of byte;
  tCheckPG = array[0..2*KoorCOUNT] of tplayGround;
  tpPlayGround = ^tPlayGround;

var
{$ALIGN 32}
  CPG :tCheckPG;
  Qsol,BSol,KSol :tPlayGround;
  pgIdx,minIdx : nativeInt;

procedure pG_Out(pSol:tpPlayGround;ConvChar : string;lmt: NativeInt);
var
  row,col: NativeInt;
begin
  iF length(ConvChar)<>3 then
    EXIT;
  for row := lmt downto 0 do
  Begin
    for col := 0 to lmt do
      write(ConvChar[1+pSol^[row,col]],' ');
    writeln;
  end;
  writeln;
end;

procedure LeftAscDia(row,col,lmt: NativeInt);
var
  pPG :tpPlayGround;
  j: NativeInt;
begin
  pPG := @CPG[pgIdx];
  if row >= col then
  begin
    j := row-col;
    col := lmt-j;
    row := lmt;
    repeat
      pPG^[row,col] := 1;
      dec(col);
      dec(row);
    until col < 0;
  end
  else
  begin
    j := col-row;
    row := lmt-j;
    col := lmt;
    repeat
      pPG^[row,col] := 1;
      dec(row);
      dec(col);
   until row < 0;
  end;
end;

procedure RightAscDia(row,col,lmt: NativeInt);
var
  pPG :tpPlayGround;
  j: NativeInt;
begin
  pPG := @CPG[pgIdx];
  j := row+col;
  if j <= lmt then
  begin
    col := j;
    row := 0;
    repeat
      pPG^[row,col] := 1;
      dec(col);
      inc(row);
    until col < 0;
  end
  else
  begin
    col := lmt;
    row := j-lmt;
    repeat
      pPG^[row,col] := 1;
      inc(row);
      dec(col);
   until row > lmt;
  end;
end;

function check(lmt:nativeInt):boolean;
//check, if all fields are attacked
var
  pPG :tpPlayGround;
  pRow : pByte;
  row,col: NativeInt;
Begin
  pPG := @CPG[pgIdx];
  For row := lmt downto 0 do
  begin
    pRow := @pPG^[row,0];
    For col := lmt downto 0 do
      if pRow[col] = 0 then
        EXIT(false);
  end;
  exit(true);
end;

procedure SetQueen(row,lmt: NativeInt);
var
  pPG :tpPlayGround;
  i,col,t: NativeInt;
begin
  t := pgIdx+1;
  if t = minIDX then
    EXIT;
  pgIdx:= t;
  //use state before
//  CPG[pgIdx]:=CPG[pgIdx-1];
  move(CPG[t-1],CPG[t],SizeOf(tPlayGround));
  col := lmt;
  //first row only check one half -> symmetry
  if row = 0 then
    col := col shr 1;

  //check every column
  For col := col downto 0 do
  begin
    pPG := @CPG[pgIdx];
    if pPG^[row,col] <> 0 then
      continue;
    //set diagonals
    RightAscDia(row,col,lmt);
    LeftAscDia(row,col,lmt);
    //set row and column as attacked
    For i := 0 to lmt do
    Begin
      pPG^[row,i] := 1;
      pPG^[i,col] := 1;
    end;
    //now set position of queen
    pPG^[row,col] := 2;

    if check(lmt) then
    begin
      if minIdx> pgIdx then
      begin
        minIdx := pgIdx;
        Qsol := pPG^;
      end;
    end
    else
      if row > lmt then
        BREAK
      else
        //check next rows
        For t := row+1 to lmt do
          SetQueen(t,lmt);
    //copy last state
    t := pgIdx;
    move(CPG[t-1],CPG[t],SizeOf(tPlayGround));
//    CPG[pgIdx]:=CPG[pgIdx-1];
  end;
  dec(pgIdx);
end;

procedure SetBishop(row,lmt: NativeInt);
var
  pPG :tpPlayGround;
  col,t: NativeInt;
begin
  if pgIdx = minIDX then
    EXIT;
  inc(pgIdx);
  move(CPG[pgIdx-1],CPG[pgIdx],SizeOf(tPlayGround));
  col := lmt;
  if row = 0 then
    col := col shr 1;
  For col := col downto 0 do
  begin
    pPG := @CPG[pgIdx];
    if pPG^[row,col] <> 0 then
      continue;

    RightAscDia(row,col,lmt);
    LeftAscDia(row,col,lmt);

    //set position of bishop
    pPG^[row,col] := 2;

    if check(lmt) then
    begin
      if minIdx> pgIdx then
      begin
        minIdx := pgIdx;
        Bsol := pPG^;
      end;
    end
    else
      if row > lmt then
        BREAK
      else
      begin
        //check same row
        SetBishop(row,lmt);
        //check next row
        t := row+1;
        if (t <= lmt) then
          SetBishop(t,lmt);
      end;
    move(CPG[pgIdx-1],CPG[pgIdx],SizeOf(tPlayGround));
  end;
  dec(pgIdx);
end;

var
  lmt,max : NativeInt;

BEGIN
  max := 10;
  write(' nxn  n=:');
  For lmt := 1 to max do
    write(lmt:3);
  writeln;

  write(' Queens :');
  For lmt := 0 to max-1 do
  begin
    pgIdx := 0;
    minIdx := lmt;
    setQueen(0,lmt);
    write(minIDX:3);
  end;
  writeln;

  write(' Bishop :');
  For lmt := 0 to max-1 do
  begin
    pgIdx := 0;
    minIdx := 2*lmt+1;
    setBishop(0,lmt);
    write(minIDX:3);
  end;
  writeln;

  pG_Out(@Qsol,'_.Q',max-1);
  writeln;

  pG_Out(@Bsol,'_.B',max-1);
END.
@TIO.RUN:
 nxn  n=:  1  2  3  4  5  6  7  8  9 10
 Queens :  1  1  2  3  3  4  4  5  5  5
 Bishop :  1  2  3  4  5  6  7  8  9 10
. . . . . . . . . .
. . . . . . . Q . .
. . . . . . . . . .
. Q . . . . . . . .
. . . . . . . . . .
. . . . . Q . . . .
. . . . . . . . . .
. . . . . . . . . Q
. . . . . . . . . .
. . . Q . . . . . .


. . . . . . . . . .
. . . . B . . . . .
. . . . . . B . . .
. . . . B . . . . .
. . . . . . B . . .
. B . . . . . . . .
. . . B . B . . . .
. . . . . B . . . .
. . . . . . . . B .
. . . . B . . . . .

Real time: 25.935 s CPU share: 99.27 % //@home AMD 5600G real	0m10,784s

Perl

Shows how the latest release of Perl can now use booleans.

Translation of: Raku
use v5.36;
use builtin 'true', 'false';
no warnings 'experimental::for_list', 'experimental::builtin';

my(@B, @D1, @D2, @D1x, @D2x, $N, $Min, $Layout);

sub X ($a,$b)       { my @c; for my $aa (0..$a-1) { for my $bb (0..$b-1) { push @c, $aa, $bb } } @c }
sub Xr($a,$b,$c,$d) { my @c; for my $ab ($a..$b)  { for my $cd ($c..$d)  { push @c, $ab, $cd } } @c }

sub is_attacked($piece, $r, $c) {
    if ($piece eq 'Q') {
        for (0..$N-1) { return true if $B[$_][$c] or $B[$r][$_] }
        return true if $D1x[ $D1[$r][$c] ] or
                       $D2x[ $D2[$r][$c] ]
    } elsif ($piece eq 'B') {
        return true if $D1x[ $D1[$r][$c] ] or $D2x[ $D2[$r][$c] ]
    } else { # 'K'
        return true if (
            $B[$r][$c] or
            $r+2 < $N and $c-1 >= 0 and $B[$r+2][$c-1] or
            $r-2 >= 0 and $c-1 >= 0 and $B[$r-2][$c-1] or
            $r+2 < $N and $c+1 < $N and $B[$r+2][$c+1] or
            $r-2 >= 0 and $c+1 < $N and $B[$r-2][$c+1] or
            $r+1 < $N and $c+2 < $N and $B[$r+1][$c+2] or
            $r-1 >= 0 and $c+2 < $N and $B[$r-1][$c+2] or
            $r+1 < $N and $c-2 >= 0 and $B[$r+1][$c-2] or
            $r-1 >= 0 and $c-2 >= 0 and $B[$r-1][$c-2]
        )
   }
   false
}

sub attacks($piece, $r, $c, $tr, $tc) {
    if    ($piece eq 'Q') { $r==$tr or $c==$tc or abs($r - $tr)==abs($c - $tc) }
    elsif ($piece eq 'B') { abs($r - $tr) == abs($c - $tc) }
    else                  {
        my ($rd, $cd) = (abs($tr - $r), abs($tc - $c));
        ($rd == 1 and $cd == 2) or ($rd == 2 and $cd == 1)
    }
}

sub store_layout($piece) {
    $Layout = '';
    for (@B) {
        map { $Layout .= $_ ?  $piece.' ' : '. ' } @$_;
        $Layout .=  "\n";
    }
}

sub place_piece($piece, $so_far, $max) {
    return if $so_far >= $Min;
    my ($all_attacked,$ti,$tj) = (true,0,0);
    for my($i,$j) (X $N, $N) {
        unless (is_attacked($piece, $i, $j)) {
            ($all_attacked,$ti,$tj) = (false,$i,$j) and last
        }
        last unless $all_attacked
    }
    if ($all_attacked) {
        $Min = $so_far;
        store_layout($piece);
    } elsif ($so_far <= $max) {
        my($si,$sj) = ($ti,$tj);
        if ($piece eq 'K') {
            $si -= 2; $si = 0 if $si < 0;
            $sj -= 2; $sj = 0 if $sj < 0;
        }
        for my ($i,$j) (Xr $si, $N-1, $sj, $N-1) {
            unless (is_attacked($piece, $i, $j)) {
                if (($i == $ti and $j == $tj) or attacks($piece, $i, $j, $ti, $tj)) {
                    $B[$i][$j] = true;
                    unless ($piece eq 'K') {
                        ($D1x[ $D1[$i][$j] ], $D2x[ $D2[$i][$j] ]) = (true,true);
                    };
                    place_piece($piece, $so_far+1, $max);
                    $B[$i][$j] = false;
                    unless ($piece eq 'K') {
                        ($D1x[ $D1[$i][$j] ], $D2x[ $D2[$i][$j] ]) = (false,false);
                    }
                }
            }
         }
     }
}

my @Pieces = <Q B K>;
my %Limits = ( 'Q' =>   10,     'B' =>    10,     'K' =>    10   );
my %Names  = ( 'Q' => 'Queens', 'B' => 'Bishops', 'K' =>'Knights');

for my $piece (@Pieces) {
    say $Names{$piece} . "\n=======\n";
    for ($N = 1 ; ; $N++) {
        @B = map { [ (false) x $N ] } 1..$N;
        unless ($piece eq 'K') {
            @D2 = reverse @D1 = map { [$_ .. $N+$_-1] } 0..$N-1;
            @D2x = @D1x = (false) x ((2*$N)-1);
        }
        $Min = 2**31 - 1;
        my $nSQ   = $N**2;
        for my $max (1..$nSQ) {
            place_piece($piece, 0, $max);
            last if $Min <= $nSQ
        }
        printf("%2d x %-2d : %d\n", $N, $N, $Min);
        if ($N == $Limits{$piece}) {
            printf "\n%s on a %d x %d board:\n", $Names{$piece}, $N, $N;
            say $Layout and last
        }
    }
}
Output:
Queens
=======

 1 x 1  : 1
 2 x 2  : 1
 3 x 3  : 1
 4 x 4  : 3
 5 x 5  : 3
 6 x 6  : 4
 7 x 7  : 4
 8 x 8  : 5
 9 x 9  : 5
10 x 10 : 5

Queens on a 10 x 10 board:
. . Q . . . . . . .
. . . . . . . . . .
. . . . . . . . Q .
. . . . . . . . . .
. . . . Q . . . . .
. . . . . . . . . .
Q . . . . . . . . .
. . . . . . . . . .
. . . . . . Q . . .
. . . . . . . . . .

Bishops
=======

 1 x 1  : 1
 2 x 2  : 2
 3 x 3  : 3
 4 x 4  : 4
 5 x 5  : 5
 6 x 6  : 6
 7 x 7  : 7
 8 x 8  : 8
 9 x 9  : 9
10 x 10 : 10

Bishops on a 10 x 10 board:
. . . . . . . . . B
. . . . . . . . . .
. . . B . B . . . .
. . . B . B . B . .
B . . . . . . . . .
. . . . . . . . . .
. . . . . B . . . .
. . . . . B . . . .
. . . . . B . . . .
. . . . . . . . . .

Knights
=======

 1 x 1  : 1
 2 x 2  : 4
 3 x 3  : 4
 4 x 4  : 4
 5 x 5  : 5
 6 x 6  : 8
 7 x 7  : 13
 8 x 8  : 14
 9 x 9  : 14
10 x 10 : 16

Knights on a 10 x 10 board:
. . . . . . . . . .
. . K K . . . . . .
. . K K . . . K K .
. . . . . . . K K .
. . . . . . . . . .
. . . . . . . . . .
. K K . . . . . . .
. K K . . . K K . .
. . . . . . K K . .
. . . . . . . . . .

Phix

Library: Phix/pGUI
Library: Phix/online

You can run this online here, with cheat mode on so it should all be done in 22s (8.3 on the desktop). Cheat mode drops the final tricky 10N search from 8,163,658 positions to just 183,937. Without cheat mode it takes 1 min 20s to completely finish on the desktop (would be ~7mins in a browser), but it always remains fully interactive throughout.

--
-- demo\rosetta\minQBN.exw
-- =======================
--
with javascript_semantics
atom t0 = time()
include pGUI.e
constant title = "Minimum QBN",
         help_text = """
Finds the minimum number of Queens, Bishops, or Knights that can be placed on an NxN board 
such that no piece attacks another but every unoccupied square is attacked.

The legend on the right shows the current search status: a red number means that is still
being or yet to be tried, and a green number means it has found a solution.

Click on the legend, or press Q/B/N and 1..9/T and/or +/-, to show the answer or maniaical
workings of a particular sub-task. Use space to toggle the timer on and off.

The window title shows additional information for the selected item.
"""
constant maxq = 10, -- 1.0s (13 is 3minutes 58s, with maxn=1)
         maxb = 10, -- 1s (100 is 10s, with maxq=1 and maxn=1)
         maxn = 10, -- 1mins 10s (9: 11.8s, 8: 8.1s, with maxq=1)
         maxqbn = max({maxq,maxb,maxn})

bool cheat = true   -- eg find 16N on a 10x10 w/o disproving 15N first.
                    -- the total time drops to 8.3s (21.9s under p2js).

sequence board

constant bm = {{-1,-1},{-1,+1},
               {+1,-1},{+1,+1}},
         rm = {{-1,0},{0,-1},
               {+1,0},{0,+1}},
         qm = rm&bm,
         nm = {{-1,-2},{-2,-1},{-2,+1},{-1,+2},
               {+1,-2},{+2,-1},{+2,+1},{+1,+2}}

function get_mm(integer piece)
    switch piece do
        case 'Q': return qm
        case 'B': return bm
        case 'N': return nm
    end switch
    crash("uh?")
end function

function mm_baby(sequence mm, integer piece, row, col, n)
    sequence res = {}
    for i=1 to length(mm) do
        integer {dx,dy} = mm[i],
                mx = row,
                my = col
        while true do
            mx += dx
            my += dy
            if mx<1 or mx>n 
            or my<1 or my>n then
                exit
            end if
            res &= {{mx,my}}
            if piece='N' then exit end if
        end while
    end for
    return res
end function

function get_moves(integer piece, n, row, col)
    -- either occupy or attack [row][col]
    -- we only have to collect right and down
    sequence res = {{row,col}}, -- (occupy)
             mm = get_mm(piece)
    mm = iff(piece='Q'?extract(mm,{3,4,7,8})
                      :mm[length(mm)/2+1..$])
    mm = mm_baby(mm,piece,row,col,n)
    for i=1 to length(mm) do
        integer {mx,my} = mm[i]
        if board[mx,my]='0' then
            res &= {{mx,my}}
        end if
    end for
    integer m = ceil(n/2)
    if piece='B' then
        -- As pointed out on the talk page, *every*
        -- valid bishop solution can be transformed
        -- into all in column m so search only that
        for i=1 to length(res) do
            if res[i][2]=m then
                res = res[i..i]
                exit
            end if
        end for
        assert(length(res)=1)
    elsif row=1 and col=1 and n>1 then
        if piece='Q' then
            -- first queen on first half of top row
            -- or first half of diagonal (not cols)
            assert(length(res)=3*n-2)
            res = res[1..m]&res[2*n..2*n+m-2]
        elsif piece='N' and n>2 then
            -- first knight, was occupy+2, but by
            -- symmetry we only need it to be 1+1
            assert(length(res)=3)
            res = res[1..2]
        end if
    end if
    -- this cheeky little fella cuts more than half off the 
    -- last phase of 10N... (a circumstantial optimisation)
    res = reverse(res)
    return res
end function

procedure move(sequence rc, integer piece, n)
    integer {row,col} = rc
    board[row][col] = piece
    sequence mm = mm_baby(get_mm(piece),piece,row,col,n)
    for i=1 to length(mm) do
        integer {mx,my} = mm[i]
        board[mx][my] += 1
    end for
end procedure

Ihandle dlg, canvas, timer
cdCanvas cddbuffer, cdcanvas

constant SQBN = " QBN",  -- (or " RBN")
         QBNU = utf8_to_utf32("♕♗♘")

integer bn = 8, -- chosen board is nxn (1..10)
        cp = 1  -- piece (1,2,3 for QBN)

sequence state

-- eg go straight for 16N on 10x10, avoid disproving 15N (from OEIS)
constant cheats = {{1,1,1,3,3,4,4,5,5,5,5,7,7,8,9,9,9,10,11,11,11,12,13,13,13},
                   {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22},
                   {1,4,4,4,5,8,13,14,14,16,22,24,29,33}}
-- some more timings with cheat mode ON:
-- 11Q: 1s, 12Q: 1.2s, 13Q: 1 min 7s, 14Q: 3 min 35s
-- 11N: 1 min 42s, 12N: gave up

procedure reset()
    state = {repeat(0,maxq),
             repeat(0,maxb),
             repeat(0,maxn)}
    -- (in case the maxq/b/n settings altered:)
    if bn>length(state[cp]) then bn = 1 end if
    for p=1 to 3 do
        integer piece = SQBN[p+1]
        for n=1 to length(state[p]) do
            atom scolour = CD_RED
--          integer m = 1
            integer m = iff(cheat?cheats[p][n]:1)
            board = repeat(repeat('0',n),n)
            sequence moves = get_moves(piece,n,1,1)
            string undo = join(board,'\n')
            state[p][n] = {scolour,m,{moves},{undo},undo,0}
        end for
    end for
    IupSetInt(timer,"RUN",true)
end procedure

procedure iterative_solve()
    -- find something not yet done
    integer n = 0, p
    for ndx=1 to maxqbn do
        for pdx=1 to 3 do
            if ndx<=length(state[pdx])
            and state[pdx][ndx][1]!=CD_DARK_GREEN then
                p = pdx
                n = ndx
                exit
            end if
        end for
        if n!=0 then exit end if
    end for
    if n=0 then
        ?{"solved",(elapsed(time()-t0))}
        IupSetInt(timer,"RUN",false)
    else
        -- but work on currently selected first, if needed
        if state[cp][bn][1]!=CD_DARK_GREEN then
            p = cp
            n = bn
        end if
        atom t1 = time()+0.04, scolour
        integer piece = SQBN[p+1], m, count
        sequence stack, undo, answer
        {scolour,m,stack,undo,answer,count} = state[p][n]
        state[p][n] = 0
        if n>1 and state[p][n-1][1]=CD_DARK_GREEN and m<state[p][n-1][2] then
            -- if we needed (eg) 7 bishops to solve a 7x7, that means 
            -- we couldn't solve it with 6, so we are not going to be
            -- able to solve an 8x8 with 6 (or less) now are we!
            m = state[p][n-1][2]
        else
            while length(stack) do
                sequence rc = stack[$][1]
                stack[$] = stack[$][2..$]
                board = split(undo[$],'\n')
                move(rc,piece,n)
                count += 1
                bool solved = true
                for row=1 to n do
                    for col=1 to n do
                        if board[row][col]='0' then
                            if length(stack)<m then
                                stack &= {get_moves(piece,n,row,col)}
                                undo &= {join(board,'\n')}
                            end if
                            solved = false
                            exit
                        end if
                    end for
                    if not solved then exit end if
                end for
                if solved then
                    answer = join(board,'\n')
                    scolour = CD_DARK_GREEN
                    stack = {}
                    undo = {}
                end if
                while length(stack) and stack[$]={} do
                    stack = stack[1..-2]
                    undo = undo[1..-2]
                    if length(undo)=0 then exit end if
                end while
                if solved or time()>t1 then
                    state[p][n] = {scolour,m,stack,undo,answer,count}
                    return
                end if
            end while
            m += 1
        end if
        board = repeat(repeat('0',n),n)
        stack = {get_moves(piece,n,1,1)}
        undo = {join(board,'\n')}
        state[p][n] = {scolour,m,stack,undo,answer,count}
    end if
end procedure

atom dx, dy -- (saved for button_cb)

function redraw_cb(Ihandle /*canvas*/)
    integer {w, h} = IupGetIntInt(canvas, "DRAWSIZE")
    dx = w/40                 -- legend fifth
    dy = h/(maxqbn+1)         -- legend delta
    atom ly = h-dy/2,         -- legend top
         cx = w/2,            -- board centre
         cy = h/2,
         bs = min(w*.7,h*.9), -- board size
         ss = bs/bn           -- square size
         
    cdCanvasActivate(cddbuffer)
    cdCanvasClear(cddbuffer)
    atom fontsize = min(ceil(dy/6),ceil(dx/2))
    cdCanvasFont(cddbuffer, "Helvetica", CD_PLAIN, fontsize)
    for i=0 to maxqbn do
        atom lx = dx*36
        for j=0 to 3 do
            if j=0 or i<=length(state[j]) then
                string txt = iff(i=0?SQBN[j+1..j+1]:
                             sprintf("%d",iff(j=0?i:state[j][i][2])))
                atom colour = iff(i==0 or j==0?CD_BLACK:state[j][i][1])
                cdCanvasSetForeground(cddbuffer, colour)
                cdCanvasText(cddbuffer,lx,ly,txt)
            end if
            lx += dx
        end for
        ly -= dy
    end for
    atom x = cx-bs/2,
         y = cy+bs/2
    cdCanvasSetForeground(cddbuffer, CD_DARK_GREY)
    for i=1 to bn do
        for j=1+even(i) to bn by 2 do
            atom sx = x+j*ss,
                 sy = y-i*ss
            cdCanvasBox(cddbuffer,sx-ss,sx,sy+ss,sy)
        end for
    end for
    cdCanvasRect(cddbuffer,x,x+bs,y,y-bs)
    string piece_text = utf32_to_utf8({QBNU[cp]})
    integer piece = SQBN[cp+1]
    sequence mm = get_mm(piece),
             st = state[cp][bn]
    bool solved = st[1]=CD_DARK_GREEN
    -- show the solution/mt or undo[$] aka maniaical workings
    board = split(iff(solved or st[4]={}?st[5]:st[4][$]),'\n')
    for row=1 to bn do
        for col=1 to bn do
            if board[row][col]=piece then
                atom sx = x+col*ss-ss/2,
                     sy = y-row*ss+ss/2
                cdCanvasSetForeground(cddbuffer, CD_BLACK)
                cdCanvasFont(cddbuffer, "Helvetica", CD_PLAIN, fontsize*5)
                cdCanvasText(cddbuffer,sx,sy+iff(platform()=JS?0:5),piece_text)
                -- and mark all attacked squares
                cdCanvasFont(cddbuffer, "Helvetica", CD_PLAIN, fontsize*2)
                cdCanvasSetForeground(cddbuffer, CD_AMBER)
                sequence mnm = mm_baby(mm,piece,col,row,bn)
                for i=1 to length(mnm) do
                    integer {mx,my} = mnm[i]
                    string ac = board[my,mx]&""
                    cdCanvasText(cddbuffer,sx+ss*(mx-col),sy-ss*(my-row),ac)
                end for
            end if
        end for
    end for
    cdCanvasFlush(cddbuffer)
    integer m = st[2], count = st[6]
    string pdesc = {"Queens", "Bishops", "Knights"}[cp][1..-1-(m=1)],
          status = iff(solved?"solved in":"working:"),
         attempt = iff(count=1?"attempt":"attempts")
    IupSetStrAttribute(dlg,"TITLE","%s - %d %s on %dx%d %s %,d %s",{title,m,pdesc,bn,bn,status,count,attempt})
    return IUP_DEFAULT
end function

function map_cb(Ihandle canvas)
    cdcanvas = cdCreateCanvas(CD_IUP, canvas)
    cddbuffer = cdCreateCanvas(CD_DBUFFER, cdcanvas)
    cdCanvasSetBackground(cddbuffer, CD_PARCHMENT)
    cdCanvasSetTextAlignment(cddbuffer,CD_CENTER)
    return IUP_DEFAULT
end function

function help()
    IupMessage(title,help_text)
    return IUP_IGNORE -- (don't open browser help!)
end function

function key_cb(Ihandle ih, atom c)
    if c=K_ESC then
        IupSetInt(timer,"RUN",false)
        return IUP_CLOSE
    end if
    if c=K_F5 then return IUP_DEFAULT end if -- (let browser reload work)
    if c=K_F1 then return help() end if
    integer k = find(upper(c),SQBN&"123456789T+-!")
    if k then
        if k=1 then IupSetInt(timer,"RUN",not IupGetInt(timer,"RUN"))
        elsif k<=4 then     cp = k-1
        elsif k<=14 then    bn = k-4
        elsif c='+' then    bn = min(bn+1,maxqbn)
        elsif c='-' then    bn = max(bn-1,1)
        end if
        bn = min(bn,length(state[cp]))
        IupUpdate(ih)
    end if
    return IUP_IGNORE
end function

function button_cb(Ihandle ih, integer button, pressed, x, y, atom /*pStatus*/)
    if button=IUP_BUTTON1 and pressed then      -- (left button pressed)
        integer p = floor((x+dx/2)/dx)-36,
                n = floor(y/dy)
        if p>=1 and p<=3 
        and n>=1 and n<=length(state[p]) then
            {cp,bn} = {p,n}
            IupUpdate(ih)
        end if
    end if
    return IUP_CONTINUE
end function

function timer_cb(Ihandln /*ih*/)
    iterative_solve()
    IupUpdate(canvas)
    return IUP_IGNORE
end function

procedure main()
    IupOpen()
    IupSetGlobal("UTF8MODE","YES") 
    canvas = IupGLCanvas("RASTERSIZE=640x480")
    IupSetCallbacks(canvas, {"ACTION", Icallback("redraw_cb"),
                             "MAP_CB", Icallback("map_cb"),
                             "BUTTON_CB", Icallback("button_cb")})
    dlg = IupDialog(canvas,`TITLE="%s"`,{title})
    IupSetCallback(dlg,"KEY_CB", Icallback("key_cb"))
    IupSetAttributeHandle(NULL,"PARENTDIALOG",dlg)
    timer = IupTimer(Icallback("timer_cb"), 30)
    reset()
    IupShow(dlg)
    IupSetAttribute(canvas, "RASTERSIZE", NULL)
    if platform()!=JS then
        IupMainLoop()
        IupClose()
    end if
end procedure

main()

Python

Translation of: Julia
""" For Rosetta Code task N-queens_minimum_and_knights_and_bishops """

from mip import Model, BINARY, xsum, minimize

def n_queens_min(N):
    """ N-queens minimum problem, oeis.org/A075458 """
    if N < 4:
        brd = [[0 for i in range(N)] for j in range(N)]
        brd[0 if N < 2 else 1][0 if N < 2 else 1] = 1
        return 1, brd

    model = Model()
    board = [[model.add_var(var_type=BINARY) for j in range(N)] for i in range(N)]
    for k in range(N):
        model += xsum(board[k][j] for j in range(N)) <= 1
        model += xsum(board[i][k] for i in range(N)) <= 1

    for k in range(1, 2 * N - 2):
        model += xsum(board[k - j][j] for j in range(max(0, k - N + 1), min(k + 1, N))) <= 1

    for k in range(2 - N, N - 1):
        model += xsum(board[k + j][j] for j in range(max(0, -k), min(N - k, N))) <= 1

    for i in range(N):
        for j in range(N):
            model += xsum([xsum(board[i][k] for k in range(N)),
               xsum(board[k][j] for k in range(N)),
               xsum(board[i + k][j + k] for k in range(-N, N)
                  if 0 <= i + k < N and 0 <= j + k < N),
               xsum(board[i - k][j + k] for k in range(-N, N)
                  if 0 <= i - k < N and 0 <= j + k < N)]) >= 1

    model.objective = minimize(xsum(board[i][j] for i in range(N) for j in range(N)))
    model.optimize()
    return model.objective_value, [[board[i][j].x for i in range(N)] for j in range(N)]


def n_bishops_min(N):
    """ N-Bishops minimum problem (returns N)"""
    model = Model()
    board = [[model.add_var(var_type=BINARY) for j in range(N)] for i in range(N)]

    for i in range(N):
        for j in range(N):
            model += xsum([
               xsum(board[i + k][j + k] for k in range(-N, N)
                  if 0 <= i + k < N and 0 <= j + k < N),
               xsum(board[i - k][j + k] for k in range(-N, N)
                  if 0 <= i - k < N and 0 <= j + k < N)]) >= 1

    model.objective = minimize(xsum(board[i][j] for i in range(N) for j in range(N)))
    model.optimize()
    return model.objective_value, [[board[i][j].x for i in range(N)] for j in range(N)]

def n_knights_min(N):
    """ N-knights minimum problem, oeis.org/A342576 """
    if N < 2:
        return 1, "N"

    knightdeltas = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
    model = Model()
    # to simplify the constraints, embed the board of size N inside a board of size N + 4
    board = [[model.add_var(var_type=BINARY) for j in range(N + 4)] for i in range(N + 4)]
    for i in range(N + 4):
        model += xsum(board[i][j] for j in [0, 1, N + 2, N + 3]) == 0
    for j in range(N + 4):
        model += xsum(board[i][j] for i in [0, 1, N + 2, N + 3]) == 0

    for i in range(2, N + 2):
        for j in range(2, N + 2):
            model += xsum([board[i][j]] + [board[i + d[0]][j + d[1]]
               for d in knightdeltas]) >= 1
            model += xsum([board[i + d[0]][j + d[1]]
               for d in knightdeltas] + [100 * board[i][j]]) <= 100

    model.objective = minimize(xsum(board[i][j] for i in range(2, N + 2) for j in range(2, N + 2)))
    model.optimize()
    minresult = model.objective_value
    return minresult, [[board[i][j].x for i in range(2, N + 2)] for j in range(2, N + 2)]


if __name__ == '__main__':
    examples, pieces, chars = [[], [], []], ["Queens", "Bishops", "Knights"], ['Q', 'B', 'N']
    print("   Squares    Queens   Bishops   Knights")
    for nrows in range(1, 11):
        print(str(nrows * nrows).rjust(10), end='')
        minval, examples[0] = n_queens_min(nrows)
        print(str(int(minval)).rjust(10), end='')
        minval, examples[1] = n_bishops_min(nrows)
        print(str(int(minval)).rjust(10), end='')
        minval, examples[2] = n_knights_min(nrows)
        print(str(int(minval)).rjust(10))
        if nrows == 10:
            print("\nExamples for N = 10:")
            for idx, piece in enumerate(chars):
                print(f"\n{pieces[idx]}:")
                for row in examples[idx]:
                    for sqr in row:
                        print(chars[idx] if sqr == 1 else '.', '', end = '')
                    print()
                print()
Output:
   Squares    Queens   Bishops   Knights
         1         1         1         1
         4         1         2         4
         9         1         3         4
        16         3         4         4
        25         3         5         5
        36         4         6         8
        49         4         7        13
        64         5         8        14
        81         5         9        14
       100         5        10        16

Examples for N = 10:

Queens:
. . . . . . . . . . 
. . Q . . . . . . . 
. . . . . . . . . . 
. . . . . . . . Q . 
. . . . . . . . . . 
. . . . Q . . . . . 
. . . . . . . . . . 
Q . . . . . . . . . 
. . . . . . . . . . 
. . . . . . Q . . . 


Bishops:
. . . . . . . . . . 
. . . . B B . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . B . B . . . 
. . B . . . B . . . 
. . . B . . . . . . 
. . . . . . B . . . 
. . . . B . B . . . 
. . . . . . . . . . 


Knights:
. . . . . . . . . . 
. . N N . . . . . . 
. . N N . . . N N . 
. . . . . . . N N . 
. . . . . . . . . . 
. . . . . . . . . . 
. N N . . . . . . . 
. N N . . . N N . . 
. . . . . . N N . . 
. . . . . . . . . . 

Raku

Due to the time it's taking only a subset of the task are attempted.

Translation of: Go
# 20220705 Raku programming solution

my (@board, @diag1, @diag2, @diag1Lookup, @diag2Lookup, $n, $minCount, $layout);

my %limits   = ( my @pieces = <Q B K> ) Z=> 7,7,6; # >>=>>> 10;
my %names    = @pieces Z=> <Queens Bishops Knights>;

sub isAttacked(\piece, \row, \col) {
   given piece {
      when 'Q' { 
         (^$n)>>.&{ return True if @board[$_;col] || @board[row;$_] }  
	 return True if @diag1Lookup[@diag1[row;col]] || 
	                @diag2Lookup[@diag2[row;col]]
      }
      when 'B' {
         return True if @diag1Lookup[@diag1[row;col]] ||
                        @diag2Lookup[@diag2[row;col]]
      }
      default { # 'K'
         return True if (
            @board[row;col] or 
            row+2 < $n && col-1 >= 0 && @board[row+2;col-1] or
            row-2 >= 0 && col-1 >= 0 && @board[row-2;col-1] or
            row+2 < $n && col+1 < $n && @board[row+2;col+1] or
            row-2 >= 0 && col+1 < $n && @board[row-2;col+1] or
            row+1 < $n && col+2 < $n && @board[row+1;col+2] or
            row-1 >= 0 && col+2 < $n && @board[row-1;col+2] or
            row+1 < $n && col-2 >= 0 && @board[row+1;col-2] or
            row-1 >= 0 && col-2 >= 0 && @board[row-1;col-2]
	 )
      }
   }
   return False
}

sub attacks(\piece, \row, \col, \trow, \tcol) {
   given piece {
      when 'Q' { row==trow || col==tcol || abs(row - trow)==abs(col - tcol) } 
      when 'B' { abs(row - trow) == abs(col - tcol) }
      default  { my (\rd,\cd) = ((trow - row),(tcol - col))>>.abs; # when 'K' 
                 (rd == 1 && cd == 2) || (rd == 2 && cd == 1)               }
   }
}

sub storeLayout(\piece) {
   $layout = [~] @board.map: -> @row { 
      [~] ( @row.map: { $_ ??  piece~' ' !! '. ' } ) , "\n"
   }   
}

sub placePiece(\piece, \countSoFar, \maxCount) {
   return if countSoFar >= $minCount; 
   my ($allAttacked,$ti,$tj) = True,0,0;
   for ^$n X ^$n -> (\i,\j) {
      unless isAttacked(piece, i, j) {
         ($allAttacked,$ti,$tj) = False,i,j andthen last
      }
      last unless $allAttacked 
   }
   if $allAttacked {
      $minCount = countSoFar;
      storeLayout(piece);
      return
   }
   if countSoFar <= maxCount {
      my ($si,$sj) = $ti,$tj;
      if piece eq 'K' {
         ($si,$sj) >>-=>> 2;
         $si = 0 if $si < 0; 
         $sj = 0 if $sj < 0; 
      }
      for ($si..^$n) X ($sj..^$n) -> (\i,\j) {
         unless isAttacked(piece, i, j) {
            if (i == $ti && j == $tj) || attacks(piece, i, j, $ti, $tj) {
               @board[i][j] = True; 
               unless piece eq 'K' {
	          (@diag1Lookup[@diag1[i;j]],@diag2Lookup[@diag2[i;j]])=True xx *               
               }
               placePiece(piece, countSoFar+1, maxCount);
               @board[i][j] = False; 
               unless piece eq 'K' {
                  (@diag1Lookup[@diag1[i;j]],@diag2Lookup[@diag2[i;j]])=False xx *
               }
            }
	 }
      }
   }
}

for @pieces -> \piece {
   say %names{piece}~"\n=======\n";
   loop ($n = 1 ; ; $n++) {
      @board = [ [ False xx $n ] xx $n ]; 
      unless piece eq 'K' {
         @diag1 = ^$n .map: { $_ ... $n+$_-1 } ;
         @diag2 = ^$n .map: { $n+$_-1 ... $_ } ;
	 @diag2Lookup = @diag1Lookup = [ False xx 2*$n-1 ]
      }
      $minCount = 2³¹ - 1; # golang: math.MaxInt32
      my \nSQ   = $n*$n;
      for 1..nSQ -> \maxCount {
         placePiece(piece, 0, maxCount);
         last if $minCount <= nSQ 
      }
      printf("%2d x %-2d : %d\n", $n, $n, $minCount);
      if $n == %limits{piece} {
         printf "\n%s on a %d x %d board:\n", %names{piece}, $n, $n;
         say $layout andthen last
      }
   }
}
Output:
Queens
=======

 1 x 1  : 1
 2 x 2  : 1
 3 x 3  : 1
 4 x 4  : 3
 5 x 5  : 3
 6 x 6  : 4
 7 x 7  : 4

Queens on a 7 x 7 board:
.  Q  .  .  .  .  . 
.  .  .  .  .  Q  . 
.  .  .  .  .  .  . 
Q  .  .  .  .  .  . 
.  .  .  .  Q  .  . 
.  .  .  .  .  .  . 
.  .  .  .  .  .  . 

Bishops
=======

 1 x 1  : 1
 2 x 2  : 2
 3 x 3  : 3
 4 x 4  : 4
 5 x 5  : 5
 6 x 6  : 6
 7 x 7  : 7

Bishops on a 7 x 7 board:
.  .  .  .  .  B  . 
.  .  B  .  .  .  . 
.  .  B  .  B  .  . 
.  .  .  .  .  .  B 
.  .  .  B  .  .  . 
.  .  .  B  .  .  . 
.  .  .  .  .  .  . 

Knights
=======

 1 x 1  : 1
 2 x 2  : 4
 3 x 3  : 4
 4 x 4  : 4
 5 x 5  : 5
 6 x 6  : 8

Knights on a 6 x 6 board:
K  .  .  .  .  K 
.  .  .  .  .  . 
.  .  K  K  .  . 
.  .  K  K  .  . 
.  .  .  .  .  . 
K  .  .  .  .  K 

Wren

CLI

Library: Wren-fmt

This was originally based on the Java code here which uses a backtracking algorithm and which I extended to deal with bishops and knights as well as queens when translating to Wren. I then used the more efficient way for checking the diagonals described here and have now incorporated the improvements made to the Go version.

Although far quicker than it was originally (it now gets to 7 knights in less than a minute), it struggles after that and needs north of 21 minutes to get to 10.

import "./fmt" for Fmt

var board
var diag1
var diag2
var diag1Lookup
var diag2Lookup
var n
var minCount
var layout
 
var isAttacked = Fn.new { |piece, row, col|
    if (piece == "Q") {
        for (i in 0...n) {
            if (board[i][col] || board[row][i]) return true
        }
        if (diag1Lookup[diag1[row][col]] ||
            diag2Lookup[diag2[row][col]]) return true
    } else if (piece == "B") {
        if (diag1Lookup[diag1[row][col]] ||
            diag2Lookup[diag2[row][col]]) return true
    } else { // piece == "K"
        if (board[row][col]) return true
        if (row + 2 < n  && col - 1 >= 0 && board[row + 2][col - 1]) return true   
        if (row - 2 >= 0 && col - 1 >= 0 && board[row - 2][col - 1]) return true
        if (row + 2 < n  && col + 1 < n  && board[row + 2][col + 1]) return true
        if (row - 2 >= 0 && col + 1 < n  && board[row - 2][col + 1]) return true
        if (row + 1 < n  && col + 2 < n  && board[row + 1][col + 2]) return true
        if (row - 1 >= 0 && col + 2 < n  && board[row - 1][col + 2]) return true
        if (row + 1 < n  && col - 2 >= 0 && board[row + 1][col - 2]) return true
        if (row - 1 >= 0 && col - 2 >= 0 && board[row - 1][col - 2]) return true
    }
    return false
}

var attacks = Fn.new { |piece, row, col, trow, tcol|
    if (piece == "Q") {
        return row == trow || col == tcol || (row-trow).abs == (col-tcol).abs
    } else if (piece == "B") {
        return (row-trow).abs == (col-tcol).abs
    } else { // piece == "K"
        var rd = (trow - row).abs
        var cd = (tcol - col).abs
        return (rd == 1 && cd == 2) || (rd == 2 && cd == 1)
    }
}

var storeLayout = Fn.new { |piece|
    var sb = ""
    for (row in board) {
        for (cell in row) sb = sb + (cell ? piece + " " : ". ")
        sb = sb + "\n"
    }
    layout = sb
}

var placePiece // recursive function
placePiece = Fn.new { |piece, countSoFar, maxCount|
    if (countSoFar >= minCount) return
    var allAttacked = true
    var ti = 0
    var tj = 0
    for (i in 0...n) {
        for (j in 0...n) {
            if (!isAttacked.call(piece, i, j)) {
                allAttacked = false
                ti = i
                tj = j
                break
            }
        }
        if (!allAttacked) break
    }
    if (allAttacked) {
        minCount = countSoFar
        storeLayout.call(piece)
        return
    }
    if (countSoFar <= maxCount) {
        var si = (piece == "K") ? (ti-2).max(0) : ti
        var sj = (piece == "K") ? (tj-2).max(0) : tj
        for (i in si...n) {
            for (j in sj...n) {
                if (!isAttacked.call(piece, i, j)) {
                    if ((i == ti && j == tj) || attacks.call(piece, i, j, ti, tj)) {
                        board[i][j] = true
                        if (piece != "K") {
                            diag1Lookup[diag1[i][j]] = true
                            diag2Lookup[diag2[i][j]] = true
                        }
                        placePiece.call(piece, countSoFar + 1, maxCount)
                        board[i][j] = false
                        if (piece != "K") {
                            diag1Lookup[diag1[i][j]] = false
                            diag2Lookup[diag2[i][j]] = false
                        }
                    }
                }
            }
        }
    }
}

var start = System.clock 
var pieces = ["Q", "B", "K"]
var limits = {"Q": 10, "B": 10, "K": 10}
var names  = {"Q": "Queens", "B": "Bishops", "K": "Knights"}
for (piece in pieces) {
    System.print(names[piece])
    System.print("=======\n")
    n = 1
    while (true) {
        board = List.filled(n, null)
        for (i in 0...n) board[i] = List.filled(n, false)
        if (piece != "K") {
            diag1 = List.filled(n, null)
            for (i in 0...n) {
                diag1[i] = List.filled(n, 0)
                for (j in 0...n) diag1[i][j] = i + j
            }
            diag2 = List.filled(n, null)
            for (i in 0...n) {
                diag2[i] = List.filled(n, 0)
                for (j in 0...n) diag2[i][j] = i - j + n - 1
            }
            diag1Lookup = List.filled(2*n-1, false)
            diag2Lookup = List.filled(2*n-1, false)
        }
        minCount = Num.maxSafeInteger
        layout = ""
        for (maxCount in 1..n*n) {
            placePiece.call(piece, 0, maxCount)
            if (minCount <= n*n) break
        }
        Fmt.print("$2d x $-2d : $d", n, n, minCount)
        if (n == limits[piece]) {
            Fmt.print("\n$s on a $d x $d board:", names[piece], n, n)
            System.print("\n" + layout)
            break
        }
        n = n + 1
    }
}
System.print("Took %(System.clock - start) seconds.")
Output:
Queens
=======

 1 x 1  : 1
 2 x 2  : 1
 3 x 3  : 1
 4 x 4  : 3
 5 x 5  : 3
 6 x 6  : 4
 7 x 7  : 4
 8 x 8  : 5
 9 x 9  : 5
10 x 10 : 5

Queens on a 10 x 10 board:

. . Q . . . . . . . 
. . . . . . . . . . 
. . . . . . . . Q . 
. . . . . . . . . . 
. . . . Q . . . . . 
. . . . . . . . . . 
Q . . . . . . . . . 
. . . . . . . . . . 
. . . . . . Q . . . 
. . . . . . . . . . 

Bishops
=======

 1 x 1  : 1
 2 x 2  : 2
 3 x 3  : 3
 4 x 4  : 4
 5 x 5  : 5
 6 x 6  : 6
 7 x 7  : 7
 8 x 8  : 8
 9 x 9  : 9
10 x 10 : 10

Bishops on a 10 x 10 board:

. . . . . . . . . B 
. . . . . . . . . . 
. . . B . B . . . . 
. . . B . B . B . . 
B . . . . . . . . . 
. . . . . . . . . . 
. . . . . B . . . . 
. . . . . B . . . . 
. . . . . B . . . . 
. . . . . . . . . . 

Knights
=======

 1 x 1  : 1
 2 x 2  : 4
 3 x 3  : 4
 4 x 4  : 4
 5 x 5  : 5
 6 x 6  : 8
 7 x 7  : 13
 8 x 8  : 14
 9 x 9  : 14
10 x 10 : 16

Knights on a 10 x 10 board:

. . . . . . . . . . 
. . K K . . . . . . 
. . K K . . . K K . 
. . . . . . . K K . 
. . . . . . . . . . 
. . . . . . . . . . 
. K K . . . . . . . 
. K K . . . K K . . 
. . . . . . K K . . 
. . . . . . . . . . 

Took 1276.522608 seconds.

Embedded

Library: Wren-linear

This is the first outing for the above module which is a wrapper for GLPK.

As there are quite a lot of variables and constraints in this task, I have used MathProg scripts to solve it rather than calling the basic API routines directly. The script file needs to be changed for each chess piece and each value of 'n' as there appear to be no looping constructs in MathProg itself.

Despite this, the program runs in only 3.25 seconds which is far quicker than I was expecting.

I have borrowed one or two tricks from the Julia/Python versions in formulating the constraints.

import "./linear" for Prob, Glp, Tran, File
import "./fmt" for Fmt

var start = System.clock

var queenMpl = """
var x{1..n, 1..n}, binary;
s.t. a{i in 1..n}: sum{j in 1..n} x[i,j] <= 1;
s.t. b{j in 1..n}: sum{i in 1..n} x[i,j] <= 1;
s.t. c{k in 2-n..n-2}: sum{i in 1..n, j in 1..n: i-j == k} x[i,j] <= 1;
s.t. d{k in 3..n+n-1}: sum{i in 1..n, j in 1..n: i+j == k} x[i,j] <= 1;
s.t. e{i in 1..n, j in 1..n}:
    sum{k in 1..n} x[i,k] +
    sum{k in 1..n} x[k,j] +
    sum{k in (1-n)..n: 1 <= i + k && i + k <= n && 1 <= j + k && j + k <=n} x[i+k,j+k]  +
    sum{k in (1-n)..n: 1 <= i - k && i - k <= n && 1 <= j + k && j + k <=n} x[i-k, k+j] >= 1;

minimize obj: sum{i in 1..n, j in 1..n} x[i,j];
solve;
end;

"""

var bishopMpl = """
var x{1..n, 1..n}, binary;
s.t. a{k in 2-n..n-2}: sum{i in 1..n, j in 1..n: i-j == k} x[i,j] <= 1;
s.t. b{k in 3..n+n-1}: sum{i in 1..n, j in 1..n: i+j == k} x[i,j] <= 1;
s.t. c{i in 1..n, j in 1..n}:
    sum{k in (1-n)..n: 1 <= i + k && i + k <= n && 1 <= j + k && j + k <=n} x[i+k,j+k]  +
    sum{k in (1-n)..n: 1 <= i - k && i - k <= n && 1 <= j + k && j + k <=n} x[i-k, k+j] >= 1;

minimize obj: sum{i in 1..n, j in 1..n} x[i,j];
solve;
end;

"""

var knightMpl = """
set deltas, dimen 2;
var x{1..n+4, 1..n+4}, binary;
s.t. a{i in 1..n+4}: sum{j in 1..n+4: j < 3 || j > n + 2} x[i,j] = 0;
s.t. b{j in 1..n+4}: sum{i in 1..n+4: i < 3 || i > n + 2} x[i,j] = 0;
s.t. c{i in 3..n+2, j in 3..n+2}: x[i, j] + sum{(k, l) in deltas} x[i + k, j + l] >= 1;
s.t. d{i in 3..n+2, j in 3..n+2}: sum{(k, l) in deltas} x[i + k, j + l] + 100 * x[i, j] <= 100;

minimize obj: sum{i in 3..n+2, j in 3..n+2} x[i,j];
solve;
data;
set deltas := (1,2) (2,1) (2,-1) (1,-2) (-1,-2) (-2,-1) (-2,1) (-1,2);
end;

"""

var mpls   = {"Q": queenMpl, "B": bishopMpl, "K": knightMpl}
var pieces = ["Q", "B", "K"]
var limits = {"Q": 10, "B": 10, "K": 10}
var names  = {"Q": "Queens", "B": "Bishops", "K": "Knights"}
var fname  = "n_pieces.mod"

Glp.termOut(Glp.OFF)
for (piece in pieces) {
    System.print(names[piece])
    System.print("=======\n")
    for (n in 1..limits[piece]) {
        var first = "param n, integer, > 0, default %(n);\n"
        File.write(fname, first + mpls[piece])
        var mip = Prob.create()
        var tran = Tran.mplAllocWksp()
        var ret = tran.mplReadModel(fname, 0)
        if (ret != 0) System.print("Error on translating model.")
        if (ret == 0) {
            ret = tran.mplGenerate(null)
            if (ret != 0) System.print("Error on generating model.")
            if (ret == 0) {
                tran.mplBuildProb(mip)
                mip.simplex(null)
                mip.intOpt(null)
                Fmt.print("$2d x $-2d : $d", n, n, mip.mipObjVal.round)
                if (n == limits[piece]) {
                    Fmt.print("\n$s on a $d x $d board:\n", names[piece], n, n)
                    var cols = {}
                    if (piece != "K") {
                        for (i in 1..n*n) cols[mip.colName(i)] = mip.mipColVal(i)
                        for (i in 1..n) {
                            for (j in 1..n) {
                                var char = (cols["x[%(i),%(j)]"] == 1) ? "%(piece) " : ". "
                                System.write(char)
                            }
                            System.print()
                        }
                    } else {
                        for (i in 1..(n+4)*(n+4)) cols[mip.colName(i)] = mip.mipColVal(i)
                        for (i in 3..n+2) {
                            for (j in 3..n+2) {
                                var char = (cols["x[%(i),%(j)]"] == 1) ? "%(piece) " : ". "
                                System.write(char)
                            }
                            System.print()
                        }
                    }
                }
            }
        }
        tran.mplFreeWksp()
        mip.delete()
    }
    System.print()
}
File.remove(fname)
System.print("Took %(System.clock - start) seconds.")
Output:
Queens
=======

 1 x 1  : 1
 2 x 2  : 1
 3 x 3  : 1
 4 x 4  : 3
 5 x 5  : 3
 6 x 6  : 4
 7 x 7  : 4
 8 x 8  : 5
 9 x 9  : 5
10 x 10 : 5

Queens on a 10 x 10 board:

. . . . . . Q . . . 
. . . . . . . . . . 
Q . . . . . . . . . 
. . . . . . . . . . 
. . . . Q . . . . . 
. . . . . . . . . . 
. . . . . . . . Q . 
. . . . . . . . . . 
. . Q . . . . . . . 
. . . . . . . . . . 

Bishops
=======

 1 x 1  : 1
 2 x 2  : 2
 3 x 3  : 3
 4 x 4  : 4
 5 x 5  : 5
 6 x 6  : 6
 7 x 7  : 7
 8 x 8  : 8
 9 x 9  : 9
10 x 10 : 10

Bishops on a 10 x 10 board:

B . . . . . . . . . 
. . . . B . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . B . B B . B . 
. B . B . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . B . . . . 
. . B . . . . . . . 

Knights
=======

 1 x 1  : 1
 2 x 2  : 4
 3 x 3  : 4
 4 x 4  : 4
 5 x 5  : 5
 6 x 6  : 8
 7 x 7  : 13
 8 x 8  : 14
 9 x 9  : 14
10 x 10 : 16

Knights on a 10 x 10 board:

. . . . . K . . . . 
. . K . . . . . . . 
. . K K . . . K K . 
. . . . . . . K . . 
K . . . . . . . . . 
. . . . . . . . . K 
. . K . . . . . . . 
. K K . . . K K . . 
. . . . . . . K . . 
. . . . K . . . . . 

Took 3.244584 seconds.