N-queens minimum and knights and bishops
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