Rosetta Code

N-queens minimum and knights and bishops: Difference between revisions

Page Discussion

N-queens minimum and knights and bishops (view source)

Revision as of 09:07, 6 January 2024

55,784 bytes added ,  4 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(33 intermediate revisions by 11 users not shown)
Line 5:
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:
* [[oeis:A075324|OEIS Independent domination number for queens]]
* [[oeis:A342576|OEIS Independent domination number for knights]]
* [https://www.sciencedirect.com/science/article/pii/S0166218X09003722 ScienceDirect | minimum dominating set of queens] - ways to do it.
<br><br>
=={{header|F_Sharp|F#}}==
<langsyntaxhighlight lang="fsharp">
// N-QueensMinimum minimumknights andto Knightsattack andall Bishopssquares not occupied on an NxN chess board. Nigel Galloway: AprilMay 19th12th., 2022
type att={n:uint64; g:uint64}
open Microsoft.SolverFoundation.Services
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}
open Microsoft.SolverFoundation.Common
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 l=([0..n-g-g-1]@[;n-g-g+1..l;n-g+2;n-g-2;n+g+g-1;n+g+g+1;n+g-2;n+g+2]|>List.mapfilter(fun nx->sprintf0<=x "N_%02d_%02d"&& nx<g*g && abs(x%g-n%g))@+abs([0..x/g-1]@[n/g+1)=3)|>List..l-1]distinct|>List.map(fun gn->sprintf "N_%02d_%02d" n g)/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])
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)@
type cand={att:att; n:int; g:int}
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)@
type Solver={n:cand seq; i:int[]; g:(int -> att) * (int -> att); e:att; l:int[]}
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)@
member Listthis.unfold(funtest()=let rec test n, i g) e l=match g with 0UL->(if n>l-2||g<1i=this.e then NoneSome(n,e) else letNone)|g when n,g%2UL=n+1,g1UL-1>test inn Some(sprintf "N_%02d_%02d" ni+((snd this.g,)(n,gthis.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)
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)
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 sln f size=
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)
let context=SolverContext.GetContext()
|_->slvK (n.xP()) i (g+1) l
context.ClearModel()
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"))
let model=context.CreateModel()
for n in 0..size-1 do for g in 0..sizes-1 do modeln.AddDecision(new Decision(Domain[g,0.IntegerRange(Rational.Zero,Rationals-1]|>Seq.One),iter(fun sprintfg->printf "N_%02d_%02ds" n g)); printfn ""
let solveK g=printfn "\nSolving for %dx%d board" g 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))
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)|]
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 "+")
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)
context.Solve()
let t,f=System.DateTime.UtcNow,fN g
let Bishops,Queens,Knights=sln fG, sln (fun n g l->fG n g l@fN n g l), sln fK
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 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 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 pieces(n:Solution)=n.Decisions|>Seq.filter(fun n->n.GetDouble()=1.0)|>Seq.length
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
printfn "%10s%10s%10s%10s" "Squares" "Queens" "Bishops" "Knights"
|_->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
[1..10]|>List.iter(fun n->printfn "%10d%10d%10d%10d" (n*n) (pieces(Queens n)) (pieces(Bishops n)) (pieces(Knights n)))
printfn "Solution found using %d knights in %A:" rn (System.DateTime.UtcNow-t); tc rb.att
printfn "Queens on a 8x8 Board"; printSol(Queens 8)
for n in 1..10 do solveK n
printfn "Knights on a 8x8 Board"; printSol(Knights 8)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Solving for 1x1 board
Squares Queens Bishops Knights
Solution found using 1 knights in 00:00:00.0331768:
1 1 1 1
X
4 1 2 4
 
9 1 3 4
Solving for 2x2 board
16 3 4 4
Solution found using 2 knights in 00:00:00:
25 3 5 5
Xo
36 4 6 8
oX
49 4 7 13
 
64 5 8 14
Solving for 3x3 board
81 5 9 14
Solution found using 4 knights in 00:00:00.0156191:
100 5 10 16
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
Queens on a 8x8 Board
Solution found using 14 knights in 00:00:10.2331055:
Place Piece 1 in row 0 column 4
.~.~.~.~.
Place Piece 2 in row 3 column 0
~.o.~.o.~
Place Piece 3 in row 4 column 7
.~Xo.oX~.
Place Piece 4 in row 6 column 1
~.~.~.~.~
Place Piece 5 in row 7 column 3
X~.~.~.~X
~.~.~.~.~
.~Xo.oX~.
~.o.~.o.~
.~.~.~.~.
 
Solving for 10x10 board
Knights on a 8x8 Board
Solution found using 16 knights in 00:04:44.0573668:
Place Piece 1 in row 0 column 0
~.~.~.~.~.
Place Piece 2 in row 0 column 3
.~.~.~Xo.~
Place Piece 3 in row 1 column 0
~Xo.~.oX~.
Place Piece 4 in row 2 column 0
.oX~.~.~.~
Place Piece 5 in row 2 column 5
~.~.~.~.~.
Place Piece 6 in row 2 column 6
.~.~.~.~.~
Place Piece 7 in row 3 column 5
~.~.~.~Xo.
Place Piece 8 in row 4 column 2
.~Xo.~.oX~
Place Piece 9 in row 5 column 1
~.oX~.~.~.
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
</pre>
 
=={{header|Go}}==
This was originally a translation of the Wren entry but was substantially improved by [[User:Petelomax|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.
{{trans|Wren}}
Much quicker, of course, than Wren itself - only takes about 35 seconds to run when using the same board limits.
 
Timing is for an Intel Core i7-8565U machine running Ubuntu 20.04.
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.
<langsyntaxhighlight lang="go">package main
 
import (
Line 83 ⟶ 137:
"math"
"strings"
"time"
)
 
Line 102 ⟶ 157:
}
} else if piece == "B" {
if board[row][col] {
return true
}
if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] {
return true
Line 138 ⟶ 190:
}
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)
}
}
 
Line 155 ⟶ 226:
}
 
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
}
Line 176 ⟶ 251:
return
}
if countSoFar <= maxCount {
 
for i := 0; isi < n; i++:= {ti
for jsj := 0; j < n; j++ {tj
if !isAttacked(piece, i,== j)"K" {
si = si - board[i][j] = true2
sj = sj - diag1Lookup[diag1[i][j]] = true2
if si < 0 diag2Lookup[diag2[i][j]] = true{
placePiece(piece,si countSoFar+1)= 0
board[i][j] = false}
if sj < 0 diag1Lookup[diag1[i][j]] = false{
diag2Lookup[diag2[i][j]]sj = false0
}
}
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
}
}
}
}
}
Line 193 ⟶ 287:
 
func main() {
start := time.Now()
pieces := []string{"Q", "B", "K"}
limits := map[string]int{"Q": 10, "B": 710, "K": 510}
names := map[string]string{"Q": "Queens", "B": "Bishops", "K": "Knights"}
for _, piece := range pieces {
Line 205 ⟶ 300:
board[i] = make([]bool, n)
}
diag1if piece != make([][]int,"K" n){
for i := 0; idiag1 <= make([][]int, n; i++ {)
diag1[for i] := make([]int,0; i < n); i++ {
for j := 0; jdiag1[i] <= make([]int, n; j++ {)
diag1[i][for j] := i0; +j < n; j++ {
diag1[i][j] = i + j
}
}
} diag2 = make([][]int, n)
diag2 for i := make([][]int,0; i < n); i++ {
for i := 0; i < n; diag2[i++] {= make([]int, n)
diag2[i] for j := make([]int,0; j < n); j++ {
for diag2[i][j] := 0;i - j <+ n; j++- {1
diag2[i][j] = i - j + n - 1}
}
diag1Lookup = make([]bool, 2*n-1)
diag2Lookup = make([]bool, 2*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)
placePiece(piece, 0, maxCount)
if minCount <= n*n {
break
}
}
fmt.Printf("%2d x %-2d : %d\n", n, n, minCount)
if n == limits[piece] {
Line 232 ⟶ 334:
}
}
elapsed := time.Now().Sub(start)
}</lang>
fmt.Printf("Took %s\n", elapsed)
}</syntaxhighlight>
 
{{out}}
Line 273 ⟶ 377:
6 x 6 : 6
7 x 7 : 7
8 x 8 : 8
9 x 9 : 9
10 x 10 : 10
 
Bishops on a 710 x 710 board:
 
. B. . B. . . . . . B
. . . B. . . . . . .
. . . B . B . . . .
. . . B . B . B . .
B . . . . . . . . .
. . B. B. . . . . . .
. . . . . B . . . .
. . . . . B . . . .
. . . . . B . . . .
. . . . . . . . . .
 
Knights
Line 292 ⟶ 402:
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 510 x 510 board:
 
K. . . . . . . . . .
. . K K . . . . . .
. . K K . . . K K .
. . . . . . . K K .
. . . . . . . . . .
. . . . . . . . . .
. K K . . . . . . .
. K K . . . K K . .
. . . . . . K K . .
. . . . . . . . . .
 
Took 22.383253365s
</pre>
 
=={{header|J}}==
 
AThis crudeis initiala crude attempt -- brute force search with some minor state space pruning. I am not patient enough to run this for 9x9boards andlarger 10x10than boards7x7 for bishops and knights:
 
<syntaxhighlight lang="j">
<lang J>genboard=: {{
genboard=: {{
safelen=:2*len=. {.y
safelen=:2*len=: {.y
shape=: 2$len
board=: shape$0
safeshape=: 2*shape,~safelen
c=:,coords=: safeshape#.shape#:i.shape
qrow=. i:{.shape-1
Line 325 ⟶ 449:
}}
 
placebishops=: {{coords #&,~ 1 (<.-:len)} board}}
place=: {{
 
N=. #r=. _#~#c
placequeens=: {{
for_open.first do.
N=. 0
board=. coords e.y+open
while. ifN=. 0 e.,boardN+1 do.
assert. N<:#c
seq=. open y place1 N board
iffor_seq. N>:#seqfirst do.
Nboard=. <:#r=coords e. queen+seq
if. end0 e.,board do.
else if. open1<N returndo.
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.
rEMPTY
}}
 
place1placeknights=: {{
rN=. (n+2) {.!._ x0
while. N=. nN+1 do.
todo= assert. (,0=y)N<:#c
for_seq. c do.
lim=. >./,(first +&{: x)+m
board=. coords e.knight+seq
for_open. (#~ lim>:]) todo do.
board=. y> if.coords 0 e.m+open,board do.
if. 0 e if.,board 1<N do.
if seq=. board knight place1 N>#x do.seq
seq=. x,open mif. place1 N board#seq do.
if assert. N>-:#seq do.
N=. <:#r= 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. x,openseq return.
end.
end.
rEMPTY
}}
 
task=: {{
QB=:KQ=:BK=:i.0
for_order.1+i.10y do.
genboard order
QB=: 1j1#"1'.QB'{~coords e.qb=. placeplacebishops queen''
KQ=: 1j1#"1'.KQ'{~coords e.kq=. placeplacequeens knight''
if. 8>order do.
B=: '.B'{~coords e.b=. place bishop
K=: 1j1#"1'.K'{~coords e.k=. placeknights ''
echo (":Q;B;K),&.|:>(' Q: ',":#q);(' B: ',":#b);' K: ',":#k
echo (":B;Q;K),&.|:>(' B: ',":#b);(' Q: ',":#q);' K: ',":#k
else.
echo (":B;Q),&.|:>(' B: ',":#b);' Q: ',":#q
end.
end.
}}</langsyntaxhighlight>
 
Task output:
 
<langsyntaxhighlight Jlang="j"> task'' 10
+--+--+--+ B: 1
┌─┬─┬─┐ Q: 1
|B |Q |K | Q: 1
│Q│B│K│ B: 1
+--+--+--+ K: 1
└─┴─┴─┘ K: 1
+----+----+----+ B: 2
┌──┬──┬──┐ Q: 1
|. . |Q . |K K | Q: 1
│Q.│BB│KK│ B: 2
│|B B |. .│..│KK│ |K K | K: 4
+----+----+----+
└──┴──┴──┘
+------+------+------+ B: 3
┌───┬───┬───┐ Q: 1
│|. . .│ |. . .│KKK│ B|K K K | Q: 31
│|B B B |. Q .│BBB│ |. K .│ | K: 4
│|. . .│ |. . .│. |. .│ . |
+------+------+------+
└───┴───┴───┘
+--------+--------+--------+ B: 4
┌────┬────┬────┐ Q: 3
│Q|. . .│ . |Q . . .│ |. K K ...│ B| Q: 43
|. . . . |. . Q . |. K K . | K: 4
│..Q.│BBBB│KKKK│ K: 4
│|B B B B |. . . .│. |. . .│....│ . |
│|.Q . .│ . |. Q . .│ |. . ..│ . |
+--------+--------+--------+
└────┴────┴────┘
+----------+----------+----------+ B: 5
┌─────┬─────┬─────┐ Q: 3
│Q|. . . .│B .B |Q . .│K . . |K . .│ B. . | Q: 53
│|. . .Q .│ . |.B . . Q .│ |. . . . .│ | K: 5
│|B B B B B |. . . . .│ |. ....│..KK.│ K K . |
│|. .Q . .│ .BB |. .│ Q . .KK |.│ . K K . |
│|. . . . .│ |. . . . .│. |. . . .│ . |
+----------+----------+----------+
└─────┴─────┴─────┘
+------------+------------+------------+ B: 6
┌──────┬──────┬──────┐ Q: 4
│Q|. . . . .│B . |Q .B . .│K . . |K . .K│ B. . K | Q: 64
│|. .Q . . .│ . |. . Q .B . .│ |. . . . . .│ | K: 8
│|. . . . .Q│ . |. .B . .│ . Q |.KK. .│ K K . . |
│|B B B B B B |. . . . . .│ |. .....│..KK..│ K K . . |
│|. . . . . .│ |. .BB . .│ . . |. . . .│ . . |
│|.Q . . . .│ . |. Q . . . .│K |K . . ..K│ . K |
+------------+------------+------------+
└──────┴──────┴──────┘
+--------------+--------------+--------------+ QB: 5 7
¦Q|. . . . . .¦ . |. . . . . .¦KKKK . |K K K K .¦ B:K 7. | Q: 4
¦|. .Q . . . . . |. Q . .¦B .BBB . .¦ |. . . . . . .¦ | K: 13
¦|. . . .Q . .¦ . |. . . . Q . .¦ |. . . . . K.¦ . |
¦.Q.....¦...|B B B B B B B |. . .¦K . . . . |K .¦ . . . K . |
¦|. . .Q . . .¦ . |. . . . . .¦ . |. . . . ..¦ . . |
¦|. . . . . . .¦ |Q . .BB . . .¦K.KK . |K .¦ K K . K . |
¦|. . . . . . .¦ |. . . Q . . . |.¦. . . . . .K¦ K |
+--------------+--------------+--------------+
+----------------+----------------+ QB: 5 8
¦Q|. . . . . . .¦ . |Q . . . . . . .¦KKK.....¦ B:| 8Q: 5
¦|. .Q . . . . .¦B . |.BBB . Q .¦. . . ..K..¦ K:. 14|
¦|. . . .Q . . .¦. . |. . . ...¦....KK..¦ Q . . . |
¦|.Q . . . . . .¦ . |. Q . .B...¦K . . .....¦ . |
|B B B B B B B B |. . . Q . . . . |
¦...Q....¦....B...¦.......K¦
¦|. . . . . . . .¦ |. . . . . . ..¦..KK...K¦ . |
¦|. . . . . . . .¦ |. . .BB . . .¦..K .....¦ . |
¦|. . . . . . . .¦ |. . . . . . ..¦.....K.K¦ . |
+----------------+----------------+
+------------------+------------------+ B: 9
|attention interrupt: place</lang>
|. . . . . . . . . |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 . . . . |
|. . . . . . . . . . |. . . . . . . . . . |
+--------------------+--------------------+
</syntaxhighlight>
 
=={{header|Julia}}==
For 9 and 10 for queens:
Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support.
<lang J> (":<'.Q'{~coords e. q),&.|:,:' Q: ',":#q=. place queen [(genboard 9)
<syntaxhighlight lang="julia">""" Rosetta code task N-queens_minimum_and_knights_and_bishops """
┌─────────┐ Q: 5
 
│Q........│
import Cbc
│..Q......│
using JuMP
│......Q..│
using LinearAlgebra
│.........│
 
│.........│
""" Make a printable string from a matrix of zeros and ones using a char ch for 1, a period for !=1. """
│.Q.......│
function smatrix(x, n, ch)
│.....Q...│
s = ""
│.........│
for i in 1:n, j in 1:n
│.........│
s *= lpad(x[i, j] == 1 ? "$ch" : ".", 2) * (j == n ? "\n" : "")
└─────────┘
end
(":<'.Q'{~coords e. q),&.|:,:' Q: ',":#q=. place queen [(genboard 10)
return s
┌──────────┐ Q: 6
end
│Q.........│
 
│..Q.......│
""" N-queens minimum, oeis.org/A075458 """
│........Q.│
function queensminimum(N, char = "Q")
│..........│
if N < 4
│..........│
a = zeros(Int, N, N)
│...Q......│
a[N ÷ 2 + 1, N ÷ 2 + 1] = 1
│.........Q│
return 1, smatrix(a, N, char)
│..........│
end
│.....Q....│
model = Model(Cbc.Optimizer)
│..........│
@variable(model, x[1:N, 1:N], Bin)
└──────────┘
 
</lang>
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])
 
</syntaxhighlight> {{out}}
<pre>
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 . .
. . . . . . . . . .
 
</pre>
 
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="Nim">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()
</syntaxhighlight>
 
{{out}}
<pre>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)
</pre>
 
=={{header|Pascal}}==
==={{header|Free Pascal}}===
The first Q,B in the first row is only placed lmt..mid because of symmetry reasons.<br>
At bishops I used a trick that at max only one row is left free.
14 Queens takes 2 min @home ~2.5x faster than TIO.RUN
<lang pascal>program TestMinimalQueen;
<syntaxhighlight 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;
 
Line 471 ⟶ 1,025:
 
tPlayGround = array[tLimit,tLimit] of byte;
tCheckPG = array[0..2*KoorCOUNT] of tplayGround;
tpPlayGround = ^tPlayGround;
 
Line 479 ⟶ 1,033:
Qsol,BSol,KSol :tPlayGround;
pgIdx,minIdx : nativeInt;
jumpedOver : boolean;
 
procedure pG_Out(pSol:tpPlayGround;ConvChar : string;lmt: NativeInt);
Line 490 ⟶ 1,043:
Begin
for col := 0 to lmt do
write(ConvChar[1+pSol^[row,col]],' ');
writeln;
end;
Line 559 ⟶ 1,112:
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 pPG^pRow[row,col] = 0 then
EXIT(false);
end;
exit(true);
end;
Line 574 ⟶ 1,131:
i,col,t: NativeInt;
begin
t := pgIdx+1;
if pgIdx = minIDX then
if t = minIDX then
EXIT;
inc(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 := 0col todownto lmt0 do
begin
//copy last state
CPG[pgIdx]:=CPG[pgIdx-1];
pPG := @CPG[pgIdx];
if pPG^[row,col] <> 0 then
continue;
//set diagonals
 
RightAscDia(row,col,lmt);
LeftAscDia(row,col,lmt);
Line 594 ⟶ 1,158:
pPG^[i,col] := 1;
end;
//now set position of queen
pPG^[row,col] := 2;
 
Line 612 ⟶ 1,176:
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);
Line 624 ⟶ 1,192:
EXIT;
inc(pgIdx);
move(CPG[pgIdx-1],CPG[pgIdx],SizeOf(tPlayGround));
For col := 0 to lmt do
col := lmt;
if row = 0 then
col := col shr 1;
For col := col downto 0 do
begin
CPG[pgIdx]:=CPG[pgIdx-1];
pPG := @CPG[pgIdx];
if pPG^[row,col] <> 0 then
Line 650 ⟶ 1,221:
else
begin
//check same row
SetBishop(row,lmt);
//check next row
t := row+1;
if (t <= lmt) then
begin
SetBishop(t,lmt);
//left out max one row on field
if jumpedOver then
Begin
inc(t);
jumpedOver := false;
if t <= lmt then
SetBishop(t,lmt);
jumpedOver := true;
end;
end;
end;
move(CPG[pgIdx-1],CPG[pgIdx],SizeOf(tPlayGround));
end;
dec(pgIdx);
Line 684 ⟶ 1,247:
begin
pgIdx := 0;
minIdx := 2*(lmt+1);
jumpedOver := true;
setQueen(0,lmt);
write(minIDX:3);
Line 695 ⟶ 1,257:
begin
pgIdx := 0;
minIdx := 2*(lmt+1);
jumpedOver := true;
setBishop(0,lmt);
write(minIDX:3);
end;
writeln;
 
pG_Out(@Qsol,'_.Q',max-1);
writeln;
 
pG_Out(@Bsol,'_.B',max-1);
END.</lang>
</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
 
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 . Q . . . .
. . . . . . . . . .
. . . . . . . .Q . Q
. . . . . . . . . .
. .Q . Q . . . . . .
 
 
B. . . . . . . . . .
. . . .. B . . . . .
. . .B . . . B . . .
. . . .. B . . . . .
. . .B . . . B . . .
. B . . . . . . .B .
. . .. B . B . . . .
. . . .B . B . . . .
. . . .B . . . . B .
B. . . . B . . . . .
 
Real time: 425.740935 s CPU share: 99.0627 %< /pre>/@home AMD 5600G real 0m10,784s
</pre>
 
=={{header|Perl}}==
Shows how the latest release of Perl can now use booleans.
{{trans|Raku}}
<syntaxhighlight lang="perl">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
}
}
}</syntaxhighlight>
{{out}}
<pre>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 . .
. . . . . . . . . .</pre>
 
=={{header|Phix}}==
{{libheader|Phix/pGUI}}
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/minqbn.htm here], with cheat mode on so it should all be done in 22s (8.3 on the desktop).
You can run this online [http://phix.x10.mx/p2js/minqbn.htm here], and explore the finished (green) ones while it toils away on the tougher ones, or watch it working. It examines 70,736,031 positions before solving B10, and 26,022,100 for N10, plus doing things in 0.4s chunks on a timer probably don't help, so it ends up taking just over 12 mins to completely finish on the desktop, and probably a fair bit longer than that in a web browser, but at least you can pause, resume, or quit it at any point.
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.
<!--<lang Phix>(phixonline)-->
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\minQBN.exw
Line 746 ⟶ 1,503:
--</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">include</span> <span style="color: #000000;">pGUI</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">title</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"Minimum QBN"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">help_text</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
Finds the minimum number of Queens, Bishops, andor Knights that can be placed on an NxN board
such that no piece attacks another but every unoccupied square is attacked.
Line 755 ⟶ 1,513:
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 maniacalmaniaical
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.
"""</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">maxq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- 1.0s (13 is 3minutes 58s, with maxn=1)</span>
<span style="color: #000000;">maxb</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- 1s (100 is 10s, with maxq=1 and maxn=1)</span>
<span style="color: #000000;">maxn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- 1mins 10s (9: 11.8s, 8: 8.1s, with maxq=1)</span>
<span style="color: #000000;">maxqbn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">({</span><span style="color: #000000;">maxq</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxn</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">cheat</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> <span style="color: #000080;font-style:italic;">-- eg find 16N on a 10x10 w/o disproving 15N first.
-- the total time drops to 8.3s (21.9s under p2js).</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">board</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">qmbm</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">01</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">01</span><span style="color: #0000FF;">,-+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span>
<span style="color: #000000;">bm</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span>
<span style="color: #000000;">rm</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span>
<span style="color: #000000;">qm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rm</span><span style="color: #0000FF;">&</span><span style="color: #000000;">bm</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">nm</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}}</span>
Line 772 ⟶ 1,538:
<span style="color: #008080;">function</span> <span style="color: #000000;">get_mm</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">piece</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">switch</span> <span style="color: #000000;">piece</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">case</span> <span style="color: #008000;">'Q'</span><span style="color: #0000FF;">:</span> <span style="color: #008080;">return</span> <span style="color: #000000;">qm</span><span style="color: #0000FF;">&</span><span style="color: #000000;">bm</span>
<span style="color: #008080;">case</span> <span style="color: #008000;">'B'</span><span style="color: #0000FF;">:</span> <span style="color: #008080;">return</span> <span style="color: #000000;">bm</span>
<span style="color: #008080;">case</span> <span style="color: #008000;">'N'</span><span style="color: #0000FF;">:</span> <span style="color: #008080;">return</span> <span style="color: #000000;">nm</span>
Line 809 ⟶ 1,575:
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mm</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">my</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mm</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">my</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' 0'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">my</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080004080;">ifinteger</span> <span style="color: #000000;">rowm</span> <span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #0080807060A8;">and</span> <span style="color: #000000;">colceil</span><span style="color: #0000FF;">=(</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">piece2</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'B'</span> <span style="color: #008080;">then)</span>
<span style="color: #008080;">if</span> <span style="color: #000080000000;font-">piece</span><span style="color:italic #0000FF;">--=</span><span firststyle="color: bishop#008000;">'B'</span> must be<span on the diagonalstyle="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- As pointed out on the talk page, *every*
-- if we don't find an answer up to the
-- mid-point,valid webishop won'tsolution findcan onebe after.</span>transformed
-- into all in column m so search only that</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- sanity check</span>
<span style="color: #000000008080;">res</span> <span style="color: #0000FF;">=for</span> <span style="color: #000000;">resi</span><span style="color: #0000FF;">[=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #7060A8008080;">ceilto</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF008080;">)]do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">m</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">piece</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'Q'</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- first queen on first half of top row
-- or first half of diagonal (not cols)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">3</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">m</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">piece</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'N'</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- first knight, was occupy+2, but by
-- symmetry we only need it to be 1+1</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- this cheeky little fella cuts more than half off the
-- last phase of 10N... (a circumstantial optimisation)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
Line 829 ⟶ 1,616:
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mm</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">my</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mm</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">my</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #008000000000;">'+'1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
Line 836 ⟶ 1,623:
<span style="color: #004080;">cdCanvas</span> <span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdcanvas</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">QBNSQBN</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8008000;">utf8_to_utf32" QBN"</span><span style="color: #0000FF;">(,</span> <span style="color: #008000000080;font-style:italic;">"♕♗♘"</span><span-- (or style="color: #0000FF;RBN">)</span>
<span style="color: #000000;">QBNU</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">utf8_to_utf32</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"♕♗♘"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">bn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- chosen board is nxn (1..10)</span>
Line 842 ⟶ 1,630:
<span style="color: #004080;">sequence</span> <span style="color: #000000;">state</span>
<span style="color: #000080;font-style:italic;">-- eg go straight for 16N on 10x10, avoid disproving 15N (from OEIS)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">cheats</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">,</span><span style="color: #000000;">24</span><span style="color: #0000FF;">,</span><span style="color: #000000;">29</span><span style="color: #0000FF;">,</span><span style="color: #000000;">33</span><span style="color: #0000FF;">}}</span>
<span style="color: #000080;font-style:italic;">-- 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</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">reset</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">state</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10maxq</span><span style="color: #0000FF;">),</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #0000007060A8;">piecerepeat</span><span style="color: #0000FF;">=(</span><span style="color: #000000;">10</span> <span style="color: #0080800000FF;">to,</span> <span style="color: #000000;">3maxb</span> <span style="color: #0080800000FF;">do),</span>
<span style="color: #008080;">for</span> <span style="color: #0000007060A8;">nrepeat</span><span style="color: #0000FF;">=(</span><span style="color: #000000;">10</span> <span style="color: #0080800000FF;">to,</span> <span style="color: #000000;">10maxn</span> <span style="color: #0080800000FF;">do)}</span>
<span style="color: #000080;font-style:italic;">-- (in case the maxq/b/n settings altered:)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">bn</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cp</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span> <span style="color: #000000;">bn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">piece</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">SQBN</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">scolour</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">CD_RED</span>
<span style="color: #000080;font-style:italic;">-- integer m = 1</span>
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequenceinteger</span> <span style="color: #000000;">movesm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000008080;">get_movesiff</span><span style="color: #0000FF;">(</span><span style="color: #008000000000;">"QBN"cheat</span><span style="color: #0000FF;">[?</span><span style="color: #000000;">piececheats</span><span style="color: #0000FF;">],[</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,][</span><span style="color: #000000;">1n</span><span style="color: #0000FF;">,]:</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_moves</span><span style="color: #0000FF;">(</span><span style="color: #000000;">piece</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">undo</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">piecep</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">scolour</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1m</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">undo</span><span style="color: #0000FF;">},</span><span style="color: #008000000000;">""undo</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
Line 860 ⟶ 1,663:
<span style="color: #000080;font-style:italic;">-- find something not yet done</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">ndx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10maxqbn</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">pdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">statendx</span><span style="color: #0000FF;">[<=</span><span style="color: #0000007060A8;">pdxlength</span><span style="color: #0000FF;">][(</span><span style="color: #000000;">ndxstate</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1pdx</span><span style="color: #0000FF;">]!=</span><span style="color: #004600;">CD_DARK_GREEN</span> <span style="color: #008080;">then)</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pdx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ndx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #004600;">CD_DARK_GREEN</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pdx</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ndx</span>
Line 871 ⟶ 1,675:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?{</span><span style="color: #008000;">"solved"</span><span style="color: #0000FF;">,(</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">))}</span>
<span style="color: #7060A8;">IupSetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">timer</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"RUN"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
Line 879 ⟶ 1,684:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">0.04</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">scolour</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">piece</span> <span style="color: #0000FF;">=</span> <span style="color: #008000000000;">"QBN"SQBN</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">undo</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">answer</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">scolour</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">,</span><span style="color: #000000;">undo</span><span style="color: #0000FF;">,</span><span style="color: #000000;">answer</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
Line 898 ⟶ 1,703:
<span style="color: #008080;">for</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">row</span><span style="color: #0000FF;">][</span><span style="color: #000000;">col</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' 0'</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">m</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">&=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">get_moves</span><span style="color: #0000FF;">(</span><span style="color: #000000;">piece</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">row</span><span style="color: #0000FF;">,</span><span style="color: #000000;">col</span><span style="color: #0000FF;">)}</span>
Line 927 ⟶ 1,732:
<span style="color: #000000;">m</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' 0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">get_moves</span><span style="color: #0000FF;">(</span><span style="color: #000000;">piece</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)}</span>
<span style="color: #000000;">undo</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)}</span>
Line 939 ⟶ 1,744:
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupGetIntInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"DRAWSIZE"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">/</span><span style="color: #000000;">40</span> <span style="color: #000080;font-style:italic;">-- legend fifth</span>
<span style="color: #000000;">dy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">/(</span><span style="color: #000000;">11maxqbn</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- legend delta</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">ly</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">-</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- legend top</span>
<span style="color: #000000;">cx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- board centre</span>
Line 950 ⟶ 1,755:
<span style="color: #004080;">atom</span> <span style="color: #000000;">fontsize</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">ceil</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">/</span><span style="color: #000000;">6</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">ceil</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">cdCanvasFont</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Helvetica"</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">CD_PLAIN</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fontsize</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10maxqbn</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">lx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">*</span><span style="color: #000000;">36</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #004080008080;">stringif</span> <span style="color: #000000;">txtj</span> <span style="color: #0000FF;">=</span> <span style="color: #008080000000;">iff0</span><span style="color: #0000FF;">(</span><span style="color: #000000008080;">ior</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0i</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" QBN"</span><span style="color: #0000FF7060A8;">[</span><span style="color: #000000;">jlength</span><span style="color: #0000FF;">+(</span><span style="color: #000000;">1state</span><span style="color: #0000FF;">..[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+])</span><span style="color: #000000;">1</span><span style="color: #0000FF008080;">]:then</span>
<span style="color: #7060A8004080;">sprintfstring</span> <span style="color: #0000FF000000;">(txt</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ji</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #000000;">iSQBN</span><span style="color: #0000FF;">:[</span><span style="color: #000000;">statej</span><span style="color: #0000FF;">[+</span><span style="color: #000000;">j1</span><span style="color: #0000FF;">][..</span><span style="color: #000000;">ij</span><span style="color: #0000FF;">][+</span><span style="color: #000000;">21</span><span style="color: #0000FF;">]))):</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">colour</span> <span style="color: #0000FF;">=</span> <span style="color: #0080807060A8;">iffsprintf</span><span style="color: #0000FF;">(</span><span style="color: #000000008000;">i"%d"</span><span style="color: #0000FF;">==,</span><span style="color: #000000008080;">0iff</span> <span style="color: #0080800000FF;">or(</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">==</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #004600000000;">CD_BLACKi</span><span style="color: #0000FF;">:</span><span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">12</span><span style="color: #0000FF;">])))</span>
<span style="color: #7060A8004080;">cdCanvasSetForegroundatom</span> <span style="color: #000000;">colour</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbufferi</span><span style="color: #0000FF;">,==</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">colourj</span><span style="color: #0000FF;">==</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #004600;">CD_BLACK</span><span style="color: #0000FF;">:</span><span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #7060A8;">cdCanvasText</span><span style="color: #0000FF;">(</span><span style="color: #0000007060A8;">cddbuffercdCanvasSetForeground</span><span style="color: #0000FF;">,(</span><span style="color: #000000;">lxcddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">txtcolour</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasText</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">txt</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">lx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">dx</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
Line 973 ⟶ 1,780:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">cdCanvasRect</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">bs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">bs</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">piece_text</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">utf32_to_utf8</span><span style="color: #0000FF;">({</span><span style="color: #000000;">QBNQBNU</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cp</span><span style="color: #0000FF;">]})</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">piece</span> <span style="color: #0000FF;">=</span> <span style="color: #008000000000;">"QBN"SQBN</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cp</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_mm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">piece</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">st</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cp</span><span style="color: #0000FF;">][</span><span style="color: #000000;">bn</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">solved</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">st</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #004600;">CD_DARK_GREEN</span>
<span style="color: #000080;font-style:italic;">-- show the solution/mt or undo[$] aka maniaical workings</span>
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solved</span><span style="color: #0000FF;">?</span><span style="color: #000000;">st</span><span style="color: #0000FF;">[</span><span style="color: #000000;">5</span><span style="color: #0000FF;">]:</span><span style="color: #000000;">st</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">][$]),</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solved</span> <span style="color: #008080;">or</span> <span style="color: #000000;">st</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]={}?</span><span style="color: #000000;">st</span><span style="color: #0000FF;">[</span><span style="color: #000000;">5</span><span style="color: #0000FF;">]:</span><span style="color: #000000;">st</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">][$]),</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">bn</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">bn</span> <span style="color: #008080;">do</span>
Line 993 ⟶ 1,801:
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mnm</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">my</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mnm</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8004080;">cdCanvasTextstring</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbufferac</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ss</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">mxboard</span><span style="color: #0000FF;">-[</span><span style="color: #000000;">colmy</span><span style="color: #0000FF;">),</span><span style="color: #000000;">symx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ss</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">my</span><span style="color: #0000FF;">-</span><span style="color: #000000;">row</span><span style="color: #0000FF;">),]&</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasText</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ss</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">col</span><span style="color: #0000FF;">),</span><span style="color: #000000;">sy</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ss</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">my</span><span style="color: #0000FF;">-</span><span style="color: #000000;">row</span><span style="color: #0000FF;">),</span><span style="color: #000000;">ac</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 1,017 ⟶ 1,826:
<span style="color: #008080;">function</span> <span style="color: #000000;">help</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">IupMessage</span><span style="color: #0000FF;">(</span><span style="color: #000000;">title</span><span style="color: #0000FF;">,</span><span style="color: #000000;">help_text</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_DEFAULTIUP_IGNORE</span> <span style="color: #000080;font-style:italic;">-- (don't open browser help!)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
Line 1,025 ⟶ 1,834:
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_CLOSE</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #008000004600;">' 'K_F5</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">IUP_DEFAULT</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (let browser reload work)</span>
<span style="color: #7060A8;">IupSetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">timer</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"RUN"</span><span style="color: #0000FF;">,</span><span style="color: #008080;">not</span> <span style="color: #7060A8;">IupGetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">timer</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"RUN"</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #004600;">K_F1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">help</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">upper</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">),</span><span style="color: #000000;">SQBN</span><span style="color: #0000FF;">&</span><span style="color: #008000;">"QBN123456789T123456789T+-!"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">31</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">IupSetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">timer</span><span style="color: #0000000000FF;">cp,</span><span style="color: #008000;">"RUN"</span><span style="color: #0000FF;">,</span><span style="color: #008080;">not</span> <span style="color: #7060A8;">IupGetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ktimer</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"RUN"</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">134</span> <span style="color: #008080;">then</span> <span style="color: #000000;">bncp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">31</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">ck</span><span style="color: #0000FF;"><=</span><span style="color: #008000000000;">'+'14</span> <span style="color: #008080;">then</span> <span style="color: #000000;">bn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bnk</span><span style="color: #0000FF;">+-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)4</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'+'</span> <span style="color: #008080;">then</span> <span style="color: #000000;">bn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bn</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxqbn</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'-'</span> <span style="color: #008080;">then</span> <span style="color: #000000;">bn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bn</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">bn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bn</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cp</span><span style="color: #0000FF;">]))</span>
<span style="color: #7060A8;">IupUpdate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 1,045 ⟶ 1,854:
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">36</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">/</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">01</span> <span style="color: #008080;">and</span> <span style="color: #000000;">p</span><span style="color: #0000FF;"><</span><span style="color: #000000;">4</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n3</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">cp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bn</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span>
<span style="color: #7060A8;">IupUpdate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span>
Line 1,080 ⟶ 1,890:
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</langsyntaxhighlight>-->
 
=={{header|Python}}==
{{trans|Julia}}
<syntaxhighlight 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()
</syntaxhighlight>{{out}}
<pre>
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 . .
. . . . . . . . . .
</pre>
 
=={{header|Raku}}==
Due to the time it's taking only a subset of the task are attempted.
{{trans|Go}}
<syntaxhighlight lang="raku" line># 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
}
}
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
=={{header|Wren}}==
===CLI===
{{libheader|Wren-fmt}}
This was originally based on the Java code [https://www.geeksforgeeks.org/minimum-queens-required-to-cover-all-the-squares-of-a-chess-board/ 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 [https://www.geeksforgeeks.org/n-queen-problem-using-branch-and-bound/ here] and have now incorporated the improvements made to the Go version.
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).
 
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.
It's based on the Java code [https://www.geeksforgeeks.org/minimum-queens-required-to-cover-all-the-squares-of-a-chess-board/ 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 [https://www.geeksforgeeks.org/n-queen-problem-using-branch-and-bound/ here].
<langsyntaxhighlight ecmascriptlang="wren">import "./fmt" for Fmt
 
var board
Line 1,097 ⟶ 2,241:
var minCount
var layout
 
var isAttacked = Fn.new { |piece, row, col|
if (piece == "Q") {
Line 1,106 ⟶ 2,250:
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
Line 1,121 ⟶ 2,264:
}
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)
}
}
 
Line 1,133 ⟶ 2,288:
 
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
}
Line 1,150 ⟶ 2,309:
return
}
forif (icountSoFar in<= 0...nmaxCount) {
forvar si = (jpiece in== 0"K") ? (ti-2)...nmax(0) {: ti
var sj if= (!isAttacked.call(piece, i,== j"K") ? (tj-2).max(0) : {tj
for (i in si...n) board[i][j] = true{
for diag1Lookup[diag1[i][(j]] =in truesj...n) {
diag2Lookup[diag2[if (!isAttacked.call(piece, i][j]], =j)) true{
placePiece if ((i == ti && j == tj) || attacks.call(piece, countSoFari, +j, 1ti, tj)) {
board[i][j] = falsetrue
diag1Lookup[diag1[i][j]] if (piece != false"K") {
diag2Lookup diag1Lookup[diag2diag1[i][j]] = falsetrue
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
}
}
}
}
}
Line 1,165 ⟶ 2,334:
}
 
var start = System.clock
var pieces = ["Q", "B", "K"]
var limits = {"Q": 10, "B": 610, "K": 510}
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"}
for (piece in pieces) {
Line 1,175 ⟶ 2,345:
board = List.filled(n, null)
for (i in 0...n) board[i] = List.filled(n, false)
diag1if = List.filled(n,piece null!= "K") {
for (i in 0.. diag1 = List.filled(n), {null)
diag1[for (i] =in List0...filled(n, 0) {
for (j in 0...n) diag1[i][j] = iList.filled(n, + j0)
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)
}
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.callfor (piece,maxCount 0in 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]) {
Line 1,198 ⟶ 2,373:
n = n + 1
}
}
}</lang>
System.print("Took %(System.clock - start) seconds.")</syntaxhighlight>
 
{{out}}
Line 1,238 ⟶ 2,414:
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 610 x 610 board:
 
B. . . B. . . . . . B
. . . B. . . . . . .
. . . B . B . . . .
. . . B . B . B . .
B . . B. B. . . . . .
. . . . . . . . . .
. . . . . B . . . .
. . . . . B . . . .
. . . . . B . . . .
. . . . . . . . . .
 
Knights
Line 1,256 ⟶ 2,440:
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 510 x 510 board:
 
K. . . . . . . . . .
. . K K . . . . . .
. . K K . . . K K .
. . . . . . . K K .
. . . . . . . . . .
. . . . . . . . . .
. K K . . . . . . .
. K K . . . K K . .
. . . . . . K K . .
. . . . . . . . . .
 
Took 1276.522608 seconds.
</pre>
 
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:
===Embedded===
{{libheader|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.
<syntaxhighlight lang="wren">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.")</syntaxhighlight>
 
{{out}}
<pre>
Queens on a 8 x 8 board:
=======
 
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.
Q . . . . . . .
. . Q . . . . .
. . . . Q . . .
. Q . . . . . .
. . . Q . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
</pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/320625...355563"