N-queens minimum and knights and bishops

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.

F#

<lang fsharp> // N-Queens minimum and Knights and Bishops. Nigel Galloway: April 19th., 2022

open Microsoft.SolverFoundation.Services

open Microsoft.SolverFoundation.Common

let fN n g l=([0..n-1]@[n+1..l-1]|>List.map(fun n->sprintf "N_%02d_%02d" n g))@([0..g-1]@[g+1..l-1]|>List.map(fun g->sprintf "N_%02d_%02d" n g)) let fG n g l=List.unfold(fun(n,g)->if n>l-2||g>l-2 then None else let n,g=n+1,g+1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)@

            List.unfold(fun(n,g)->if n<1||g>l-2 then None else let n,g=n-1,g+1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)@
            List.unfold(fun(n,g)->if n<1||g<1 then None else let n,g=n-1,g-1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)@
            List.unfold(fun(n,g)->if n>l-2||g<1 then None else let n,g=n+1,g-1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)

let fK n g l=[(1,-2);(2,-1);(1,2);(2,1);(-1,2);(-2,1);(-1,-2);(-2,-1)]|>List.choose(fun(x,y)->match n+x,g+y with p,q when p>=0 && q>=0 && p<=l-1 && q<=l-1->Some(sprintf "N_%02d_%02d" p q) |_->None) let sln f size=

 let context=SolverContext.GetContext()
 context.ClearModel()
 let model=context.CreateModel()
 for n in 0..size-1 do for g in 0..size-1 do model.AddDecision(new Decision(Domain.IntegerRange(Rational.Zero,Rational.One), sprintf "N_%02d_%02d" n g))
 for n in 0..size-1 do for g in 0..size-1 do model.AddConstraint(sprintf "G_%02d_%02d" n g,([sprintf "0<%d*N_%02d_%02d" (size*size) n g]@f n g size|>String.concat "+")+sprintf "<%d" (size*size+1))
 model.AddGoal("Goal0", GoalKind.Minimize, [for n in 0..size-1 do for g in 0..size-1->sprintf "N_%02d_%02d" n g]|>String.concat "+")
 context.Solve()

let Bishops,Queens,Knights=sln fG, sln (fun n g l->fG n g l@fN n g l), sln fK let printSol(n:Solution)=n.Decisions|>Seq.filter(fun n->n.GetDouble()=1.0)|>Seq.iteri(fun n g->let g=g.Name in printfn "Place Piece %d in row %d column %d" (n+1) (int(g.[2..3])) (int(g.[5..6]))); printfn "" let pieces(n:Solution)=n.Decisions|>Seq.filter(fun n->n.GetDouble()=1.0)|>Seq.length

printfn "%10s%10s%10s%10s" "Squares" "Queens" "Bishops" "Knights" [1..10]|>List.iter(fun n->printfn "%10d%10d%10d%10d" (n*n) (pieces(Queens n)) (pieces(Bishops n)) (pieces(Knights n))) printfn "Queens on a 8x8 Board"; printSol(Queens 8) printfn "Knights on a 8x8 Board"; printSol(Knights 8) </lang>

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

Queens on a 8x8 Board
Place Piece 1 in row 0 column 4
Place Piece 2 in row 3 column 0
Place Piece 3 in row 4 column 7
Place Piece 4 in row 6 column 1
Place Piece 5 in row 7 column 3

Knights on a 8x8 Board
Place Piece 1 in row 0 column 0
Place Piece 2 in row 0 column 3
Place Piece 3 in row 1 column 0
Place Piece 4 in row 2 column 0
Place Piece 5 in row 2 column 5
Place Piece 6 in row 2 column 6
Place Piece 7 in row 3 column 5
Place Piece 8 in row 4 column 2
Place Piece 9 in row 5 column 1
Place Piece 10 in row 5 column 2
Place Piece 11 in row 5 column 7
Place Piece 12 in row 6 column 7
Place Piece 13 in row 7 column 4
Place Piece 14 in row 7 column 7