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> // 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 </lang>
- 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
Much quicker, of course, than Wren itself - only takes about 35 seconds to run when using the same board limits.
However, it struggles as soon as you try to increase the board sizes for bishops or knights. When you try 7 x 7 for bishops (as the code below does) the run time shoots up to almost 5.5 minutes. <lang go>package main
import (
"fmt" "math" "strings"
)
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 board[row][col] { return true } 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 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 int) {
if countSoFar >= minCount { return } allAttacked := true for i := 0; i < n; i++ { for j := 0; j < n; j++ { if !isAttacked(piece, i, j) { allAttacked = false break } } if !allAttacked { break } } if allAttacked { minCount = countSoFar storeLayout(piece) return }
for i := 0; i < n; i++ { for j := 0; j < n; j++ { if !isAttacked(piece, i, j) { board[i][j] = true diag1Lookup[diag1[i][j]] = true diag2Lookup[diag2[i][j]] = true placePiece(piece, countSoFar+1) board[i][j] = false diag1Lookup[diag1[i][j]] = false diag2Lookup[diag2[i][j]] = false } } }
}
func main() {
pieces := []string{"Q", "B", "K"} limits := map[string]int{"Q": 10, "B": 7, "K": 5} 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) } 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 = "" placePiece(piece, 0) 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 } } }
}</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 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 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 Knights on a 5 x 5 board: K . . . . . . . . . . . K K . . . K K . . . . . .
Quick hack [temp]
Above with my (--Pete Lomax (talk)) suggestions applied, but not optimising bishops, so I've kept that at 9 (w/should drop to 49s or so, as-is 10B clocks in at 3m44s) <lang go>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 board[row][col] { return true } 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) { //func placePiece(piece string, countSoFar 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 { for i := 0; i < n; i++ { for j := 0; j < n; j++ { if !isAttacked(piece, i, j) { if (i==ti && j==tj) || Attacks(piece,i,j,ti,tj) { board[i][j] = true diag1Lookup[diag1[i][j]] = true diag2Lookup[diag2[i][j]] = true
// placePiece(piece, countSoFar+1)
placePiece(piece, countSoFar+1, maxCount) board[i][j] = false 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": 9, "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) } 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 = ""
// placePiece(piece, 0)
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(" (this took %s)\n\n", elapsed)
}</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 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 Bishops on a 9 x 9 board: 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 . . . . . . . . . . . . (this took 1m1.7084192s)
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:
<lang J> 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=: Template:Coords
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=: Template:For seq. y,"1 0(
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.
}}</lang>
Task output:
<lang J> 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 . . . . | |. . . . . . . . . . |. . . . . . . . . . | +--------------------+--------------------+ </lang>
Julia
Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support. <lang ruby>""" 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])
</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 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 . . . . . . . . . . . .
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
<lang pascal>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. </lang>
- @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
Phix
You can run this online here, and explore the finished (green) ones while it toils away on the tougher ones, or watch it working. It examines 21,801,024 positions before solving N10, plus doing things in 0.4s chunks on a timer probably don't help, so it ends up taking just over 3 mins to completely finish on the desktop, though 18mins 46s in my web browser, but at least you can explore, pause, resume, or quit it at any point.
-- -- 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, -- 2.8s (13 is 3minutes 46s, with maxn=1) maxb = 10, -- 1s (100 is 10s, with maxq=1 and maxn=1) maxn = 10, -- 3mins 3s (9: 17s, 8: 7.2s, with maxq=1) maxqbn = max({maxq,maxb,maxn}) 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[n+1..n+m] 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 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", QBNU = utf8_to_utf32("♕♗♘") integer bn = 8, -- chosen board is nxn (1..10) cp = 1 -- piece (1,2,3 for QBN) sequence state 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 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,row,col,bn) -- nope! sequence mnm = mm_baby(mm,piece,col,row,bn) -- yepp! (damy) 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 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>0 and p<4 and n>0 then cp = p bn = min(n,length(state[cp])) 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
<lang python>""" 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()
</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 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 . . . . . . . . . . . .
Wren
Although this seems to work and give the correct answers, it's very slow taking about 23.5 minutes to run even when the board sizes are limited to 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. I've used the more efficient way for checking the diagonals described here. <lang ecmascript>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 (board[row][col]) return true 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 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 diag1Lookup[diag1[i][j]] = true diag2Lookup[diag2[i][j]] = true placePiece.call(piece, countSoFar + 1) board[i][j] = false diag1Lookup[diag1[i][j]] = false diag2Lookup[diag2[i][j]] = false } } }
}
var pieces = ["Q", "B", "K"] var limits = {"Q": 10, "B": 6, "K": 5} 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) 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 = "" 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 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 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 . . . . . .
If I limit the board size for the queens to 8 x 8, the run time comes down to around 2 minutes 12 seconds and the following example layout is produced:
Queens on a 8 x 8 board: Q . . . . . . . . . Q . . . . . . . . . Q . . . . Q . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . .