N-queens minimum and knights and bishops: Difference between revisions
m (formatting) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
(29 intermediate revisions by 11 users not shown) | |||
Line 5: | 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. |
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#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// |
// Minimum knights to attack all squares not occupied on an NxN chess board. Nigel Galloway: May 12th., 2022 |
||
type att={n:uint64; g:uint64} |
|||
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=[n-g-g-1;n-g-g+1;n-g+2;n-g-2;n+g+g-1;n+g+g+1;n+g-2;n+g+2]|>List.filter(fun x->0<=x && x<g*g && abs(x%g-n%g)+abs(x/g-n/g)=3)|>List.distinct|>List.map(fun n->n/2) |
|||
let n,g=Array.init(g*g)(fun n->att.att [n/2] (fG n g)), Array.init(g*g)(fun n->att.att (fG n g) [n/2]) in (fun g->n.[g]),(fun n->g.[n]) |
|||
type cand={att:att; n:int; g:int} |
|||
type Solver={n:cand seq; i:int[]; g:(int -> att) * (int -> att); e:att; l:int[]} |
|||
member this.test()=let rec test n i g e l=match g with 0UL->(if i=this.e then Some(n,e) else None)|g when g%2UL=1UL->test n (i+((snd this.g)(this.i.[l])))(g/2UL)(e+1)(l+1) |_->test n i (g/2UL) e (l+1) |
|||
let n=this.n|>Seq.choose(fun n->test n n.att (this.e.g^^^n.att.g) 0 0) in if Seq.isEmpty n then None else Some(n|>Seq.minBy snd) |
|||
member this.xP() ={this with n=this.n|>Seq.collect(fun n->[for g in n.n..n.g do let att=n.att+((fst this.g)(this.l.[g])) in yield {n with att=att; n=g}])} |
|||
let rec slvK (n:Solver) i g l = match n.test() with Some(r,ta)->match min l (g+ta) with t when t>2*(g+1) || l<t->slvK (n.xP()) (if t<l then Some(r,ta) else i) (g+1) (min t l) |t->Some(min t l,r) |
|||
|_->slvK (n.xP()) i (g+1) l |
|||
let tC bw s (att:att)=let n=Array2D.init s s (fun n g->if (n+g)%2=bw then (if att.n &&& pown 2UL ((n*s+g)/2) > 0UL then "X" else ".") else (if att.g &&& pown 2UL ((n*s+g)/2) > 0UL then "~" else "o")) |
|||
for g in 0..s-1 do n.[g,0..s-1]|>Seq.iter(fun g->printf "%s" g); printfn "" |
|||
let solveK g=printfn "\nSolving for %dx%d board" g g |
|||
let bs,ws=[|for n in g..g+g..(g*g-1)/2 do for z in 0..g+1..(g*g-1)/2-n->((n+z)/g,(n+z)%g)|],[|for n in 0..g+g..(g*g-1)/2 do for z in 0..g+1..(g*g-1)/2-n->((n+z)/g,(n+z)%g)|] |
|||
let i,l=let n,i=[|for n in 0..g-1 do for g in 0..g-1->(n,g)|]|>Array.partition(fun(n,g)->(n+g)%2=1) in n|>Array.map(fun(n,i)->n*g+i), i|>Array.map(fun(n,i)->n*g+i) |
|||
let t,f=System.DateTime.UtcNow,fN g |
|||
let bK={l=Array.concat[bs|>Array.map(fun(n,i)->n*g+i);i]|>Array.distinct; i=l; e=att.att [0..i.Length-1] [0..l.Length-1]; n=bs|>Array.mapi(fun l (n,e)->let att=((fst f)(n*g+e)) in {att=att; n=l+1; g=i.Length-1}); g=fN g} |
|||
let wK={l=Array.concat[ws|>Array.map(fun(n,i)->n*g+i);l]|>Array.distinct; i=i; e=att.att [0..l.Length-1] [0..i.Length-1]; n=ws|>Array.mapi(fun i (n,e)->let att=((fst f)(n*g+e)) in {att=att; n=i+1; g=l.Length-1}); g=fN g} |
|||
let (rn,rb),tc=match g with 1|2->(slvK wK None 1 (g*g/2+g%2)).Value, tC 0 g |
|||
|x when x%2=0->(slvK bK None 1 (g*g/2)).Value, tC 1 g |
|||
|_->let x,y=(slvK bK None 1 (g*g/2)).Value, (slvK wK None 1 (g*g/2+1)).Value in if (fst x)<(fst y) then x,tC 1 g else y,tC 0 g |
|||
printfn "Solution found using %d knights in %A:" rn (System.DateTime.UtcNow-t); tc rb.att |
|||
for n in 1..10 do solveK n |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Solving for 1x1 board |
|||
Solution found using 1 knights in 00:00:00.0331768: |
|||
X |
|||
Solving for 2x2 board |
|||
let fN n g l=([0..n-1]@[n+1..l-1]|>List.map(fun n->sprintf "N_%02d_%02d" n g))@([0..g-1]@[g+1..l-1]|>List.map(fun g->sprintf "N_%02d_%02d" n g)) |
|||
Solution found using 2 knights in 00:00:00: |
|||
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)@ |
|||
Xo |
|||
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)@ |
|||
oX |
|||
List.unfold(fun(n,g)->if n<1||g<1 then None else let n,g=n-1,g-1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)@ |
|||
List.unfold(fun(n,g)->if n>l-2||g<1 then None else let n,g=n+1,g-1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g) |
|||
let fK n g l=[(1,-2);(2,-1);(1,2);(2,1);(-1,2);(-2,1);(-1,-2);(-2,-1)]|>List.choose(fun(x,y)->match n+x,g+y with p,q when p>=0 && q>=0 && p<=l-1 && q<=l-1->Some(sprintf "N_%02d_%02d" p q) |_->None) |
|||
let sln f size= |
|||
let context=SolverContext.GetContext() |
|||
context.ClearModel() |
|||
let model=context.CreateModel() |
|||
for n in 0..size-1 do for g in 0..size-1 do model.AddDecision(new Decision(Domain.IntegerRange(Rational.Zero,Rational.One), sprintf "N_%02d_%02d" n g)) |
|||
for n in 0..size-1 do for g in 0..size-1 do model.AddConstraint(sprintf "G_%02d_%02d" n g,([sprintf "0<%d*N_%02d_%02d" (size*size) n g]@f n g size|>String.concat "+")+sprintf "<%d" (size*size+1)) |
|||
model.AddGoal("Goal0", GoalKind.Minimize, [for n in 0..size-1 do for g in 0..size-1->sprintf "N_%02d_%02d" n g]|>String.concat "+") |
|||
context.Solve() |
|||
let Bishops,Queens,Knights=sln fG, sln (fun n g l->fG n g l@fN n g l), sln fK |
|||
let printSol(n:Solution)=n.Decisions|>Seq.filter(fun n->n.GetDouble()=1.0)|>Seq.iteri(fun n g->let g=g.Name in printfn "Place Piece %d in row %d column %d" (n+1) (int(g.[2..3])) (int(g.[5..6]))); printfn "" |
|||
let pieces(n:Solution)=n.Decisions|>Seq.filter(fun n->n.GetDouble()=1.0)|>Seq.length |
|||
Solving for 3x3 board |
|||
printfn "%10s%10s%10s%10s" "Squares" "Queens" "Bishops" "Knights" |
|||
Solution found using 4 knights in 00:00:00.0156191: |
|||
[1..10]|>List.iter(fun n->printfn "%10d%10d%10d%10d" (n*n) (pieces(Queens n)) (pieces(Bishops n)) (pieces(Knights n))) |
|||
Xo. |
|||
printfn "Queens on a 8x8 Board"; printSol(Queens 8) |
|||
oX~ |
|||
printfn "Knights on a 8x8 Board"; printSol(Knights 8) |
|||
.~. |
|||
</lang> |
|||
{{out}} |
|||
Solving for 4x4 board |
|||
<pre> |
|||
Solution found using 4 knights in 00:00:00: |
|||
Squares Queens Bishops Knights |
|||
~.~. |
|||
1 1 1 1 |
|||
XoXo |
|||
4 1 2 4 |
|||
~.~. |
|||
9 1 3 4 |
|||
.~.~ |
|||
16 3 4 4 |
|||
25 3 5 5 |
|||
Solving for 5x5 board |
|||
36 4 6 8 |
|||
Solution found using 5 knights in 00:00:00: |
|||
49 4 7 13 |
|||
.o.~. |
|||
64 5 8 14 |
|||
~X~.~ |
|||
81 5 9 14 |
|||
.o.~. |
|||
100 5 10 16 |
|||
~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> |
</pre> |
||
=={{header|Go}}== |
=={{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. |
|||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 83: | Line 137: | ||
"math" |
"math" |
||
"strings" |
"strings" |
||
"time" |
|||
) |
) |
||
Line 102: | Line 157: | ||
} |
} |
||
} else if piece == "B" { |
} else if piece == "B" { |
||
if board[row][col] { |
|||
return true |
|||
} |
|||
if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] { |
if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] { |
||
return true |
return true |
||
Line 138: | Line 190: | ||
} |
} |
||
return false |
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: | Line 226: | ||
} |
} |
||
func placePiece(piece string, countSoFar int) { |
func placePiece(piece string, countSoFar, maxCount int) { |
||
if countSoFar >= minCount { |
if countSoFar >= minCount { |
||
return |
return |
||
} |
} |
||
allAttacked := true |
allAttacked := true |
||
ti := 0 |
|||
tj := 0 |
|||
for i := 0; i < n; i++ { |
for i := 0; i < n; i++ { |
||
for j := 0; j < n; j++ { |
for j := 0; j < n; j++ { |
||
if !isAttacked(piece, i, j) { |
if !isAttacked(piece, i, j) { |
||
allAttacked = false |
allAttacked = false |
||
ti = i |
|||
tj = j |
|||
break |
break |
||
} |
} |
||
Line 176: | Line 251: | ||
return |
return |
||
} |
} |
||
if countSoFar <= maxCount { |
|||
si := ti |
|||
sj := tj |
|||
if piece == "K" { |
|||
si = si - 2 |
|||
sj = sj - 2 |
|||
if si < 0 { |
|||
si = 0 |
|||
} |
|||
if sj < 0 { |
|||
sj = 0 |
|||
} |
|||
} |
|||
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: | Line 287: | ||
func main() { |
func main() { |
||
start := time.Now() |
|||
pieces := []string{"Q", "B", "K"} |
pieces := []string{"Q", "B", "K"} |
||
limits := map[string]int{"Q": 10, "B": |
limits := map[string]int{"Q": 10, "B": 10, "K": 10} |
||
names := map[string]string{"Q": "Queens", "B": "Bishops", "K": "Knights"} |
names := map[string]string{"Q": "Queens", "B": "Bishops", "K": "Knights"} |
||
for _, piece := range pieces { |
for _, piece := range pieces { |
||
Line 205: | Line 300: | ||
board[i] = make([]bool, n) |
board[i] = make([]bool, n) |
||
} |
} |
||
if piece != "K" { |
|||
diag1 = make([][]int, n) |
|||
for i := 0; i < n; i++ { |
|||
diag1[i] = make([]int, n) |
|||
for j := 0; j < n; j++ { |
|||
diag1[i][j] = i + j |
|||
} |
|||
} |
} |
||
diag2 = make([][]int, n) |
|||
for i := 0; i < n; i++ { |
|||
diag2[i] = make([]int, n) |
|||
for j := 0; j < n; j++ { |
|||
diag2[i][j] = i - j + n - 1 |
|||
} |
|||
} |
} |
||
diag1Lookup = make([]bool, 2*n-1) |
|||
diag2Lookup = make([]bool, 2*n-1) |
|||
} |
} |
||
diag1Lookup = make([]bool, 2*n-1) |
|||
diag2Lookup = make([]bool, 2*n-1) |
|||
minCount = math.MaxInt32 |
minCount = math.MaxInt32 |
||
layout = "" |
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) |
fmt.Printf("%2d x %-2d : %d\n", n, n, minCount) |
||
if n == limits[piece] { |
if n == limits[piece] { |
||
Line 232: | Line 334: | ||
} |
} |
||
} |
} |
||
elapsed := time.Now().Sub(start) |
|||
}</lang> |
|||
fmt.Printf("Took %s\n", elapsed) |
|||
}</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
Line 273: | Line 377: | ||
6 x 6 : 6 |
6 x 6 : 6 |
||
7 x 7 : 7 |
7 x 7 : 7 |
||
8 x 8 : 8 |
|||
9 x 9 : 9 |
|||
10 x 10 : 10 |
|||
Bishops on a |
Bishops on a 10 x 10 board: |
||
. |
. . . . . . . . . B |
||
. . . |
. . . . . . . . . . |
||
. . . . . . . |
. . . B . B . . . . |
||
. . B B . . . |
. . . B . B . B . . |
||
. . . . . . . |
B . . . . . . . . . |
||
. . |
. . . . . . . . . . |
||
. . . . . . . |
. . . . . B . . . . |
||
. . . . . B . . . . |
|||
. . . . . B . . . . |
|||
. . . . . . . . . . |
|||
Knights |
Knights |
||
Line 292: | Line 402: | ||
4 x 4 : 4 |
4 x 4 : 4 |
||
5 x 5 : 5 |
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 |
Knights on a 10 x 10 board: |
||
. . . . . . . . . . |
|||
. . . . . |
. . K K . . . . . . |
||
. . K K . |
. . K K . . . K K . |
||
. . K K . |
. . . . . . . K K . |
||
. . . . . |
. . . . . . . . . . |
||
. . . . . . . . . . |
|||
. K K . . . . . . . |
|||
. K K . . . K K . . |
|||
. . . . . . K K . . |
|||
. . . . . . . . . . |
|||
Took 22.383253365s |
|||
</pre> |
</pre> |
||
=={{header|J}}== |
=={{header|J}}== |
||
This is a crude attempt -- brute force search with some minor state space pruning. I am not patient enough to run this for boards larger than 7x7 for knights: |
|||
<syntaxhighlight lang="j"> |
|||
<lang J>genboard=: {{ |
|||
genboard=: {{ |
|||
safelen=:2*len=. {.y |
|||
safelen=:2*len=: {.y |
|||
shape=: 2$len |
shape=: 2$len |
||
board=: shape$0 |
board=: shape$0 |
||
safeshape=: |
safeshape=: ,~safelen |
||
c=:,coords=: safeshape#.shape#:i.shape |
c=:,coords=: safeshape#.shape#:i.shape |
||
qrow=. i:{.shape-1 |
qrow=. i:{.shape-1 |
||
Line 325: | Line 449: | ||
}} |
}} |
||
placebishops=: {{coords #&,~ 1 (<.-:len)} board}} |
|||
place=: {{ |
|||
N=. #r=. _#~#c |
|||
placequeens=: {{ |
|||
for_open.first do. |
|||
N=. 0 |
|||
board=. coords e.y+open |
|||
while. N=. N+1 do. |
|||
assert. N<:#c |
|||
seq=. open y place1 N board |
|||
for_seq. first do. |
|||
board=. coords e.queen+seq |
|||
if. 0 e.,board do. |
|||
if. 1<N do. |
|||
seq=. board queen place1 N seq |
|||
if. #seq do. |
|||
assert. N-:#seq |
|||
assert. */c e.,queen+/seq |
|||
seq return. |
|||
end. |
|||
end. |
|||
else. |
|||
seq return. |
|||
end. |
|||
end. |
end. |
||
end. |
end. |
||
EMPTY |
|||
}} |
}} |
||
placeknights=:{{ |
|||
N=. 0 |
|||
N=. |
while. N=. N+1 do. |
||
assert. N<:#c |
|||
for_seq. c do. |
|||
lim=. >./,(first +&{: x)+m |
|||
board=. coords e.knight+seq |
|||
for_open. (#~ lim>:]) todo do. |
|||
if. 0 e.,board do. |
|||
if. 1<N do. |
|||
seq=. board knight place1 N seq |
|||
if. #seq do. |
|||
assert. N-:#seq |
|||
assert. */c e.,knight+/seq |
|||
seq return. |
|||
end. |
|||
end. |
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. |
end. |
||
else. |
else. seq return. |
||
end. |
end. |
||
end. |
end. |
||
EMPTY |
|||
}} |
}} |
||
task=: {{ |
task=: {{ |
||
B=:Q=:K=:i.0 |
|||
for_order.1+i. |
for_order.1+i.y do. |
||
genboard order |
genboard order |
||
B=: 1j1#"1'.B'{~coords e.b=. placebishops '' |
|||
Q=: 1j1#"1'.Q'{~coords e.q=. placequeens '' |
|||
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. |
end. |
||
}}</ |
}}</syntaxhighlight> |
||
Task output: |
Task output: |
||
<syntaxhighlight lang="j"> task 10 |
|||
<lang J> |
|||
+--+--+--+ B: 1 |
|||
task'' |
|||
|B |Q |K | Q: 1 |
|||
┌─┬─┬─┐ Q: 1 |
|||
+--+--+--+ K: 1 |
|||
│Q│B│K│ B: 1 |
|||
+----+----+----+ B: 2 |
|||
└─┴─┴─┘ K: 1 |
|||
|. . |Q . |K K | Q: 1 |
|||
┌──┬──┬──┐ Q: 1 |
|||
|B B |. . |K K | K: 4 |
|||
│Q.│BB│KK│ B: 2 |
|||
+----+----+----+ |
|||
│..│..│KK│ K: 4 |
|||
+------+------+------+ B: 3 |
|||
└──┴──┴──┘ |
|||
|. . . |. . . |K K K | Q: 1 |
|||
┌───┬───┬───┐ Q: 1 |
|||
|B B B |. Q . |. K . | K: 4 |
|||
│...│...│KKK│ B: 3 |
|||
|. . . |. . . |. . . | |
|||
│.Q.│BBB│.K.│ K: 4 |
|||
+------+------+------+ |
|||
│...│...│...│ |
|||
+--------+--------+--------+ B: 4 |
|||
└───┴───┴───┘ |
|||
|. . . . |Q . . . |. K K . | Q: 3 |
|||
┌────┬────┬────┐ Q: 3 |
|||
|. . . . |. . Q . |. K K . | K: 4 |
|||
|B B B B |. . . . |. . . . | |
|||
│..Q.│BBBB│KKKK│ K: 4 |
|||
|. . . . |. Q . . |. . . . | |
|||
+--------+--------+--------+ |
|||
│.Q..│....│....│ |
|||
+----------+----------+----------+ B: 5 |
|||
└────┴────┴────┘ |
|||
|. . . . . |Q . . . . |K . . . . | Q: 3 |
|||
┌─────┬─────┬─────┐ Q: 3 |
|||
|. . . . . |. . . Q . |. . . . . | K: 5 |
|||
|B B B B B |. . . . . |. . K K . | |
|||
|. . . . . |. . Q . . |. . K K . | |
|||
|. . . . . |. . . . . |. . . . . | |
|||
+----------+----------+----------+ |
|||
│.....│.....│.....│ |
|||
+------------+------------+------------+ B: 6 |
|||
└─────┴─────┴─────┘ |
|||
|. . . . . . |Q . . . . . |K . . . . K | Q: 4 |
|||
┌──────┬──────┬──────┐ Q: 4 |
|||
|. . . . . . |. . Q . . . |. . . . . . | K: 8 |
|||
|. . . . . . |. . . . . Q |. . K K . . | |
|||
|B B B B B B |. . . . . . |. . K K . . | |
|||
|. . . . . . |. . . . . . |. . . . . . | |
|||
|. . . . . . |. Q . . . . |K . . . . K | |
|||
+------------+------------+------------+ |
|||
│.Q....│......│K....K│ |
|||
+--------------+--------------+--------------+ B: 7 |
|||
└──────┴──────┴──────┘ |
|||
|. . . . . . . |. . . . . . . |K K K K . K . | Q: 4 |
|||
┌───────┬───────┬───────┐ Q: 4 |
|||
|. . . . . . . |. Q . . . . . |. . . . . . . | K: 13 |
|||
|. . . . . . . |. . . . Q . . |. . . . . K . | |
|||
|B B B B B B B |. . . . . . . |K . . . . K . | |
|||
|. . . . . . . |. . . . . . . |. . . . . . . | |
|||
|. . . . . . . |Q . . . . . . |K . K K . K . | |
|||
|. . . . . . . |. . . Q . . . |. . . . . . K | |
|||
+--------------+--------------+--------------+ |
|||
│...Q...│.......│......K│ |
|||
+----------------+----------------+ B: 8 |
|||
└───────┴───────┴───────┘ |
|||
|. . . . . . . . |Q . . . . . . . | Q: 5 |
|||
┌────────┬────────┬────────┐ Q: 5 |
|||
|. . . . . . . . |. . Q . . . . . | |
|||
|. . . . . . . . |. . . . Q . . . | |
|||
|. . . . . . . . |. Q . . . . . . | |
|||
|B B B B B B B B |. . . Q . . . . | |
|||
│.Q......│....B...│K.......│ |
|||
|. . . . . . . . |. . . . . . . . | |
|||
|. . . . . . . . |. . . . . . . . | |
|||
|. . . . . . . . |. . . . . . . . | |
|||
+----------------+----------------+ |
|||
│........│........│.....K.K│ |
|||
+------------------+------------------+ B: 9 |
|||
└────────┴────────┴────────┘ |
|||
|. . . . . . . . . |Q . . . . . . . . | Q: 5 |
|||
|attention interrupt: place</lang> |
|||
|. . . . . . . . . |. . Q . . . . . . | |
|||
|. . . . . . . . . |. . . . . . Q . . | |
|||
For 9 and 10 for queens: |
|||
|. . . . . . . . . |. . . . . . . . . | |
|||
<lang J> (":<'.Q'{~coords e. q),&.|:,:' Q: ',":#q=. place queen [(genboard 9) |
|||
|B B B B B B B B B |. . . . . . . . . | |
|||
┌─────────┐ Q: 5 |
|||
|. . . . . . . . . |. Q . . . . . . . | |
|||
|. . . . . . . . . |. . . . . Q . . . | |
|||
|. . . . . . . . . |. . . . . . . . . | |
|||
|. . . . . . . . . |. . . . . . . . . | |
|||
+------------------+------------------+ |
|||
│.........│ |
|||
+--------------------+--------------------+ B: 10 |
|||
│.Q.......│ |
|||
|. . . . . . . . . . |Q . . . . . . . . . | Q: 6 |
|||
|. . . . . . . . . . |. . Q . . . . . . . | |
|||
|. . . . . . . . . . |. . . . . . . . Q . | |
|||
|. . . . . . . . . . |. . . . . . . . . . | |
|||
└─────────┘ |
|||
|. . . . . . . . . . |. . . . . . . . . . | |
|||
(":<'.Q'{~coords e. q),&.|:,:' Q: ',":#q=. place queen [(genboard 10) |
|||
|B B B B B B B B B B |. . . Q . . . . . . | |
|||
┌──────────┐ Q: 6 |
|||
|. . . . . . . . . . |. . . . . . . . . Q | |
|||
|. . . . . . . . . . |. . . . . . . . . . | |
|||
|. . . . . . . . . . |. . . . . Q . . . . | |
|||
|. . . . . . . . . . |. . . . . . . . . . | |
|||
+--------------------+--------------------+ |
|||
│..........│ |
|||
</syntaxhighlight> |
|||
│...Q......│ |
|||
│.........Q│ |
|||
│..........│ |
|||
│.....Q....│ |
|||
│..........│ |
|||
└──────────┘ |
|||
</lang> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Uses the |
Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support. |
||
< |
<syntaxhighlight lang="julia">""" Rosetta code task N-queens_minimum_and_knights_and_bishops """ |
||
import HiGHS |
|||
import Cbc |
import Cbc |
||
using JuMP |
using JuMP |
||
using LinearAlgebra |
using LinearAlgebra |
||
""" |
""" Make a printable string from a matrix of zeros and ones using a char ch for 1, a period for !=1. """ |
||
function smatrix(x, n, ch) |
function smatrix(x, n, ch) |
||
s = "" |
s = "" |
||
Line 482: | Line 634: | ||
return 1, smatrix(a, N, char) |
return 1, smatrix(a, N, char) |
||
end |
end |
||
model = Model( |
model = Model(Cbc.Optimizer) |
||
@variable(model, x[1:N, 1:N], Bin) |
@variable(model, x[1:N, 1:N], Bin) |
||
Line 512: | Line 664: | ||
N == 2 && return 2, "$char .\n$char .\n" |
N == 2 && return 2, "$char .\n$char .\n" |
||
model = Model( |
model = Model(Cbc.Optimizer) |
||
@variable(model, x[1:N, 1:N], Bin) |
@variable(model, x[1:N, 1:N], Bin) |
||
Line 573: | Line 725: | ||
"\nKnights:\n", examples[3]) |
"\nKnights:\n", examples[3]) |
||
</ |
</syntaxhighlight> {{out}} |
||
<pre> |
<pre> |
||
Squares Queens Bishops Knights |
Squares Queens Bishops Knights |
||
Line 586: | Line 738: | ||
81 5 9 14 |
81 5 9 14 |
||
100 5 10 16 |
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: |
Examples for N = 10: |
||
Line 626: | Line 778: | ||
. . . . . . . . . . |
. . . . . . . . . . |
||
</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> |
</pre> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
==={{header|Free 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} |
{$MODE DELPHI}{$OPTIMIZATION ON,ALL} |
||
uses |
uses |
||
sysutils; |
sysutils; |
||
type |
|||
tDeltaKoor = packed record |
|||
dRow, |
|||
dCol : Int8; |
|||
end; |
|||
const |
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; |
KoorCOUNT = 16; |
||
Line 643: | Line 1,025: | ||
tPlayGround = array[tLimit,tLimit] of byte; |
tPlayGround = array[tLimit,tLimit] of byte; |
||
tCheckPG = array[0..KoorCOUNT] of tplayGround; |
tCheckPG = array[0..2*KoorCOUNT] of tplayGround; |
||
tpPlayGround = ^tPlayGround; |
tpPlayGround = ^tPlayGround; |
||
Line 651: | Line 1,033: | ||
Qsol,BSol,KSol :tPlayGround; |
Qsol,BSol,KSol :tPlayGround; |
||
pgIdx,minIdx : nativeInt; |
pgIdx,minIdx : nativeInt; |
||
jumpedOver : boolean; |
|||
procedure pG_Out(pSol:tpPlayGround;ConvChar : string;lmt: NativeInt); |
procedure pG_Out(pSol:tpPlayGround;ConvChar : string;lmt: NativeInt); |
||
Line 662: | Line 1,043: | ||
Begin |
Begin |
||
for col := 0 to lmt do |
for col := 0 to lmt do |
||
write(ConvChar[1+pSol^[row,col]]); |
write(ConvChar[1+pSol^[row,col]],' '); |
||
writeln; |
writeln; |
||
end; |
end; |
||
Line 731: | Line 1,112: | ||
var |
var |
||
pPG :tpPlayGround; |
pPG :tpPlayGround; |
||
pRow : pByte; |
|||
row,col: NativeInt; |
row,col: NativeInt; |
||
Begin |
Begin |
||
pPG := @CPG[pgIdx]; |
pPG := @CPG[pgIdx]; |
||
For row := lmt downto 0 do |
For row := lmt downto 0 do |
||
begin |
|||
pRow := @pPG^[row,0]; |
|||
For col := lmt downto 0 do |
For col := lmt downto 0 do |
||
if |
if pRow[col] = 0 then |
||
EXIT(false); |
EXIT(false); |
||
end; |
|||
exit(true); |
exit(true); |
||
end; |
end; |
||
Line 746: | Line 1,131: | ||
i,col,t: NativeInt; |
i,col,t: NativeInt; |
||
begin |
begin |
||
t := pgIdx+1; |
|||
if pgIdx = minIDX then |
|||
if t = minIDX then |
|||
EXIT; |
EXIT; |
||
pgIdx:= t; |
|||
//use state before |
|||
// CPG[pgIdx]:=CPG[pgIdx-1]; |
|||
move(CPG[t-1],CPG[t],SizeOf(tPlayGround)); |
|||
col := lmt; |
|||
//first row only check one half -> symmetry |
|||
if row = 0 then |
|||
col := col shr 1; |
|||
//check every column |
//check every column |
||
For col := |
For col := col downto 0 do |
||
begin |
begin |
||
//copy last state |
|||
CPG[pgIdx]:=CPG[pgIdx-1]; |
|||
pPG := @CPG[pgIdx]; |
pPG := @CPG[pgIdx]; |
||
if pPG^[row,col] <> 0 then |
if pPG^[row,col] <> 0 then |
||
continue; |
continue; |
||
//set diagonals |
|||
RightAscDia(row,col,lmt); |
RightAscDia(row,col,lmt); |
||
LeftAscDia(row,col,lmt); |
LeftAscDia(row,col,lmt); |
||
Line 766: | Line 1,158: | ||
pPG^[i,col] := 1; |
pPG^[i,col] := 1; |
||
end; |
end; |
||
//set position of queen |
//now set position of queen |
||
pPG^[row,col] := 2; |
pPG^[row,col] := 2; |
||
Line 784: | Line 1,176: | ||
For t := row+1 to lmt do |
For t := row+1 to lmt do |
||
SetQueen(t,lmt); |
SetQueen(t,lmt); |
||
//copy last state |
|||
t := pgIdx; |
|||
move(CPG[t-1],CPG[t],SizeOf(tPlayGround)); |
|||
// CPG[pgIdx]:=CPG[pgIdx-1]; |
|||
end; |
end; |
||
dec(pgIdx); |
dec(pgIdx); |
||
Line 796: | Line 1,192: | ||
EXIT; |
EXIT; |
||
inc(pgIdx); |
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 |
begin |
||
CPG[pgIdx]:=CPG[pgIdx-1]; |
|||
pPG := @CPG[pgIdx]; |
pPG := @CPG[pgIdx]; |
||
if pPG^[row,col] <> 0 then |
if pPG^[row,col] <> 0 then |
||
Line 822: | Line 1,221: | ||
else |
else |
||
begin |
begin |
||
//check same row |
|||
SetBishop(row,lmt); |
|||
//check next row |
//check next row |
||
t := row+1; |
t := row+1; |
||
if (t <= lmt) then |
if (t <= lmt) then |
||
begin |
|||
SetBishop(t,lmt); |
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; |
end; |
||
move(CPG[pgIdx-1],CPG[pgIdx],SizeOf(tPlayGround)); |
|||
end; |
end; |
||
dec(pgIdx); |
dec(pgIdx); |
||
Line 856: | Line 1,247: | ||
begin |
begin |
||
pgIdx := 0; |
pgIdx := 0; |
||
minIdx := |
minIdx := lmt; |
||
jumpedOver := true; |
|||
setQueen(0,lmt); |
setQueen(0,lmt); |
||
write(minIDX:3); |
write(minIDX:3); |
||
Line 867: | Line 1,257: | ||
begin |
begin |
||
pgIdx := 0; |
pgIdx := 0; |
||
minIdx := 2* |
minIdx := 2*lmt+1; |
||
jumpedOver := true; |
|||
setBishop(0,lmt); |
setBishop(0,lmt); |
||
write(minIDX:3); |
write(minIDX:3); |
||
end; |
end; |
||
writeln; |
writeln; |
||
pG_Out(@Qsol,'_.Q',max-1); |
pG_Out(@Qsol,'_.Q',max-1); |
||
writeln; |
writeln; |
||
pG_Out(@Bsol,'_.B',max-1); |
pG_Out(@Bsol,'_.B',max-1); |
||
END. |
END. |
||
</syntaxhighlight> |
|||
{{out|@TIO.RUN}} |
{{out|@TIO.RUN}} |
||
<pre> |
<pre> |
||
nxn n=: 1 2 3 4 5 6 7 8 9 10 |
nxn n=: 1 2 3 4 5 6 7 8 9 10 |
||
Queens : 1 1 2 3 3 4 4 5 5 5 |
Queens : 1 1 2 3 3 4 4 5 5 5 |
||
Bishop : 1 2 3 4 5 6 7 8 9 10 |
Bishop : 1 2 3 4 5 6 7 8 9 10 |
||
.......... |
. . . . . . . . . . |
||
...... |
. . . . . . . Q . . |
||
.......... |
. . . . . . . . . . |
||
. Q . . . . . . . . |
|||
.......... |
. . . . . . . . . . |
||
.... |
. . . . . Q . . . . |
||
.......... |
. . . . . . . . . . |
||
........ |
. . . . . . . . . Q |
||
.......... |
. . . . . . . . . . |
||
.. |
. . . Q . . . . . . |
||
. . . . . . . . . . |
|||
.... |
. . . . B . . . . . |
||
... |
. . . . . . B . . . |
||
.... |
. . . . B . . . . . |
||
... |
. . . . . . B . . . |
||
........ |
. B . . . . . . . . |
||
... |
. . . B . B . . . . |
||
.... |
. . . . . B . . . . |
||
.... |
. . . . . . . . B . |
||
. . . . B . . . . . |
|||
Real time: |
Real time: 25.935 s CPU share: 99.27 % //@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}}== |
=={{header|Phix}}== |
||
{{libheader|Phix/pGUI}} |
{{libheader|Phix/pGUI}} |
||
{{libheader|Phix/online}} |
{{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;">-- |
<span style="color: #000080;font-style:italic;">-- |
||
-- demo\rosetta\minQBN.exw |
-- demo\rosetta\minQBN.exw |
||
Line 918: | Line 1,503: | ||
--</span> |
--</span> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</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;">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: #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;">""" |
<span style="color: #000000;">help_text</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""" |
||
Finds the minimum number of Queens, Bishops, |
Finds the minimum number of Queens, Bishops, or Knights that can be placed on an NxN board |
||
such that no piece attacks another but every unoccupied square is attacked. |
such that no piece attacks another but every unoccupied square is attacked. |
||
Line 927: | Line 1,513: | ||
being or yet to be tried, and a green number means it has found a solution. |
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 |
Click on the legend, or press Q/B/N and 1..9/T and/or +/-, to show the answer or maniaical |
||
workings of a particular sub-task. Use space to toggle the timer on and off. |
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. |
The window title shows additional information for the selected item. |
||
"""</span> |
"""</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: #004080;">sequence</span> <span style="color: #000000;">board</span> |
||
<span style="color: #008080;">constant</span> <span style="color: #000000;"> |
<span style="color: #008080;">constant</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;">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: #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: #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> |
<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 944: | Line 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;">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;">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 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: #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;">'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> |
<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 981: | Line 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: #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: #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;">' |
<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: #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;">if</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> |
||
<span style="color: # |
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">ceil</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: #008080;">if</span> <span style="color: #000000;">piece</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'B'</span> <span style="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 |
|||
-- |
-- valid bishop solution can be 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: # |
<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;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">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: #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;">return</span> <span style="color: #000000;">res</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
Line 1,001: | Line 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: #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: #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: # |
<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: #000000;">1</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> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
||
Line 1,008: | Line 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: #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;"> |
<span style="color: #008080;">constant</span> <span style="color: #000000;">SQBN</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" QBN"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (or " 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> |
<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 1,014: | Line 1,630: | ||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">state</span> |
<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: #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: #000000;">state</span> <span style="color: #0000FF;">=</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;">maxq</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;">maxb</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;">maxn</span><span style="color: #0000FF;">)}</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: #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;"> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cheat</span><span style="color: #0000FF;">?</span><span style="color: #000000;">cheats</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: #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: #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;"> |
<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> <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;">m</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: #000000;">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> |
||
<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 1,032: | Line 1,663: | ||
<span style="color: #000080;font-style:italic;">-- find something not yet done</span> |
<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: #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;"> |
<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;">maxqbn</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;">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;"> |
<span style="color: #008080;">if</span> <span style="color: #000000;">ndx</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;">pdx</span><span style="color: #0000FF;">])</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;">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> |
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ndx</span> |
||
Line 1,043: | Line 1,675: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<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: #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: #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> |
<span style="color: #008080;">else</span> |
||
Line 1,051: | Line 1,684: | ||
<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: #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;">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: # |
<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: #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: #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> |
<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 1,070: | Line 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;">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;">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;">' |
<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: #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> |
<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 1,099: | Line 1,732: | ||
<span style="color: #000000;">m</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
<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: #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;">' |
<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;">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> |
<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 1,111: | Line 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: #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;">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;"> |
<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;">maxqbn</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: #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> |
<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 1,122: | Line 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: #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: #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;"> |
<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;">maxqbn</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: #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: #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: # |
<span style="color: #008080;">if</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">i</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;">j</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span> |
||
<span style="color: #004080;">string</span> <span style="color: #000000;">txt</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #000000;">SQBN</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: #0000FF;">..</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]:</span> |
|||
<span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</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;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #000000;">i</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;">2</span><span style="color: #0000FF;">])))</span> |
|||
<span style="color: # |
<span style="color: #004080;">atom</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;">i</span><span style="color: #0000FF;">==</span><span style="color: #000000;">0</span> <span style="color: #008080;">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: #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;">cdCanvasSetForeground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">colour</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: #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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
Line 1,145: | Line 1,780: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<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: #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;"> |
<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;">QBNU</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: # |
<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;">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: #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: #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: #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;">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> |
<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 1,165: | Line 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: #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: #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: # |
<span style="color: #004080;">string</span> <span style="color: #000000;">ac</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">my</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">]&</span><span style="color: #008000;">""</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;">for</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> |
||
Line 1,189: | Line 1,826: | ||
<span style="color: #008080;">function</span> <span style="color: #000000;">help</span><span style="color: #0000FF;">()</span> |
<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: #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;"> |
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
Line 1,197: | Line 1,834: | ||
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_CLOSE</span> |
<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;">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: # |
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #004600;">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: #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: #008000;">" |
<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;">"123456789T+-!"</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: #008080;">then</span> |
||
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"> |
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</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: #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;">elsif</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #000000;"> |
<span style="color: #008080;">elsif</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">4</span> <span style="color: #008080;">then</span> <span style="color: #000000;">cp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> |
||
<span style="color: #008080;">elsif</span> <span style="color: #000000;"> |
<span style="color: #008080;">elsif</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">14</span> <span style="color: #008080;">then</span> <span style="color: #000000;">bn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">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;">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: #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: #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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
Line 1,217: | Line 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: #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: #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;"> |
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">p</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">3</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: #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> |
<span style="color: #7060A8;">IupUpdate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span> |
||
Line 1,252: | Line 1,890: | ||
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
=={{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}}== |
=={{header|Wren}}== |
||
===CLI=== |
|||
{{libheader|Wren-fmt}} |
{{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]. |
|||
< |
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
||
var board |
var board |
||
Line 1,269: | Line 2,241: | ||
var minCount |
var minCount |
||
var layout |
var layout |
||
var isAttacked = Fn.new { |piece, row, col| |
var isAttacked = Fn.new { |piece, row, col| |
||
if (piece == "Q") { |
if (piece == "Q") { |
||
Line 1,278: | Line 2,250: | ||
diag2Lookup[diag2[row][col]]) return true |
diag2Lookup[diag2[row][col]]) return true |
||
} else if (piece == "B") { |
} else if (piece == "B") { |
||
if (board[row][col]) return true |
|||
if (diag1Lookup[diag1[row][col]] || |
if (diag1Lookup[diag1[row][col]] || |
||
diag2Lookup[diag2[row][col]]) return true |
diag2Lookup[diag2[row][col]]) return true |
||
Line 1,293: | Line 2,264: | ||
} |
} |
||
return false |
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,305: | Line 2,288: | ||
var placePiece // recursive function |
var placePiece // recursive function |
||
placePiece = Fn.new { |piece, countSoFar| |
placePiece = Fn.new { |piece, countSoFar, maxCount| |
||
if (countSoFar >= minCount) return |
if (countSoFar >= minCount) return |
||
var allAttacked = true |
var allAttacked = true |
||
var ti = 0 |
|||
var tj = 0 |
|||
for (i in 0...n) { |
for (i in 0...n) { |
||
for (j in 0...n) { |
for (j in 0...n) { |
||
if (!isAttacked.call(piece, i, j)) { |
if (!isAttacked.call(piece, i, j)) { |
||
allAttacked = false |
allAttacked = false |
||
ti = i |
|||
tj = j |
|||
break |
break |
||
} |
} |
||
Line 1,322: | Line 2,309: | ||
return |
return |
||
} |
} |
||
if (countSoFar <= maxCount) { |
|||
var si = (piece == "K") ? (ti-2).max(0) : ti |
|||
var sj = (piece == "K") ? (tj-2).max(0) : tj |
|||
for (i in si...n) { |
|||
for (j in sj...n) { |
|||
if (!isAttacked.call(piece, i, j)) { |
|||
if ((i == ti && j == tj) || attacks.call(piece, i, j, ti, tj)) { |
|||
board[i][j] = |
board[i][j] = true |
||
if (piece != "K") { |
|||
diag1Lookup[diag1[i][j]] = true |
|||
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,337: | Line 2,334: | ||
} |
} |
||
var start = System.clock |
|||
var pieces = ["Q", "B", "K"] |
var pieces = ["Q", "B", "K"] |
||
var limits = {"Q": 10, "B": |
var limits = {"Q": 10, "B": 10, "K": 10} |
||
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"} |
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"} |
||
for (piece in pieces) { |
for (piece in pieces) { |
||
Line 1,347: | Line 2,345: | ||
board = List.filled(n, null) |
board = List.filled(n, null) |
||
for (i in 0...n) board[i] = List.filled(n, false) |
for (i in 0...n) board[i] = List.filled(n, false) |
||
if (piece != "K") { |
|||
diag1 = List.filled(n, null) |
|||
for (i in 0...n) { |
|||
diag1[i] = List.filled(n, 0) |
|||
for (j in 0...n) diag1[i][j] = i + j |
|||
} |
|||
diag2 = List.filled(n, null) |
|||
for (i in 0...n) { |
|||
diag2[i] = List.filled(n, 0) |
|||
for (j in 0...n) diag2[i][j] = i - j + n - 1 |
|||
} |
|||
diag1Lookup = List.filled(2*n-1, false) |
|||
diag2Lookup = List.filled(2*n-1, false) |
|||
} |
} |
||
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 |
minCount = Num.maxSafeInteger |
||
layout = "" |
layout = "" |
||
for (maxCount in 1..n*n) { |
|||
placePiece.call(piece, 0, maxCount) |
|||
if (minCount <= n*n) break |
|||
} |
|||
Fmt.print("$2d x $-2d : $d", n, n, minCount) |
Fmt.print("$2d x $-2d : $d", n, n, minCount) |
||
if (n == limits[piece]) { |
if (n == limits[piece]) { |
||
Line 1,370: | Line 2,373: | ||
n = n + 1 |
n = n + 1 |
||
} |
} |
||
} |
|||
}</lang> |
|||
System.print("Took %(System.clock - start) seconds.")</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
Line 1,410: | Line 2,414: | ||
5 x 5 : 5 |
5 x 5 : 5 |
||
6 x 6 : 6 |
6 x 6 : 6 |
||
7 x 7 : 7 |
|||
8 x 8 : 8 |
|||
9 x 9 : 9 |
|||
10 x 10 : 10 |
|||
Bishops on a |
Bishops on a 10 x 10 board: |
||
. . . . . . . . . B |
|||
. . . |
. . . . . . . . . . |
||
. . . B . . |
. . . B . B . . . . |
||
. . . . . . |
. . . B . B . B . . |
||
. . |
B . . . . . . . . . |
||
. . . . . . |
. . . . . . . . . . |
||
. . . . . B . . . . |
|||
. . . . . B . . . . |
|||
. . . . . B . . . . |
|||
. . . . . . . . . . |
|||
Knights |
Knights |
||
Line 1,428: | Line 2,440: | ||
4 x 4 : 4 |
4 x 4 : 4 |
||
5 x 5 : 5 |
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 |
Knights on a 10 x 10 board: |
||
. . . . . . . . . . |
|||
. . . . . |
. . K K . . . . . . |
||
. . K K . |
. . K K . . . K K . |
||
. . K K . |
. . . . . . . K K . |
||
. . . . . |
. . . . . . . . . . |
||
. . . . . . . . . . |
|||
. K K . . . . . . . |
|||
. K K . . . K K . . |
|||
. . . . . . K K . . |
|||
. . . . . . . . . . |
|||
Took 1276.522608 seconds. |
|||
</pre> |
</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> |
<pre> |
||
Queens |
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 . . . . . |
|||
Took 3.244584 seconds. |
|||
Q . . . . . . . |
|||
. . Q . . . . . |
|||
. . . . Q . . . |
|||
. Q . . . . . . |
|||
. . . Q . . . . |
|||
. . . . . . . . |
|||
. . . . . . . . |
|||
. . . . . . . . |
|||
</pre> |
</pre> |
Latest revision as of 09:07, 6 January 2024
N-Queens: you've been there; done that; have the T-shirt. It is time to find the minimum number of Queens, Bishops or Knights that can be placed on an NxN board such that no piece attacks another but every unoccupied square is attacked.
For N=1 to 10 discover the minimum number of Queens, Bishops, and Knights required to fulfill the above requirement. For N=8 print out a possible solution for Queens and Bishops.
- Links
- OEIS Independent domination number for queens
- OEIS Independent domination number for knights
- ScienceDirect | minimum dominating set of queens - ways to do it.
F#
// Minimum knights to attack all squares not occupied on an NxN chess board. Nigel Galloway: May 12th., 2022
type att={n:uint64; g:uint64}
static member att n g=let g=g|>Seq.fold(fun n g->n ||| (1UL<<<g)) 0UL in {n=n|>Seq.fold(fun n g->n ||| (1UL<<<g)) 0UL; g=g}
static member (+) (n,g)=let x=n.g ||| g.g in {n=n.n ||| g.n; g=x}
let fN g=let fG n g=[n-g-g-1;n-g-g+1;n-g+2;n-g-2;n+g+g-1;n+g+g+1;n+g-2;n+g+2]|>List.filter(fun x->0<=x && x<g*g && abs(x%g-n%g)+abs(x/g-n/g)=3)|>List.distinct|>List.map(fun n->n/2)
let n,g=Array.init(g*g)(fun n->att.att [n/2] (fG n g)), Array.init(g*g)(fun n->att.att (fG n g) [n/2]) in (fun g->n.[g]),(fun n->g.[n])
type cand={att:att; n:int; g:int}
type Solver={n:cand seq; i:int[]; g:(int -> att) * (int -> att); e:att; l:int[]}
member this.test()=let rec test n i g e l=match g with 0UL->(if i=this.e then Some(n,e) else None)|g when g%2UL=1UL->test n (i+((snd this.g)(this.i.[l])))(g/2UL)(e+1)(l+1) |_->test n i (g/2UL) e (l+1)
let n=this.n|>Seq.choose(fun n->test n n.att (this.e.g^^^n.att.g) 0 0) in if Seq.isEmpty n then None else Some(n|>Seq.minBy snd)
member this.xP() ={this with n=this.n|>Seq.collect(fun n->[for g in n.n..n.g do let att=n.att+((fst this.g)(this.l.[g])) in yield {n with att=att; n=g}])}
let rec slvK (n:Solver) i g l = match n.test() with Some(r,ta)->match min l (g+ta) with t when t>2*(g+1) || l<t->slvK (n.xP()) (if t<l then Some(r,ta) else i) (g+1) (min t l) |t->Some(min t l,r)
|_->slvK (n.xP()) i (g+1) l
let tC bw s (att:att)=let n=Array2D.init s s (fun n g->if (n+g)%2=bw then (if att.n &&& pown 2UL ((n*s+g)/2) > 0UL then "X" else ".") else (if att.g &&& pown 2UL ((n*s+g)/2) > 0UL then "~" else "o"))
for g in 0..s-1 do n.[g,0..s-1]|>Seq.iter(fun g->printf "%s" g); printfn ""
let solveK g=printfn "\nSolving for %dx%d board" g g
let bs,ws=[|for n in g..g+g..(g*g-1)/2 do for z in 0..g+1..(g*g-1)/2-n->((n+z)/g,(n+z)%g)|],[|for n in 0..g+g..(g*g-1)/2 do for z in 0..g+1..(g*g-1)/2-n->((n+z)/g,(n+z)%g)|]
let i,l=let n,i=[|for n in 0..g-1 do for g in 0..g-1->(n,g)|]|>Array.partition(fun(n,g)->(n+g)%2=1) in n|>Array.map(fun(n,i)->n*g+i), i|>Array.map(fun(n,i)->n*g+i)
let t,f=System.DateTime.UtcNow,fN g
let bK={l=Array.concat[bs|>Array.map(fun(n,i)->n*g+i);i]|>Array.distinct; i=l; e=att.att [0..i.Length-1] [0..l.Length-1]; n=bs|>Array.mapi(fun l (n,e)->let att=((fst f)(n*g+e)) in {att=att; n=l+1; g=i.Length-1}); g=fN g}
let wK={l=Array.concat[ws|>Array.map(fun(n,i)->n*g+i);l]|>Array.distinct; i=i; e=att.att [0..l.Length-1] [0..i.Length-1]; n=ws|>Array.mapi(fun i (n,e)->let att=((fst f)(n*g+e)) in {att=att; n=i+1; g=l.Length-1}); g=fN g}
let (rn,rb),tc=match g with 1|2->(slvK wK None 1 (g*g/2+g%2)).Value, tC 0 g
|x when x%2=0->(slvK bK None 1 (g*g/2)).Value, tC 1 g
|_->let x,y=(slvK bK None 1 (g*g/2)).Value, (slvK wK None 1 (g*g/2+1)).Value in if (fst x)<(fst y) then x,tC 1 g else y,tC 0 g
printfn "Solution found using %d knights in %A:" rn (System.DateTime.UtcNow-t); tc rb.att
for n in 1..10 do solveK n
- Output:
Solving for 1x1 board Solution found using 1 knights in 00:00:00.0331768: X Solving for 2x2 board Solution found using 2 knights in 00:00:00: Xo oX Solving for 3x3 board Solution found using 4 knights in 00:00:00.0156191: Xo. oX~ .~. Solving for 4x4 board Solution found using 4 knights in 00:00:00: ~.~. XoXo ~.~. .~.~ Solving for 5x5 board Solution found using 5 knights in 00:00:00: .o.~. ~X~.~ .o.~. ~X~.~ .o.~. Solving for 6x6 board Solution found using 8 knights in 00:00:00: ~.~.~. .~.~.~ oX~.oX Xo.~Xo ~.~.~. .~.~.~ Solving for 7x7 board Solution found using 13 knights in 00:00:00.1426817: X~.~.o. oX~.~.~ X~.~.o. ~.~.~Xo .~.~.~. o.oX~.~ .~.o.~X Solving for 8x8 board Solution found using 14 knights in 00:00:00.2655969: o.~X~.~. X~.~.~.~ o.~.~Xo. .~.~.o.~ ~.o.~.~. .oX~.~.o ~.~.~.~X .~.~X~.o Solving for 9x9 board Solution found using 14 knights in 00:00:10.2331055: .~.~.~.~. ~.o.~.o.~ .~Xo.oX~. ~.~.~.~.~ X~.~.~.~X ~.~.~.~.~ .~Xo.oX~. ~.o.~.o.~ .~.~.~.~. Solving for 10x10 board Solution found using 16 knights in 00:04:44.0573668: ~.~.~.~.~. .~.~.~Xo.~ ~Xo.~.oX~. .oX~.~.~.~ ~.~.~.~.~. .~.~.~.~.~ ~.~.~.~Xo. .~Xo.~.oX~ ~.oX~.~.~. .~.~.~.~.~
Go
This was originally a translation of the Wren entry but was substantially improved by 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.
Timing is for an Intel Core i7-8565U machine running Ubuntu 20.04.
package main
import (
"fmt"
"math"
"strings"
"time"
)
var board [][]bool
var diag1, diag2 [][]int
var diag1Lookup, diag2Lookup []bool
var n, minCount int
var layout string
func isAttacked(piece string, row, col int) bool {
if piece == "Q" {
for i := 0; i < n; i++ {
if board[i][col] || board[row][i] {
return true
}
}
if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] {
return true
}
} else if piece == "B" {
if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] {
return true
}
} else { // piece == "K"
if board[row][col] {
return true
}
if row+2 < n && col-1 >= 0 && board[row+2][col-1] {
return true
}
if row-2 >= 0 && col-1 >= 0 && board[row-2][col-1] {
return true
}
if row+2 < n && col+1 < n && board[row+2][col+1] {
return true
}
if row-2 >= 0 && col+1 < n && board[row-2][col+1] {
return true
}
if row+1 < n && col+2 < n && board[row+1][col+2] {
return true
}
if row-1 >= 0 && col+2 < n && board[row-1][col+2] {
return true
}
if row+1 < n && col-2 >= 0 && board[row+1][col-2] {
return true
}
if row-1 >= 0 && col-2 >= 0 && board[row-1][col-2] {
return true
}
}
return false
}
func abs(i int) int {
if i < 0 {
i = -i
}
return i
}
func attacks(piece string, row, col, trow, tcol int) bool {
if piece == "Q" {
return row == trow || col == tcol || abs(row-trow) == abs(col-tcol)
} else if piece == "B" {
return abs(row-trow) == abs(col-tcol)
} else { // piece == "K"
rd := abs(trow - row)
cd := abs(tcol - col)
return (rd == 1 && cd == 2) || (rd == 2 && cd == 1)
}
}
func storeLayout(piece string) {
var sb strings.Builder
for _, row := range board {
for _, cell := range row {
if cell {
sb.WriteString(piece + " ")
} else {
sb.WriteString(". ")
}
}
sb.WriteString("\n")
}
layout = sb.String()
}
func placePiece(piece string, countSoFar, maxCount int) {
if countSoFar >= minCount {
return
}
allAttacked := true
ti := 0
tj := 0
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if !isAttacked(piece, i, j) {
allAttacked = false
ti = i
tj = j
break
}
}
if !allAttacked {
break
}
}
if allAttacked {
minCount = countSoFar
storeLayout(piece)
return
}
if countSoFar <= maxCount {
si := ti
sj := tj
if piece == "K" {
si = si - 2
sj = sj - 2
if si < 0 {
si = 0
}
if sj < 0 {
sj = 0
}
}
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
}
}
}
}
}
}
}
func main() {
start := time.Now()
pieces := []string{"Q", "B", "K"}
limits := map[string]int{"Q": 10, "B": 10, "K": 10}
names := map[string]string{"Q": "Queens", "B": "Bishops", "K": "Knights"}
for _, piece := range pieces {
fmt.Println(names[piece])
fmt.Println("=======\n")
for n = 1; ; n++ {
board = make([][]bool, n)
for i := 0; i < n; i++ {
board[i] = make([]bool, n)
}
if piece != "K" {
diag1 = make([][]int, n)
for i := 0; i < n; i++ {
diag1[i] = make([]int, n)
for j := 0; j < n; j++ {
diag1[i][j] = i + j
}
}
diag2 = make([][]int, n)
for i := 0; i < n; i++ {
diag2[i] = make([]int, n)
for j := 0; j < n; j++ {
diag2[i][j] = i - j + n - 1
}
}
diag1Lookup = make([]bool, 2*n-1)
diag2Lookup = make([]bool, 2*n-1)
}
minCount = math.MaxInt32
layout = ""
for maxCount := 1; maxCount <= n*n; maxCount++ {
placePiece(piece, 0, maxCount)
if minCount <= n*n {
break
}
}
fmt.Printf("%2d x %-2d : %d\n", n, n, minCount)
if n == limits[piece] {
fmt.Printf("\n%s on a %d x %d board:\n", names[piece], n, n)
fmt.Println("\n" + layout)
break
}
}
}
elapsed := time.Now().Sub(start)
fmt.Printf("Took %s\n", elapsed)
}
- Output:
Queens ======= 1 x 1 : 1 2 x 2 : 1 3 x 3 : 1 4 x 4 : 3 5 x 5 : 3 6 x 6 : 4 7 x 7 : 4 8 x 8 : 5 9 x 9 : 5 10 x 10 : 5 Queens on a 10 x 10 board: . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . Bishops ======= 1 x 1 : 1 2 x 2 : 2 3 x 3 : 3 4 x 4 : 4 5 x 5 : 5 6 x 6 : 6 7 x 7 : 7 8 x 8 : 8 9 x 9 : 9 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 22.383253365s
J
This is a crude attempt -- brute force search with some minor state space pruning. I am not patient enough to run this for boards larger than 7x7 for knights:
genboard=: {{
safelen=:2*len=: {.y
shape=: 2$len
board=: shape$0
safeshape=: ,~safelen
c=:,coords=: safeshape#.shape#:i.shape
qrow=. i:{.shape-1
qcol=. qrow*safelen
qdiag1=. qrow+qcol
qdiag2=. qrow-qcol
queen=: ~.qrow,qcol,qdiag1,qdiag2
k1=. ,(1 _1*safelen)+/2 _2
k2=. ,(2 _2*safelen)+/1 _1
knight=: 0,k1,k2
bishop=: ~.qdiag1,qdiag2
row=. i.len
first=: ~.,coords#"1~(row<:>.<:len%2) * >:/~ row
EMPTY
}}
placebishops=: {{coords #&,~ 1 (<.-:len)} board}}
placequeens=: {{
N=. 0
while. N=. N+1 do.
assert. N<:#c
for_seq. first do.
board=. coords e.queen+seq
if. 0 e.,board do.
if. 1<N do.
seq=. board queen place1 N seq
if. #seq do.
assert. N-:#seq
assert. */c e.,queen+/seq
seq return.
end.
end.
else.
seq return.
end.
end.
end.
EMPTY
}}
placeknights=:{{
N=. 0
while. N=. N+1 do.
assert. N<:#c
for_seq. c do.
board=. coords e.knight+seq
if. 0 e.,board do.
if. 1<N do.
seq=. board knight place1 N seq
if. #seq do.
assert. N-:#seq
assert. */c e.,knight+/seq
seq return.
end.
end.
else.
seq return.
end.
end.
end.
EMPTY
}}
NB. x: board with currently attacked locations marked
NB. m: move targets
NB. n: best sequence length so far
NB. y: coords of placed pieces
place1=: {{
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. seq return.
end.
end.
EMPTY
}}
task=: {{
B=:Q=:K=:i.0
for_order.1+i.y do.
genboard order
B=: 1j1#"1'.B'{~coords e.b=. placebishops ''
Q=: 1j1#"1'.Q'{~coords e.q=. placequeens ''
if. 8>order do.
K=: 1j1#"1'.K'{~coords e.k=. placeknights ''
echo (":B;Q;K),&.|:>(' B: ',":#b);(' Q: ',":#q);' K: ',":#k
else.
echo (":B;Q),&.|:>(' B: ',":#b);' Q: ',":#q
end.
end.
}}
Task output:
task 10
+--+--+--+ B: 1
|B |Q |K | Q: 1
+--+--+--+ K: 1
+----+----+----+ B: 2
|. . |Q . |K K | Q: 1
|B B |. . |K K | K: 4
+----+----+----+
+------+------+------+ B: 3
|. . . |. . . |K K K | Q: 1
|B B B |. Q . |. K . | K: 4
|. . . |. . . |. . . |
+------+------+------+
+--------+--------+--------+ B: 4
|. . . . |Q . . . |. K K . | Q: 3
|. . . . |. . Q . |. K K . | K: 4
|B B B B |. . . . |. . . . |
|. . . . |. Q . . |. . . . |
+--------+--------+--------+
+----------+----------+----------+ B: 5
|. . . . . |Q . . . . |K . . . . | Q: 3
|. . . . . |. . . Q . |. . . . . | K: 5
|B B B B B |. . . . . |. . K K . |
|. . . . . |. . Q . . |. . K K . |
|. . . . . |. . . . . |. . . . . |
+----------+----------+----------+
+------------+------------+------------+ B: 6
|. . . . . . |Q . . . . . |K . . . . K | Q: 4
|. . . . . . |. . Q . . . |. . . . . . | K: 8
|. . . . . . |. . . . . Q |. . K K . . |
|B B B B B B |. . . . . . |. . K K . . |
|. . . . . . |. . . . . . |. . . . . . |
|. . . . . . |. Q . . . . |K . . . . K |
+------------+------------+------------+
+--------------+--------------+--------------+ B: 7
|. . . . . . . |. . . . . . . |K K K K . K . | Q: 4
|. . . . . . . |. Q . . . . . |. . . . . . . | K: 13
|. . . . . . . |. . . . Q . . |. . . . . K . |
|B B B B B B B |. . . . . . . |K . . . . K . |
|. . . . . . . |. . . . . . . |. . . . . . . |
|. . . . . . . |Q . . . . . . |K . K K . K . |
|. . . . . . . |. . . Q . . . |. . . . . . K |
+--------------+--------------+--------------+
+----------------+----------------+ B: 8
|. . . . . . . . |Q . . . . . . . | Q: 5
|. . . . . . . . |. . Q . . . . . |
|. . . . . . . . |. . . . Q . . . |
|. . . . . . . . |. Q . . . . . . |
|B B B B B B B B |. . . Q . . . . |
|. . . . . . . . |. . . . . . . . |
|. . . . . . . . |. . . . . . . . |
|. . . . . . . . |. . . . . . . . |
+----------------+----------------+
+------------------+------------------+ B: 9
|. . . . . . . . . |Q . . . . . . . . | Q: 5
|. . . . . . . . . |. . Q . . . . . . |
|. . . . . . . . . |. . . . . . Q . . |
|. . . . . . . . . |. . . . . . . . . |
|B B B B B B B B B |. . . . . . . . . |
|. . . . . . . . . |. Q . . . . . . . |
|. . . . . . . . . |. . . . . Q . . . |
|. . . . . . . . . |. . . . . . . . . |
|. . . . . . . . . |. . . . . . . . . |
+------------------+------------------+
+--------------------+--------------------+ B: 10
|. . . . . . . . . . |Q . . . . . . . . . | Q: 6
|. . . . . . . . . . |. . Q . . . . . . . |
|. . . . . . . . . . |. . . . . . . . Q . |
|. . . . . . . . . . |. . . . . . . . . . |
|. . . . . . . . . . |. . . . . . . . . . |
|B B B B B B B B B B |. . . Q . . . . . . |
|. . . . . . . . . . |. . . . . . . . . Q |
|. . . . . . . . . . |. . . . . . . . . . |
|. . . . . . . . . . |. . . . . Q . . . . |
|. . . . . . . . . . |. . . . . . . . . . |
+--------------------+--------------------+
Julia
Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support.
""" Rosetta code task N-queens_minimum_and_knights_and_bishops """
import Cbc
using JuMP
using LinearAlgebra
""" Make a printable string from a matrix of zeros and ones using a char ch for 1, a period for !=1. """
function smatrix(x, n, ch)
s = ""
for i in 1:n, j in 1:n
s *= lpad(x[i, j] == 1 ? "$ch" : ".", 2) * (j == n ? "\n" : "")
end
return s
end
""" N-queens minimum, oeis.org/A075458 """
function queensminimum(N, char = "Q")
if N < 4
a = zeros(Int, N, N)
a[N ÷ 2 + 1, N ÷ 2 + 1] = 1
return 1, smatrix(a, N, char)
end
model = Model(Cbc.Optimizer)
@variable(model, x[1:N, 1:N], Bin)
for i in 1:N
@constraint(model, sum(x[i, :]) <= 1)
@constraint(model, sum(x[:, i]) <= 1)
end
for i in -(N - 1):(N-1)
@constraint(model, sum(diag(x, i)) <= 1)
@constraint(model, sum(diag(reverse(x, dims = 1), i)) <= 1)
end
for i in 1:N, j in 1:N
@constraint(model, sum(x[i, :]) + sum(x[:, j]) + sum(diag(x, j - i)) +
sum(diag(rotl90(x), N - j - i + 1)) >= 1)
end
set_silent(model)
@objective(model, Min, sum(x))
optimize!(model)
solution = round.(Int, value.(x))
minresult = sum(solution)
return minresult, smatrix(solution, N, char)
end
""" N-bishops minimum, same as N """
function bishopsminimum(N, char = "B")
N == 1 && return 1, "$char"
N == 2 && return 2, "$char .\n$char .\n"
model = Model(Cbc.Optimizer)
@variable(model, x[1:N, 1:N], Bin)
for i in 1:N, j in 1:N
@constraint(model, sum(diag(x, j - i)) + sum(diag(rotl90(x), N - j - i + 1)) >= 1)
end
set_silent(model)
@objective(model, Min, sum(x))
optimize!(model)
solution = round.(Int, value.(x))
minresult = sum(solution)
return minresult, smatrix(solution, N, char)
end
""" N-knights minimum, oeis.org/A342576 """
function knightsminimum(N, char = "N")
N < 2 && return 1, "$char"
knightdeltas = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
model = Model(Cbc.Optimizer)
# to simplify the constraints, embed the board of size N inside a board of size n + 4
@variable(model, x[1:N+4, 1:N+4], Bin)
@constraint(model, x[:, 1:2] .== 0)
@constraint(model, x[1:2, :] .== 0)
@constraint(model, x[:, N+3:N+4] .== 0)
@constraint(model, x[N+3:N+4, :] .== 0)
for i in 3:N+2, j in 3:N+2
@constraint(model, x[i, j] + sum(x[i + d[1], j + d[2]] for d in knightdeltas) >= 1)
@constraint(model, x[i, j] => {sum(x[i + d[1], j + d[2]] for d in knightdeltas) == 0})
end
set_silent(model)
@objective(model, Min, sum(x))
optimize!(model)
solution = round.(Int, value.(x))
minresult = sum(solution)
return minresult, smatrix(solution[3:N+2, 3:N+2], N, char)
end
const examples = fill("", 3)
println(" Squares Queens Bishops Knights")
@time for N in 1:10
print(lpad(N^2, 10))
i, examples[1] = queensminimum(N)
print(lpad(i, 10))
i, examples[2] = bishopsminimum(N)
print(lpad(i, 10))
i, examples[3] = knightsminimum(N)
println(lpad(i, 10))
end
println("\nExamples for N = 10:\n\nQueens:\n", examples[1], "\nBishops:\n", examples[2],
"\nKnights:\n", examples[3])
- Output:
Squares Queens Bishops Knights 1 1 1 1 4 1 2 4 9 1 3 4 16 3 4 4 25 3 5 5 36 4 6 8 49 4 7 13 64 5 8 14 81 5 9 14 100 5 10 16 49.922920 seconds (30.87 M allocations: 1.656 GiB, 2.39% gc time, 65.49% compilation time) Examples for N = 10: Queens: . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . Bishops: . . . . . . . . . . . . . . . B . . . . . . . . . B . . . . . B . . . . . . . . . B . . . . B . . . . . . . . . B . . . . . B . . . B . . . . . . . . . B . . . . B . . . . . . . . . . . . . . . . . . Knights: . . . . . . . . . . . . N N . . . . . . . . N N . . . N N . . . . . . . . N N . . . . . . . . . . . . . . . . . . . . . . N N . . . . . . . . N N . . . N N . . . . . . . . N N . . . . . . . . . . . .
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()
- Output:
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)
Pascal
Free Pascal
The first Q,B in the first row is only placed lmt..mid because of symmetry reasons.
14 Queens takes 2 min @home ~2.5x faster than TIO.RUN
program TestMinimalQueen;
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
uses
sysutils;
type
tDeltaKoor = packed record
dRow,
dCol : Int8;
end;
const
cKnightAttacks : array[0..7] of tDeltaKoor =
((dRow:-2;dCol:-1),(dRow:-2;dCol:+1),
(dRow:-1;dCol:-2),(dRow:-1;dCol:+2),
(dRow:+1;dCol:-2),(dRow:+1;dCol:+2),
(dRow:+2;dCol:-1),(dRow:+2;dCol:+1));
KoorCOUNT = 16;
type
tLimit = 0..KoorCOUNT-1;
tPlayGround = array[tLimit,tLimit] of byte;
tCheckPG = array[0..2*KoorCOUNT] of tplayGround;
tpPlayGround = ^tPlayGround;
var
{$ALIGN 32}
CPG :tCheckPG;
Qsol,BSol,KSol :tPlayGround;
pgIdx,minIdx : nativeInt;
procedure pG_Out(pSol:tpPlayGround;ConvChar : string;lmt: NativeInt);
var
row,col: NativeInt;
begin
iF length(ConvChar)<>3 then
EXIT;
for row := lmt downto 0 do
Begin
for col := 0 to lmt do
write(ConvChar[1+pSol^[row,col]],' ');
writeln;
end;
writeln;
end;
procedure LeftAscDia(row,col,lmt: NativeInt);
var
pPG :tpPlayGround;
j: NativeInt;
begin
pPG := @CPG[pgIdx];
if row >= col then
begin
j := row-col;
col := lmt-j;
row := lmt;
repeat
pPG^[row,col] := 1;
dec(col);
dec(row);
until col < 0;
end
else
begin
j := col-row;
row := lmt-j;
col := lmt;
repeat
pPG^[row,col] := 1;
dec(row);
dec(col);
until row < 0;
end;
end;
procedure RightAscDia(row,col,lmt: NativeInt);
var
pPG :tpPlayGround;
j: NativeInt;
begin
pPG := @CPG[pgIdx];
j := row+col;
if j <= lmt then
begin
col := j;
row := 0;
repeat
pPG^[row,col] := 1;
dec(col);
inc(row);
until col < 0;
end
else
begin
col := lmt;
row := j-lmt;
repeat
pPG^[row,col] := 1;
inc(row);
dec(col);
until row > lmt;
end;
end;
function check(lmt:nativeInt):boolean;
//check, if all fields are attacked
var
pPG :tpPlayGround;
pRow : pByte;
row,col: NativeInt;
Begin
pPG := @CPG[pgIdx];
For row := lmt downto 0 do
begin
pRow := @pPG^[row,0];
For col := lmt downto 0 do
if pRow[col] = 0 then
EXIT(false);
end;
exit(true);
end;
procedure SetQueen(row,lmt: NativeInt);
var
pPG :tpPlayGround;
i,col,t: NativeInt;
begin
t := pgIdx+1;
if t = minIDX then
EXIT;
pgIdx:= t;
//use state before
// CPG[pgIdx]:=CPG[pgIdx-1];
move(CPG[t-1],CPG[t],SizeOf(tPlayGround));
col := lmt;
//first row only check one half -> symmetry
if row = 0 then
col := col shr 1;
//check every column
For col := col downto 0 do
begin
pPG := @CPG[pgIdx];
if pPG^[row,col] <> 0 then
continue;
//set diagonals
RightAscDia(row,col,lmt);
LeftAscDia(row,col,lmt);
//set row and column as attacked
For i := 0 to lmt do
Begin
pPG^[row,i] := 1;
pPG^[i,col] := 1;
end;
//now set position of queen
pPG^[row,col] := 2;
if check(lmt) then
begin
if minIdx> pgIdx then
begin
minIdx := pgIdx;
Qsol := pPG^;
end;
end
else
if row > lmt then
BREAK
else
//check next rows
For t := row+1 to lmt do
SetQueen(t,lmt);
//copy last state
t := pgIdx;
move(CPG[t-1],CPG[t],SizeOf(tPlayGround));
// CPG[pgIdx]:=CPG[pgIdx-1];
end;
dec(pgIdx);
end;
procedure SetBishop(row,lmt: NativeInt);
var
pPG :tpPlayGround;
col,t: NativeInt;
begin
if pgIdx = minIDX then
EXIT;
inc(pgIdx);
move(CPG[pgIdx-1],CPG[pgIdx],SizeOf(tPlayGround));
col := lmt;
if row = 0 then
col := col shr 1;
For col := col downto 0 do
begin
pPG := @CPG[pgIdx];
if pPG^[row,col] <> 0 then
continue;
RightAscDia(row,col,lmt);
LeftAscDia(row,col,lmt);
//set position of bishop
pPG^[row,col] := 2;
if check(lmt) then
begin
if minIdx> pgIdx then
begin
minIdx := pgIdx;
Bsol := pPG^;
end;
end
else
if row > lmt then
BREAK
else
begin
//check same row
SetBishop(row,lmt);
//check next row
t := row+1;
if (t <= lmt) then
SetBishop(t,lmt);
end;
move(CPG[pgIdx-1],CPG[pgIdx],SizeOf(tPlayGround));
end;
dec(pgIdx);
end;
var
lmt,max : NativeInt;
BEGIN
max := 10;
write(' nxn n=:');
For lmt := 1 to max do
write(lmt:3);
writeln;
write(' Queens :');
For lmt := 0 to max-1 do
begin
pgIdx := 0;
minIdx := lmt;
setQueen(0,lmt);
write(minIDX:3);
end;
writeln;
write(' Bishop :');
For lmt := 0 to max-1 do
begin
pgIdx := 0;
minIdx := 2*lmt+1;
setBishop(0,lmt);
write(minIDX:3);
end;
writeln;
pG_Out(@Qsol,'_.Q',max-1);
writeln;
pG_Out(@Bsol,'_.B',max-1);
END.
- @TIO.RUN:
nxn n=: 1 2 3 4 5 6 7 8 9 10 Queens : 1 1 2 3 3 4 4 5 5 5 Bishop : 1 2 3 4 5 6 7 8 9 10 . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . B . . . . . . . . . . . B . . . . . . . B . . . . . . . . . . . B . . . . B . . . . . . . . . . . B . B . . . . . . . . . B . . . . . . . . . . . . B . . . . . B . . . . . Real time: 25.935 s CPU share: 99.27 % //@home AMD 5600G real 0m10,784s
Perl
Shows how the latest release of Perl can now use booleans.
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
}
}
}
- Output:
Queens ======= 1 x 1 : 1 2 x 2 : 1 3 x 3 : 1 4 x 4 : 3 5 x 5 : 3 6 x 6 : 4 7 x 7 : 4 8 x 8 : 5 9 x 9 : 5 10 x 10 : 5 Queens on a 10 x 10 board: . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . Bishops ======= 1 x 1 : 1 2 x 2 : 2 3 x 3 : 3 4 x 4 : 4 5 x 5 : 5 6 x 6 : 6 7 x 7 : 7 8 x 8 : 8 9 x 9 : 9 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 . . . . . . . . . . . .
Phix
You can run this online here, with cheat mode on so it should all be done in 22s (8.3 on the desktop). 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.
-- -- demo\rosetta\minQBN.exw -- ======================= -- with javascript_semantics atom t0 = time() include pGUI.e constant title = "Minimum QBN", help_text = """ Finds the minimum number of Queens, Bishops, or Knights that can be placed on an NxN board such that no piece attacks another but every unoccupied square is attacked. The legend on the right shows the current search status: a red number means that is still being or yet to be tried, and a green number means it has found a solution. Click on the legend, or press Q/B/N and 1..9/T and/or +/-, to show the answer or maniaical workings of a particular sub-task. Use space to toggle the timer on and off. The window title shows additional information for the selected item. """ constant maxq = 10, -- 1.0s (13 is 3minutes 58s, with maxn=1) maxb = 10, -- 1s (100 is 10s, with maxq=1 and maxn=1) maxn = 10, -- 1mins 10s (9: 11.8s, 8: 8.1s, with maxq=1) maxqbn = max({maxq,maxb,maxn}) bool cheat = true -- eg find 16N on a 10x10 w/o disproving 15N first. -- the total time drops to 8.3s (21.9s under p2js). sequence board constant bm = {{-1,-1},{-1,+1}, {+1,-1},{+1,+1}}, rm = {{-1,0},{0,-1}, {+1,0},{0,+1}}, qm = rm&bm, nm = {{-1,-2},{-2,-1},{-2,+1},{-1,+2}, {+1,-2},{+2,-1},{+2,+1},{+1,+2}} function get_mm(integer piece) switch piece do case 'Q': return qm case 'B': return bm case 'N': return nm end switch crash("uh?") end function function mm_baby(sequence mm, integer piece, row, col, n) sequence res = {} for i=1 to length(mm) do integer {dx,dy} = mm[i], mx = row, my = col while true do mx += dx my += dy if mx<1 or mx>n or my<1 or my>n then exit end if res &= {{mx,my}} if piece='N' then exit end if end while end for return res end function function get_moves(integer piece, n, row, col) -- either occupy or attack [row][col] -- we only have to collect right and down sequence res = {{row,col}}, -- (occupy) mm = get_mm(piece) mm = iff(piece='Q'?extract(mm,{3,4,7,8}) :mm[length(mm)/2+1..$]) mm = mm_baby(mm,piece,row,col,n) for i=1 to length(mm) do integer {mx,my} = mm[i] if board[mx,my]='0' then res &= {{mx,my}} end if end for integer m = ceil(n/2) if piece='B' then -- As pointed out on the talk page, *every* -- valid bishop solution can be transformed -- into all in column m so search only that for i=1 to length(res) do if res[i][2]=m then res = res[i..i] exit end if end for assert(length(res)=1) elsif row=1 and col=1 and n>1 then if piece='Q' then -- first queen on first half of top row -- or first half of diagonal (not cols) assert(length(res)=3*n-2) res = res[1..m]&res[2*n..2*n+m-2] elsif piece='N' and n>2 then -- first knight, was occupy+2, but by -- symmetry we only need it to be 1+1 assert(length(res)=3) res = res[1..2] end if end if -- this cheeky little fella cuts more than half off the -- last phase of 10N... (a circumstantial optimisation) res = reverse(res) return res end function procedure move(sequence rc, integer piece, n) integer {row,col} = rc board[row][col] = piece sequence mm = mm_baby(get_mm(piece),piece,row,col,n) for i=1 to length(mm) do integer {mx,my} = mm[i] board[mx][my] += 1 end for end procedure Ihandle dlg, canvas, timer cdCanvas cddbuffer, cdcanvas constant SQBN = " QBN", -- (or " RBN") QBNU = utf8_to_utf32("♕♗♘") integer bn = 8, -- chosen board is nxn (1..10) cp = 1 -- piece (1,2,3 for QBN) sequence state -- eg go straight for 16N on 10x10, avoid disproving 15N (from OEIS) constant cheats = {{1,1,1,3,3,4,4,5,5,5,5,7,7,8,9,9,9,10,11,11,11,12,13,13,13}, {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22}, {1,4,4,4,5,8,13,14,14,16,22,24,29,33}} -- 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 procedure reset() state = {repeat(0,maxq), repeat(0,maxb), repeat(0,maxn)} -- (in case the maxq/b/n settings altered:) if bn>length(state[cp]) then bn = 1 end if for p=1 to 3 do integer piece = SQBN[p+1] for n=1 to length(state[p]) do atom scolour = CD_RED -- integer m = 1 integer m = iff(cheat?cheats[p][n]:1) board = repeat(repeat('0',n),n) sequence moves = get_moves(piece,n,1,1) string undo = join(board,'\n') state[p][n] = {scolour,m,{moves},{undo},undo,0} end for end for IupSetInt(timer,"RUN",true) end procedure procedure iterative_solve() -- find something not yet done integer n = 0, p for ndx=1 to maxqbn do for pdx=1 to 3 do if ndx<=length(state[pdx]) and state[pdx][ndx][1]!=CD_DARK_GREEN then p = pdx n = ndx exit end if end for if n!=0 then exit end if end for if n=0 then ?{"solved",(elapsed(time()-t0))} IupSetInt(timer,"RUN",false) else -- but work on currently selected first, if needed if state[cp][bn][1]!=CD_DARK_GREEN then p = cp n = bn end if atom t1 = time()+0.04, scolour integer piece = SQBN[p+1], m, count sequence stack, undo, answer {scolour,m,stack,undo,answer,count} = state[p][n] state[p][n] = 0 if n>1 and state[p][n-1][1]=CD_DARK_GREEN and m<state[p][n-1][2] then -- if we needed (eg) 7 bishops to solve a 7x7, that means -- we couldn't solve it with 6, so we are not going to be -- able to solve an 8x8 with 6 (or less) now are we! m = state[p][n-1][2] else while length(stack) do sequence rc = stack[$][1] stack[$] = stack[$][2..$] board = split(undo[$],'\n') move(rc,piece,n) count += 1 bool solved = true for row=1 to n do for col=1 to n do if board[row][col]='0' then if length(stack)<m then stack &= {get_moves(piece,n,row,col)} undo &= {join(board,'\n')} end if solved = false exit end if end for if not solved then exit end if end for if solved then answer = join(board,'\n') scolour = CD_DARK_GREEN stack = {} undo = {} end if while length(stack) and stack[$]={} do stack = stack[1..-2] undo = undo[1..-2] if length(undo)=0 then exit end if end while if solved or time()>t1 then state[p][n] = {scolour,m,stack,undo,answer,count} return end if end while m += 1 end if board = repeat(repeat('0',n),n) stack = {get_moves(piece,n,1,1)} undo = {join(board,'\n')} state[p][n] = {scolour,m,stack,undo,answer,count} end if end procedure atom dx, dy -- (saved for button_cb) function redraw_cb(Ihandle /*canvas*/) integer {w, h} = IupGetIntInt(canvas, "DRAWSIZE") dx = w/40 -- legend fifth dy = h/(maxqbn+1) -- legend delta atom ly = h-dy/2, -- legend top cx = w/2, -- board centre cy = h/2, bs = min(w*.7,h*.9), -- board size ss = bs/bn -- square size cdCanvasActivate(cddbuffer) cdCanvasClear(cddbuffer) atom fontsize = min(ceil(dy/6),ceil(dx/2)) cdCanvasFont(cddbuffer, "Helvetica", CD_PLAIN, fontsize) for i=0 to maxqbn do atom lx = dx*36 for j=0 to 3 do if j=0 or i<=length(state[j]) then string txt = iff(i=0?SQBN[j+1..j+1]: sprintf("%d",iff(j=0?i:state[j][i][2]))) atom colour = iff(i==0 or j==0?CD_BLACK:state[j][i][1]) cdCanvasSetForeground(cddbuffer, colour) cdCanvasText(cddbuffer,lx,ly,txt) end if lx += dx end for ly -= dy end for atom x = cx-bs/2, y = cy+bs/2 cdCanvasSetForeground(cddbuffer, CD_DARK_GREY) for i=1 to bn do for j=1+even(i) to bn by 2 do atom sx = x+j*ss, sy = y-i*ss cdCanvasBox(cddbuffer,sx-ss,sx,sy+ss,sy) end for end for cdCanvasRect(cddbuffer,x,x+bs,y,y-bs) string piece_text = utf32_to_utf8({QBNU[cp]}) integer piece = SQBN[cp+1] sequence mm = get_mm(piece), st = state[cp][bn] bool solved = st[1]=CD_DARK_GREEN -- show the solution/mt or undo[$] aka maniaical workings board = split(iff(solved or st[4]={}?st[5]:st[4][$]),'\n') for row=1 to bn do for col=1 to bn do if board[row][col]=piece then atom sx = x+col*ss-ss/2, sy = y-row*ss+ss/2 cdCanvasSetForeground(cddbuffer, CD_BLACK) cdCanvasFont(cddbuffer, "Helvetica", CD_PLAIN, fontsize*5) cdCanvasText(cddbuffer,sx,sy+iff(platform()=JS?0:5),piece_text) -- and mark all attacked squares cdCanvasFont(cddbuffer, "Helvetica", CD_PLAIN, fontsize*2) cdCanvasSetForeground(cddbuffer, CD_AMBER) sequence mnm = mm_baby(mm,piece,col,row,bn) for i=1 to length(mnm) do integer {mx,my} = mnm[i] string ac = board[my,mx]&"" cdCanvasText(cddbuffer,sx+ss*(mx-col),sy-ss*(my-row),ac) end for end if end for end for cdCanvasFlush(cddbuffer) integer m = st[2], count = st[6] string pdesc = {"Queens", "Bishops", "Knights"}[cp][1..-1-(m=1)], status = iff(solved?"solved in":"working:"), attempt = iff(count=1?"attempt":"attempts") IupSetStrAttribute(dlg,"TITLE","%s - %d %s on %dx%d %s %,d %s",{title,m,pdesc,bn,bn,status,count,attempt}) return IUP_DEFAULT end function function map_cb(Ihandle canvas) cdcanvas = cdCreateCanvas(CD_IUP, canvas) cddbuffer = cdCreateCanvas(CD_DBUFFER, cdcanvas) cdCanvasSetBackground(cddbuffer, CD_PARCHMENT) cdCanvasSetTextAlignment(cddbuffer,CD_CENTER) return IUP_DEFAULT end function function help() IupMessage(title,help_text) return IUP_IGNORE -- (don't open browser help!) end function function key_cb(Ihandle ih, atom c) if c=K_ESC then IupSetInt(timer,"RUN",false) return IUP_CLOSE end if if c=K_F5 then return IUP_DEFAULT end if -- (let browser reload work) if c=K_F1 then return help() end if integer k = find(upper(c),SQBN&"123456789T+-!") if k then if k=1 then IupSetInt(timer,"RUN",not IupGetInt(timer,"RUN")) elsif k<=4 then cp = k-1 elsif k<=14 then bn = k-4 elsif c='+' then bn = min(bn+1,maxqbn) elsif c='-' then bn = max(bn-1,1) end if bn = min(bn,length(state[cp])) IupUpdate(ih) end if return IUP_IGNORE end function function button_cb(Ihandle ih, integer button, pressed, x, y, atom /*pStatus*/) if button=IUP_BUTTON1 and pressed then -- (left button pressed) integer p = floor((x+dx/2)/dx)-36, n = floor(y/dy) if p>=1 and p<=3 and n>=1 and n<=length(state[p]) then {cp,bn} = {p,n} IupUpdate(ih) end if end if return IUP_CONTINUE end function function timer_cb(Ihandln /*ih*/) iterative_solve() IupUpdate(canvas) return IUP_IGNORE end function procedure main() IupOpen() IupSetGlobal("UTF8MODE","YES") canvas = IupGLCanvas("RASTERSIZE=640x480") IupSetCallbacks(canvas, {"ACTION", Icallback("redraw_cb"), "MAP_CB", Icallback("map_cb"), "BUTTON_CB", Icallback("button_cb")}) dlg = IupDialog(canvas,`TITLE="%s"`,{title}) IupSetCallback(dlg,"KEY_CB", Icallback("key_cb")) IupSetAttributeHandle(NULL,"PARENTDIALOG",dlg) timer = IupTimer(Icallback("timer_cb"), 30) reset() IupShow(dlg) IupSetAttribute(canvas, "RASTERSIZE", NULL) if platform()!=JS then IupMainLoop() IupClose() end if end procedure main()
Python
""" 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()
- Output:
Squares Queens Bishops Knights 1 1 1 1 4 1 2 4 9 1 3 4 16 3 4 4 25 3 5 5 36 4 6 8 49 4 7 13 64 5 8 14 81 5 9 14 100 5 10 16 Examples for N = 10: Queens: . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . Bishops: . . . . . . . . . . . . . . B B . . . . . . . . . . . . . . . . . . . . . . . . . . . . B . B . . . . . B . . . B . . . . . . B . . . . . . . . . . . . B . . . . . . . B . B . . . . . . . . . . . . . Knights: . . . . . . . . . . . . N N . . . . . . . . N N . . . N N . . . . . . . . N N . . . . . . . . . . . . . . . . . . . . . . N N . . . . . . . . N N . . . N N . . . . . . . . N N . . . . . . . . . . . .
Raku
Due to the time it's taking only a subset of the task are attempted.
# 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
}
}
}
- Output:
Queens ======= 1 x 1 : 1 2 x 2 : 1 3 x 3 : 1 4 x 4 : 3 5 x 5 : 3 6 x 6 : 4 7 x 7 : 4 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
Wren
CLI
This was originally based on the Java code here which uses a backtracking algorithm and which I extended to deal with bishops and knights as well as queens when translating to Wren. I then used the more efficient way for checking the diagonals described here and have now incorporated the improvements made to the Go version.
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.
import "./fmt" for Fmt
var board
var diag1
var diag2
var diag1Lookup
var diag2Lookup
var n
var minCount
var layout
var isAttacked = Fn.new { |piece, row, col|
if (piece == "Q") {
for (i in 0...n) {
if (board[i][col] || board[row][i]) return true
}
if (diag1Lookup[diag1[row][col]] ||
diag2Lookup[diag2[row][col]]) return true
} else if (piece == "B") {
if (diag1Lookup[diag1[row][col]] ||
diag2Lookup[diag2[row][col]]) return true
} else { // piece == "K"
if (board[row][col]) return true
if (row + 2 < n && col - 1 >= 0 && board[row + 2][col - 1]) return true
if (row - 2 >= 0 && col - 1 >= 0 && board[row - 2][col - 1]) return true
if (row + 2 < n && col + 1 < n && board[row + 2][col + 1]) return true
if (row - 2 >= 0 && col + 1 < n && board[row - 2][col + 1]) return true
if (row + 1 < n && col + 2 < n && board[row + 1][col + 2]) return true
if (row - 1 >= 0 && col + 2 < n && board[row - 1][col + 2]) return true
if (row + 1 < n && col - 2 >= 0 && board[row + 1][col - 2]) return true
if (row - 1 >= 0 && col - 2 >= 0 && board[row - 1][col - 2]) return true
}
return false
}
var 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)
}
}
var storeLayout = Fn.new { |piece|
var sb = ""
for (row in board) {
for (cell in row) sb = sb + (cell ? piece + " " : ". ")
sb = sb + "\n"
}
layout = sb
}
var placePiece // recursive function
placePiece = Fn.new { |piece, countSoFar, 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
}
}
if (!allAttacked) break
}
if (allAttacked) {
minCount = countSoFar
storeLayout.call(piece)
return
}
if (countSoFar <= maxCount) {
var si = (piece == "K") ? (ti-2).max(0) : ti
var sj = (piece == "K") ? (tj-2).max(0) : tj
for (i in si...n) {
for (j in sj...n) {
if (!isAttacked.call(piece, i, j)) {
if ((i == ti && j == tj) || attacks.call(piece, i, j, ti, tj)) {
board[i][j] = true
if (piece != "K") {
diag1Lookup[diag1[i][j]] = true
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
}
}
}
}
}
}
}
var start = System.clock
var pieces = ["Q", "B", "K"]
var limits = {"Q": 10, "B": 10, "K": 10}
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"}
for (piece in pieces) {
System.print(names[piece])
System.print("=======\n")
n = 1
while (true) {
board = List.filled(n, null)
for (i in 0...n) board[i] = List.filled(n, false)
if (piece != "K") {
diag1 = List.filled(n, null)
for (i in 0...n) {
diag1[i] = List.filled(n, 0)
for (j in 0...n) diag1[i][j] = i + j
}
diag2 = List.filled(n, null)
for (i in 0...n) {
diag2[i] = List.filled(n, 0)
for (j in 0...n) diag2[i][j] = i - j + n - 1
}
diag1Lookup = List.filled(2*n-1, false)
diag2Lookup = List.filled(2*n-1, false)
}
minCount = Num.maxSafeInteger
layout = ""
for (maxCount in 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]) {
Fmt.print("\n$s on a $d x $d board:", names[piece], n, n)
System.print("\n" + layout)
break
}
n = n + 1
}
}
System.print("Took %(System.clock - start) seconds.")
- Output:
Queens ======= 1 x 1 : 1 2 x 2 : 1 3 x 3 : 1 4 x 4 : 3 5 x 5 : 3 6 x 6 : 4 7 x 7 : 4 8 x 8 : 5 9 x 9 : 5 10 x 10 : 5 Queens on a 10 x 10 board: . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . Bishops ======= 1 x 1 : 1 2 x 2 : 2 3 x 3 : 3 4 x 4 : 4 5 x 5 : 5 6 x 6 : 6 7 x 7 : 7 8 x 8 : 8 9 x 9 : 9 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 1276.522608 seconds.
Embedded
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.
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.")
- Output:
Queens ======= 1 x 1 : 1 2 x 2 : 1 3 x 3 : 1 4 x 4 : 3 5 x 5 : 3 6 x 6 : 4 7 x 7 : 4 8 x 8 : 5 9 x 9 : 5 10 x 10 : 5 Queens on a 10 x 10 board: . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . Bishops ======= 1 x 1 : 1 2 x 2 : 2 3 x 3 : 3 4 x 4 : 4 5 x 5 : 5 6 x 6 : 6 7 x 7 : 7 8 x 8 : 8 9 x 9 : 9 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.