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
Wren
Although this seems to work and give the correct answers, it's very slow indeed taking just under 5.5 minutes to run even when the board sizes are limited to 8 x 8 (queens), 6 x 6 (bishops) and 5 x 5 (knights).
It's 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. <lang ecmascript>import "./fmt" for Fmt
var board 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
}
for (i in 0...n) {
if (row-i >= 0 && col-i >= 0 && board[row-i][col-i]) return true
if (row-i >= 0 && col+i < n && board[row-i][col+i]) return true
if (row+i < n && col-i >= 0 && board[row+i][col-i]) return true
if (row+i < n && col+i < n && board[row+i][col+i]) return true
}
} else if (piece == "B") {
if (board[row][col]) return true
for (i in 0...n) {
if (row-i >= 0 && col-i >= 0 && board[row-i][col-i]) return true
if (row-i >= 0 && col+i < n && board[row-i][col+i]) return true
if (row+i < n && col-i >= 0 && board[row+i][col-i]) return true
if (row+i < n && col+i < n && board[row+i][col+i]) 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 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|
if (countSoFar >= minCount) return
var allAttacked = true
for (i in 0...n) {
for (j in 0...n) {
if (!isAttacked.call(piece, i, j)) {
allAttacked = false
break
}
}
if (!allAttacked) break
}
if (allAttacked) {
minCount = countSoFar
storeLayout.call(piece)
return
}
for (i in 0...n) {
for (j in 0...n) {
if (!isAttacked.call(piece, i, j)) {
board[i][j] = true
placePiece.call(piece, countSoFar + 1)
board[i][j] = false
}
}
}
}
var pieces = ["Q", "B", "K"] var limits = {"Q": 8, "B": 5, "K": 4} 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)
minCount = Num.maxSafeInteger
layout = ""
placePiece.call(piece, 0)
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
}
}</lang>
- 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 Queens on a 8 x 8 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 Bishops on a 6 x 6 board: 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 Knights on a 5 x 5 board: K . . . . . . . . . . . K K . . . K K . . . . . .