N-queens minimum and knights and bishops: Difference between revisions
m (→{{header|J}}: fix broken state space pruning mechanism) |
m (use Cbc optimizer only) |
||
Line 458: | Line 458: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Uses the |
Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support. |
||
<lang ruby>""" Rosetta code task N-queens_minimum_and_knights_and_bishops """ |
<lang ruby>""" Rosetta code task N-queens_minimum_and_knights_and_bishops """ |
||
import HiGHS |
|||
import Cbc |
import Cbc |
||
using JuMP |
using JuMP |
||
Line 482: | Line 481: | ||
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 511: | ||
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 586: | Line 585: | ||
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: |
Revision as of 05:10, 28 April 2022
N-Queens: you've been there; done that; have the T-shirt. It is time to find the minimum number of Queens, Bishops or Knights that can be placed on an NxN board such that no piece attacks another but every unoccupied square is attacked.
For N=1 to 10 discover the minimum number of Queens, Bishops, and Knights required to fulfill the above requirement. For N=8 print out a possible solution for Queens and Bishops.
F#
<lang fsharp> // N-Queens minimum and Knights and Bishops. Nigel Galloway: April 19th., 2022
open Microsoft.SolverFoundation.Services
open Microsoft.SolverFoundation.Common
let fN n g l=([0..n-1]@[n+1..l-1]|>List.map(fun n->sprintf "N_%02d_%02d" n g))@([0..g-1]@[g+1..l-1]|>List.map(fun g->sprintf "N_%02d_%02d" n g)) let fG n g l=List.unfold(fun(n,g)->if n>l-2||g>l-2 then None else let n,g=n+1,g+1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)@
List.unfold(fun(n,g)->if n<1||g>l-2 then None else let n,g=n-1,g+1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)@ List.unfold(fun(n,g)->if n<1||g<1 then None else let n,g=n-1,g-1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)@ List.unfold(fun(n,g)->if n>l-2||g<1 then None else let n,g=n+1,g-1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)
let fK n g l=[(1,-2);(2,-1);(1,2);(2,1);(-1,2);(-2,1);(-1,-2);(-2,-1)]|>List.choose(fun(x,y)->match n+x,g+y with p,q when p>=0 && q>=0 && p<=l-1 && q<=l-1->Some(sprintf "N_%02d_%02d" p q) |_->None) let sln f size=
let context=SolverContext.GetContext() context.ClearModel() let model=context.CreateModel() for n in 0..size-1 do for g in 0..size-1 do model.AddDecision(new Decision(Domain.IntegerRange(Rational.Zero,Rational.One), sprintf "N_%02d_%02d" n g)) for n in 0..size-1 do for g in 0..size-1 do model.AddConstraint(sprintf "G_%02d_%02d" n g,([sprintf "0<%d*N_%02d_%02d" (size*size) n g]@f n g size|>String.concat "+")+sprintf "<%d" (size*size+1)) model.AddGoal("Goal0", GoalKind.Minimize, [for n in 0..size-1 do for g in 0..size-1->sprintf "N_%02d_%02d" n g]|>String.concat "+") context.Solve()
let Bishops,Queens,Knights=sln fG, sln (fun n g l->fG n g l@fN n g l), sln fK let printSol(n:Solution)=n.Decisions|>Seq.filter(fun n->n.GetDouble()=1.0)|>Seq.iteri(fun n g->let g=g.Name in printfn "Place Piece %d in row %d column %d" (n+1) (int(g.[2..3])) (int(g.[5..6]))); printfn "" let pieces(n:Solution)=n.Decisions|>Seq.filter(fun n->n.GetDouble()=1.0)|>Seq.length
printfn "%10s%10s%10s%10s" "Squares" "Queens" "Bishops" "Knights" [1..10]|>List.iter(fun n->printfn "%10d%10d%10d%10d" (n*n) (pieces(Queens n)) (pieces(Bishops n)) (pieces(Knights n))) printfn "Queens on a 8x8 Board"; printSol(Queens 8) printfn "Knights on a 8x8 Board"; printSol(Knights 8) </lang>
- Output:
Squares Queens Bishops Knights 1 1 1 1 4 1 2 4 9 1 3 4 16 3 4 4 25 3 5 5 36 4 6 8 49 4 7 13 64 5 8 14 81 5 9 14 100 5 10 16 Queens on a 8x8 Board Place Piece 1 in row 0 column 4 Place Piece 2 in row 3 column 0 Place Piece 3 in row 4 column 7 Place Piece 4 in row 6 column 1 Place Piece 5 in row 7 column 3 Knights on a 8x8 Board Place Piece 1 in row 0 column 0 Place Piece 2 in row 0 column 3 Place Piece 3 in row 1 column 0 Place Piece 4 in row 2 column 0 Place Piece 5 in row 2 column 5 Place Piece 6 in row 2 column 6 Place Piece 7 in row 3 column 5 Place Piece 8 in row 4 column 2 Place Piece 9 in row 5 column 1 Place Piece 10 in row 5 column 2 Place Piece 11 in row 5 column 7 Place Piece 12 in row 6 column 7 Place Piece 13 in row 7 column 4 Place Piece 14 in row 7 column 7
Go
Much quicker, of course, than Wren itself - only takes about 35 seconds to run when using the same board limits.
However, it struggles as soon as you try to increase the board sizes for bishops or knights. When you try 7 x 7 for bishops (as the code below does) the run time shoots up to almost 5.5 minutes. <lang go>package main
import (
"fmt" "math" "strings"
)
var board [][]bool var diag1, diag2 [][]int var diag1Lookup, diag2Lookup []bool var n, minCount int var layout string
func isAttacked(piece string, row, col int) bool {
if piece == "Q" { for i := 0; i < n; i++ { if board[i][col] || board[row][i] { return true } } if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] { return true } } else if piece == "B" { if board[row][col] { return true } if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] { return true } } else { // piece == "K" if board[row][col] { return true } if row+2 < n && col-1 >= 0 && board[row+2][col-1] { return true } if row-2 >= 0 && col-1 >= 0 && board[row-2][col-1] { return true } if row+2 < n && col+1 < n && board[row+2][col+1] { return true } if row-2 >= 0 && col+1 < n && board[row-2][col+1] { return true } if row+1 < n && col+2 < n && board[row+1][col+2] { return true } if row-1 >= 0 && col+2 < n && board[row-1][col+2] { return true } if row+1 < n && col-2 >= 0 && board[row+1][col-2] { return true } if row-1 >= 0 && col-2 >= 0 && board[row-1][col-2] { return true } } return false
}
func storeLayout(piece string) {
var sb strings.Builder for _, row := range board { for _, cell := range row { if cell { sb.WriteString(piece + " ") } else { sb.WriteString(". ") } } sb.WriteString("\n") } layout = sb.String()
}
func placePiece(piece string, countSoFar int) {
if countSoFar >= minCount { return } allAttacked := true for i := 0; i < n; i++ { for j := 0; j < n; j++ { if !isAttacked(piece, i, j) { allAttacked = false break } } if !allAttacked { break } } if allAttacked { minCount = countSoFar storeLayout(piece) return }
for i := 0; i < n; i++ { for j := 0; j < n; j++ { if !isAttacked(piece, i, j) { board[i][j] = true diag1Lookup[diag1[i][j]] = true diag2Lookup[diag2[i][j]] = true placePiece(piece, countSoFar+1) board[i][j] = false diag1Lookup[diag1[i][j]] = false diag2Lookup[diag2[i][j]] = false } } }
}
func main() {
pieces := []string{"Q", "B", "K"} limits := map[string]int{"Q": 10, "B": 7, "K": 5} names := map[string]string{"Q": "Queens", "B": "Bishops", "K": "Knights"} for _, piece := range pieces { fmt.Println(names[piece]) fmt.Println("=======\n")
for n = 1; ; n++ { board = make([][]bool, n) for i := 0; i < n; i++ { board[i] = make([]bool, n) } diag1 = make([][]int, n) for i := 0; i < n; i++ { diag1[i] = make([]int, n) for j := 0; j < n; j++ { diag1[i][j] = i + j } } diag2 = make([][]int, n) for i := 0; i < n; i++ { diag2[i] = make([]int, n) for j := 0; j < n; j++ { diag2[i][j] = i - j + n - 1 } } diag1Lookup = make([]bool, 2*n-1) diag2Lookup = make([]bool, 2*n-1) minCount = math.MaxInt32 layout = "" placePiece(piece, 0) fmt.Printf("%2d x %-2d : %d\n", n, n, minCount) if n == limits[piece] { fmt.Printf("\n%s on a %d x %d board:\n", names[piece], n, n) fmt.Println("\n" + layout) break } } }
}</lang>
- Output:
Queens ======= 1 x 1 : 1 2 x 2 : 1 3 x 3 : 1 4 x 4 : 3 5 x 5 : 3 6 x 6 : 4 7 x 7 : 4 8 x 8 : 5 9 x 9 : 5 10 x 10 : 5 Queens on a 10 x 10 board: . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . Bishops ======= 1 x 1 : 1 2 x 2 : 2 3 x 3 : 3 4 x 4 : 4 5 x 5 : 5 6 x 6 : 6 7 x 7 : 7 Bishops on a 7 x 7 board: . B . B . . . . . . B . . . . . . . . . . . . B B . . . . . . . . . . . . B B . . . . . . . . . . Knights ======= 1 x 1 : 1 2 x 2 : 4 3 x 3 : 4 4 x 4 : 4 5 x 5 : 5 Knights on a 5 x 5 board: K . . . . . . . . . . . K K . . . K K . . . . . .
J
A crude initial attempt -- brute force search with some minor state space pruning. I am not patient enough to run this for 9x9 and 10x10 boards for bishops and knights:
<lang J>genboard=: {{
safelen=:2*len=. {.y shape=: 2$len board=: shape$0 safeshape=: 2*shape 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
}}
place=: Template:N=.
place1=: {{
r=. (n+2) {.!._ x N=. n todo=. (,0=y)#c lim=. >./,(first +&{: x)+m for_open. (#~ lim>:]) todo do. board=. y>.coords e.m+open if. 0 e.,board do. if. N>#x do. seq=. (x,open) m place1 N board if. N>:#seq do. N=. <:#r=. seq end. end. else. x,open return. end. end. r
}}
task=: {{
Q=:K=:B=:i.0 for_order.1+i.10 do. genboard order Q=: '.Q'{~coords e.q=. place queen K=: '.K'{~coords e.k=. place knight B=: '.B'{~coords e.b=. place bishop echo (":Q;B;K),&.|:>(' Q: ',":#q);(' B: ',":#b);' K: ',":#k end.
}}</lang>
Task output:
<lang J>
task
┌─┬─┬─┐ Q: 1 │Q│B│K│ B: 1 └─┴─┴─┘ K: 1 ┌──┬──┬──┐ Q: 1 │Q.│BB│KK│ B: 2 │..│..│KK│ K: 4 └──┴──┴──┘ ┌───┬───┬───┐ Q: 1 │...│...│KKK│ B: 3 │.Q.│BBB│.K.│ K: 4 │...│...│...│ └───┴───┴───┘ ┌────┬────┬────┐ Q: 3 │Q...│....│....│ B: 4 │..Q.│BBBB│KKKK│ K: 4 │....│....│....│ │.Q..│....│....│ └────┴────┴────┘ ┌─────┬─────┬─────┐ Q: 3 │Q....│B.B..│K....│ B: 5 │...Q.│..B..│.....│ K: 5 │.....│.....│..KK.│ │..Q..│.BB..│..KK.│ │.....│.....│.....│ └─────┴─────┴─────┘ ┌──────┬──────┬──────┐ Q: 4 │Q.....│B..B..│K....K│ B: 6 │..Q...│...B..│......│ K: 8 │.....Q│...B..│..KK..│ │......│......│..KK..│ │......│..BB..│......│ │.Q....│......│K....K│ └──────┴──────┴──────┘ ┌───────┬───────┬───────┐ Q: 4 │.......│.......│KKKK.K.│ B: 7 │.Q.....│B.BBB..│.......│ K: 13 │....Q..│.......│.....K.│ │.......│...B...│K....K.│ │.......│.......│.......│ │Q......│..BB...│K.KK.K.│ │...Q...│.......│......K│ └───────┴───────┴───────┘ ┌────────┬────────┬────────┐ Q: 5 │Q.......│........│KKK.....│ B: 8 │..Q.....│B..BBB..│.....K..│ K: 14 │....Q...│........│....KK..│ │.Q......│....B...│K.......│ │...Q....│....B...│.......K│ │........│........│..KK...K│ │........│...BB...│..K.....│ │........│........│.....K.K│ └────────┴────────┴────────┘ |attention interrupt: place</lang>
For 9 and 10 for queens: <lang J> (":<'.Q'{~coords e. q),&.|:,:' Q: ',":#q=. place queen [(genboard 9) ┌─────────┐ Q: 5 │Q........│ │..Q......│ │......Q..│ │.........│ │.........│ │.Q.......│ │.....Q...│ │.........│ │.........│ └─────────┘
(":<'.Q'{~coords e. q),&.|:,:' Q: ',":#q=. place queen [(genboard 10)
┌──────────┐ Q: 6 │Q.........│ │..Q.......│ │........Q.│ │..........│ │..........│ │...Q......│ │.........Q│ │..........│ │.....Q....│ │..........│ └──────────┘ </lang>
Julia
Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support. <lang ruby>""" Rosetta code task N-queens_minimum_and_knights_and_bishops """
import Cbc using JuMP using LinearAlgebra
""" Make a printable string from a matrix of zeros and ones using a char ch for 1, a period for !=1. """ function smatrix(x, n, ch)
s = "" for i in 1:n, j in 1:n s *= lpad(x[i, j] == 1 ? "$ch" : ".", 2) * (j == n ? "\n" : "") end return s
end
""" N-queens minimum, oeis.org/A075458 """ function queensminimum(N, char = "Q")
if N < 4 a = zeros(Int, N, N) a[N ÷ 2 + 1, N ÷ 2 + 1] = 1 return 1, smatrix(a, N, char) end model = Model(Cbc.Optimizer) @variable(model, x[1:N, 1:N], Bin)
for i in 1:N @constraint(model, sum(x[i, :]) <= 1) @constraint(model, sum(x[:, i]) <= 1) end for i in -(N - 1):(N-1) @constraint(model, sum(diag(x, i)) <= 1) @constraint(model, sum(diag(reverse(x, dims = 1), i)) <= 1) end for i in 1:N, j in 1:N @constraint(model, sum(x[i, :]) + sum(x[:, j]) + sum(diag(x, j - i)) + sum(diag(rotl90(x), N - j - i + 1)) >= 1) end
set_silent(model) @objective(model, Min, sum(x)) optimize!(model)
solution = round.(Int, value.(x)) minresult = sum(solution) return minresult, smatrix(solution, N, char)
end
""" N-bishops minimum, same as N """ function bishopsminimum(N, char = "B")
N == 1 && return 1, "$char" N == 2 && return 2, "$char .\n$char .\n"
model = Model(Cbc.Optimizer) @variable(model, x[1:N, 1:N], Bin)
for i in 1:N, j in 1:N @constraint(model, sum(diag(x, j - i)) + sum(diag(rotl90(x), N - j - i + 1)) >= 1) end
set_silent(model) @objective(model, Min, sum(x)) optimize!(model)
solution = round.(Int, value.(x)) minresult = sum(solution) return minresult, smatrix(solution, N, char)
end
""" N-knights minimum, oeis.org/A342576 """ function knightsminimum(N, char = "N")
N < 2 && return 1, "$char"
knightdeltas = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
model = Model(Cbc.Optimizer)
# to simplify the constraints, embed the board of size N inside a board of size n + 4 @variable(model, x[1:N+4, 1:N+4], Bin)
@constraint(model, x[:, 1:2] .== 0) @constraint(model, x[1:2, :] .== 0) @constraint(model, x[:, N+3:N+4] .== 0) @constraint(model, x[N+3:N+4, :] .== 0)
for i in 3:N+2, j in 3:N+2 @constraint(model, x[i, j] + sum(x[i + d[1], j + d[2]] for d in knightdeltas) >= 1) @constraint(model, x[i, j] => {sum(x[i + d[1], j + d[2]] for d in knightdeltas) == 0}) end
set_silent(model) @objective(model, Min, sum(x)) optimize!(model)
solution = round.(Int, value.(x)) minresult = sum(solution) return minresult, smatrix(solution[3:N+2, 3:N+2], N, char)
end
const examples = fill("", 3) println(" Squares Queens Bishops Knights") @time for N in 1:10
print(lpad(N^2, 10)) i, examples[1] = queensminimum(N) print(lpad(i, 10)) i, examples[2] = bishopsminimum(N) print(lpad(i, 10)) i, examples[3] = knightsminimum(N) println(lpad(i, 10))
end
println("\nExamples for N = 10:\n\nQueens:\n", examples[1], "\nBishops:\n", examples[2],
"\nKnights:\n", examples[3])
</lang>
- Output:
Squares Queens Bishops Knights 1 1 1 1 4 1 2 4 9 1 3 4 16 3 4 4 25 3 5 5 36 4 6 8 49 4 7 13 64 5 8 14 81 5 9 14 100 5 10 16 49.922920 seconds (30.87 M allocations: 1.656 GiB, 2.39% gc time, 65.49% compilation time) Examples for N = 10: Queens: . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . Bishops: . . . . . . . . . . . . . . . B . . . . . . . . . B . . . . . B . . . . . . . . . B . . . . B . . . . . . . . . B . . . . . B . . . B . . . . . . . . . B . . . . B . . . . . . . . . . . . . . . . . . Knights: . . . . . . . . . . . . N N . . . . . . . . N N . . . N N . . . . . . . . N N . . . . . . . . . . . . . . . . . . . . . . N N . . . . . . . . N N . . . N N . . . . . . . . N N . . . . . . . . . . . .
Pascal
Free Pascal
At bishops I used a trick that at max only one row is left free. <lang pascal>program TestMinimalQueen; {$MODE DELPHI}{$OPTIMIZATION ON,ALL}
uses
sysutils;
const
KoorCOUNT = 16;
type
tLimit = 0..KoorCOUNT-1;
tPlayGround = array[tLimit,tLimit] of byte; tCheckPG = array[0..KoorCOUNT] of tplayGround; tpPlayGround = ^tPlayGround;
var {$ALIGN 32}
CPG :tCheckPG; Qsol,BSol,KSol :tPlayGround; pgIdx,minIdx : nativeInt; jumpedOver : boolean;
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; row,col: NativeInt;
Begin
pPG := @CPG[pgIdx]; For row := lmt downto 0 do For col := lmt downto 0 do if pPG^[row,col] = 0 then EXIT(false); exit(true);
end;
procedure SetQueen(row,lmt: NativeInt); var
pPG :tpPlayGround; i,col,t: NativeInt;
begin
if pgIdx = minIDX then EXIT; inc(pgIdx); //check every column For col := 0 to lmt do begin //copy last state CPG[pgIdx]:=CPG[pgIdx-1]; pPG := @CPG[pgIdx]; if pPG^[row,col] <> 0 then continue;
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; //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); end; dec(pgIdx);
end;
procedure SetBishop(row,lmt: NativeInt); var
pPG :tpPlayGround; col,t: NativeInt;
begin
if pgIdx = minIDX then EXIT; inc(pgIdx); For col := 0 to lmt do begin CPG[pgIdx]:=CPG[pgIdx-1]; 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 next row t := row+1; if (t <= lmt) then begin SetBishop(t,lmt); //left out max one row on field if jumpedOver then Begin inc(t); jumpedOver := false; if t <= lmt then SetBishop(t,lmt); jumpedOver := true; end; end; end; 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 := 2*(lmt+1); jumpedOver := true; setQueen(0,lmt); write(minIDX:3); end; writeln;
write(' Bishop :'); For lmt := 0 to max-1 do begin pgIdx := 0; minIdx := 2*(lmt+1); jumpedOver := true; setBishop(0,lmt); write(minIDX:3); end; writeln; pG_Out(@Qsol,'_.Q',max-1); writeln; pG_Out(@Bsol,'_.B',max-1);
END.</lang>
- @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: 4.740 s CPU share: 99.06 %
Phix
You can run this online here, and explore the finished (green) ones while it toils away on the tougher ones, or watch it working. It examines 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.
-- -- demo\rosetta\minQBN.exw -- ======================= -- with javascript_semantics include pGUI.e constant title = "Minimum QBN", help_text = """ Finds the minimum number of Queens, Bishops, and 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 maniacal 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. """ sequence board constant qm = {{-1,0},{0,-1}, {+1,0},{0,+1}}, bm = {{-1,-1},{-1,+1}, {+1,-1},{+1,+1}}, 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&bm 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]=' ' then res &= {{mx,my}} end if end for if row=1 and col=1 and n>1 and piece='B' then -- first bishop must be on the diagonal: -- if we don't find an answer up to the -- mid-point, we won't find one after. assert(length(res)=n) -- sanity check res = res[1..ceil(length(res)/2)] end if return res end function procedure move(sequence rc, integer piece, n) integer {row,col} = rc board[row][col] = piece sequence mm = mm_baby(get_mm(piece),piece,row,col,n) for i=1 to length(mm) do integer {mx,my} = mm[i] board[mx][my] = '+' end for end procedure Ihandle dlg, canvas, timer cdCanvas cddbuffer, cdcanvas constant QBN = utf8_to_utf32("♕♗♘") integer bn = 8, -- chosen board is nxn (1..10) cp = 1 -- piece (1,2,3 for QBN) sequence state procedure reset() state = repeat(repeat(0,10),3) for piece=1 to 3 do for n=1 to 10 do atom scolour = CD_RED board = repeat(repeat(' ',n),n) sequence moves = get_moves("QBN"[piece],n,1,1) string undo = join(board,'\n') state[piece][n] = {scolour,1,{moves},{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 10 do for pdx=1 to 3 do if 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 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 = "QBN"[p], 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]=' ' 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(' ',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/11 -- 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 10 do atom lx = dx*36 for j=0 to 3 do string txt = iff(i=0?" QBN"[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) 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({QBN[cp]}) integer piece = "QBN"[cp] sequence mm = get_mm(piece), st = state[cp][bn] bool solved = st[1]=CD_DARK_GREEN board = split(iff(solved?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] cdCanvasText(cddbuffer,sx+ss*(mx-col),sy-ss*(my-row),"+") 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_DEFAULT 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=' ' then IupSetInt(timer,"RUN",not IupGetInt(timer,"RUN")) end if if c=K_F1 then return help() end if integer k = find(upper(c),"QBN123456789T+-!") if k then if k<=3 then cp = k elsif k<=13 then bn = k-3 elsif c='+' then bn = min(bn+1,10) elsif c='-' then bn = max(bn-1,1) end if IupUpdate(ih) end if return IUP_IGNORE end function function button_cb(Ihandle ih, integer button, pressed, x, y, atom /*pStatus*/) if button=IUP_BUTTON1 and pressed then -- (left button pressed) integer p = floor((x+dx/2)/dx)-36, n = floor(y/dy) if p>0 and p<4 and n>0 then {cp,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()
Wren
Although this seems to work and give the correct answers, it's very slow taking about 23.5 minutes to run even when the board sizes are limited to 6 x 6 (bishops) and 5 x 5 (knights).
It's based on the Java code here which uses a backtracking algorithm and which I extended to deal with bishops and knights as well as queens when translating to Wren. I've used the more efficient way for checking the diagonals described here. <lang ecmascript>import "./fmt" for Fmt
var board var diag1 var diag2 var diag1Lookup var diag2Lookup var n var minCount var layout
var isAttacked = Fn.new { |piece, row, col|
if (piece == "Q") { for (i in 0...n) { if (board[i][col] || board[row][i]) return true } if (diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]]) return true } else if (piece == "B") { if (board[row][col]) return true if (diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]]) return true } else { // piece == "K" if (board[row][col]) return true if (row + 2 < n && col - 1 >= 0 && board[row + 2][col - 1]) return true if (row - 2 >= 0 && col - 1 >= 0 && board[row - 2][col - 1]) return true if (row + 2 < n && col + 1 < n && board[row + 2][col + 1]) return true if (row - 2 >= 0 && col + 1 < n && board[row - 2][col + 1]) return true if (row + 1 < n && col + 2 < n && board[row + 1][col + 2]) return true if (row - 1 >= 0 && col + 2 < n && board[row - 1][col + 2]) return true if (row + 1 < n && col - 2 >= 0 && board[row + 1][col - 2]) return true if (row - 1 >= 0 && col - 2 >= 0 && board[row - 1][col - 2]) return true } return false
}
var storeLayout = Fn.new { |piece|
var sb = "" for (row in board) { for (cell in row) sb = sb + (cell ? piece + " " : ". ") sb = sb + "\n" } layout = sb
}
var placePiece // recursive function placePiece = Fn.new { |piece, countSoFar|
if (countSoFar >= minCount) return var allAttacked = true for (i in 0...n) { for (j in 0...n) { if (!isAttacked.call(piece, i, j)) { allAttacked = false break } } if (!allAttacked) break } if (allAttacked) { minCount = countSoFar storeLayout.call(piece) return } for (i in 0...n) { for (j in 0...n) { if (!isAttacked.call(piece, i, j)) { board[i][j] = true diag1Lookup[diag1[i][j]] = true diag2Lookup[diag2[i][j]] = true placePiece.call(piece, countSoFar + 1) board[i][j] = false diag1Lookup[diag1[i][j]] = false diag2Lookup[diag2[i][j]] = false } } }
}
var pieces = ["Q", "B", "K"] var limits = {"Q": 10, "B": 6, "K": 5} var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"} for (piece in pieces) {
System.print(names[piece]) System.print("=======\n") n = 1 while (true) { board = List.filled(n, null) for (i in 0...n) board[i] = List.filled(n, false) diag1 = List.filled(n, null) for (i in 0...n) { diag1[i] = List.filled(n, 0) for (j in 0...n) diag1[i][j] = i + j } diag2 = List.filled(n, null) for (i in 0...n) { diag2[i] = List.filled(n, 0) for (j in 0...n) diag2[i][j] = i - j + n - 1 } diag1Lookup = List.filled(2*n-1, false) diag2Lookup = List.filled(2*n-1, false) minCount = Num.maxSafeInteger layout = "" placePiece.call(piece, 0) Fmt.print("$2d x $-2d : $d", n, n, minCount) if (n == limits[piece]) { Fmt.print("\n$s on a $d x $d board:", names[piece], n, n) System.print("\n" + layout) break } n = n + 1 }
}</lang>
- Output:
Queens ======= 1 x 1 : 1 2 x 2 : 1 3 x 3 : 1 4 x 4 : 3 5 x 5 : 3 6 x 6 : 4 7 x 7 : 4 8 x 8 : 5 9 x 9 : 5 10 x 10 : 5 Queens on a 10 x 10 board: . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . Bishops ======= 1 x 1 : 1 2 x 2 : 2 3 x 3 : 3 4 x 4 : 4 5 x 5 : 5 6 x 6 : 6 Bishops on a 6 x 6 board: B . . B . . . . . B . . . . . B . . . . . . . . . . B B . . . . . . . . Knights ======= 1 x 1 : 1 2 x 2 : 4 3 x 3 : 4 4 x 4 : 4 5 x 5 : 5 Knights on a 5 x 5 board: K . . . . . . . . . . . K K . . . K K . . . . . .
If I limit the board size for the queens to 8 x 8, the run time comes down to around 2 minutes 12 seconds and the following example layout is produced:
Queens on a 8 x 8 board: Q . . . . . . . . . Q . . . . . . . . . Q . . . . Q . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . .