N-queens minimum and knights and bishops
N-Queens: you've been there; done that; have the T-shirt. It is time to find the minimum number of Queens, Bishops or Knights that can be placed on an NxN board such that no piece attacks another but every unoccupied square is attacked.
For N=1 to 10 discover the minimum number of Queens, Bishops, and Knights required to fulfill the above requirement. For N=8 print out a possible solution for Queens and Bishops.
F#
<lang fsharp> // N-Queens minimum and Knights and Bishops. Nigel Galloway: April 19th., 2022
open Microsoft.SolverFoundation.Services
open Microsoft.SolverFoundation.Common
let fN n g l=([0..n-1]@[n+1..l-1]|>List.map(fun n->sprintf "N_%02d_%02d" n g))@([0..g-1]@[g+1..l-1]|>List.map(fun g->sprintf "N_%02d_%02d" n g)) let fG n g l=List.unfold(fun(n,g)->if n>l-2||g>l-2 then None else let n,g=n+1,g+1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)@
List.unfold(fun(n,g)->if n<1||g>l-2 then None else let n,g=n-1,g+1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)@
List.unfold(fun(n,g)->if n<1||g<1 then None else let n,g=n-1,g-1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)@
List.unfold(fun(n,g)->if n>l-2||g<1 then None else let n,g=n+1,g-1 in Some(sprintf "N_%02d_%02d" n g,(n,g)))(n,g)
let fK n g l=[(1,-2);(2,-1);(1,2);(2,1);(-1,2);(-2,1);(-1,-2);(-2,-1)]|>List.choose(fun(x,y)->match n+x,g+y with p,q when p>=0 && q>=0 && p<=l-1 && q<=l-1->Some(sprintf "N_%02d_%02d" p q) |_->None) let sln f size=
let context=SolverContext.GetContext()
context.ClearModel()
let model=context.CreateModel()
for n in 0..size-1 do for g in 0..size-1 do model.AddDecision(new Decision(Domain.IntegerRange(Rational.Zero,Rational.One), sprintf "N_%02d_%02d" n g))
for n in 0..size-1 do for g in 0..size-1 do model.AddConstraint(sprintf "G_%02d_%02d" n g,([sprintf "0<%d*N_%02d_%02d" (size*size) n g]@f n g size|>String.concat "+")+sprintf "<%d" (size*size+1))
model.AddGoal("Goal0", GoalKind.Minimize, [for n in 0..size-1 do for g in 0..size-1->sprintf "N_%02d_%02d" n g]|>String.concat "+")
context.Solve()
let Bishops,Queens,Knights=sln fG, sln (fun n g l->fG n g l@fN n g l), sln fK let printSol(n:Solution)=n.Decisions|>Seq.filter(fun n->n.GetDouble()=1.0)|>Seq.iteri(fun n g->let g=g.Name in printfn "Place Piece %d in row %d column %d" (n+1) (int(g.[2..3])) (int(g.[5..6]))); printfn "" let pieces(n:Solution)=n.Decisions|>Seq.filter(fun n->n.GetDouble()=1.0)|>Seq.length
printfn "%10s%10s%10s%10s" "Squares" "Queens" "Bishops" "Knights" [1..10]|>List.iter(fun n->printfn "%10d%10d%10d%10d" (n*n) (pieces(Queens n)) (pieces(Bishops n)) (pieces(Knights n))) printfn "Queens on a 8x8 Board"; printSol(Queens 8) printfn "Knights on a 8x8 Board"; printSol(Knights 8) </lang>
- Output:
Squares Queens Bishops Knights
1 1 1 1
4 1 2 4
9 1 3 4
16 3 4 4
25 3 5 5
36 4 6 8
49 4 7 13
64 5 8 14
81 5 9 14
100 5 10 16
Queens on a 8x8 Board
Place Piece 1 in row 0 column 4
Place Piece 2 in row 3 column 0
Place Piece 3 in row 4 column 7
Place Piece 4 in row 6 column 1
Place Piece 5 in row 7 column 3
Knights on a 8x8 Board
Place Piece 1 in row 0 column 0
Place Piece 2 in row 0 column 3
Place Piece 3 in row 1 column 0
Place Piece 4 in row 2 column 0
Place Piece 5 in row 2 column 5
Place Piece 6 in row 2 column 6
Place Piece 7 in row 3 column 5
Place Piece 8 in row 4 column 2
Place Piece 9 in row 5 column 1
Place Piece 10 in row 5 column 2
Place Piece 11 in row 5 column 7
Place Piece 12 in row 6 column 7
Place Piece 13 in row 7 column 4
Place Piece 14 in row 7 column 7
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=. (#~ ({:x) < ]) (,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
echo label=. ' order queens bishops knights'
L=.1+#@>;:label
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....¦K....¦ B: 5 ¦...Q.¦..BB.¦.....¦ K: 5 ¦.....¦B....¦..KK.¦ ¦..Q..¦..B..¦..KK.¦ ¦.....¦.....¦.....¦ +-----------------+ +--------------------+ Q: 4 ¦Q.....¦B.....¦......¦ B: 6 ¦.....Q¦..BBB.¦......¦ K: 8 ¦.Q....¦......¦KK..KK¦ ¦......¦......¦KK..KK¦ ¦......¦..BB..¦......¦ ¦..Q...¦......¦......¦ +--------------------+ +-----------------------+ Q: 5 ¦Q......¦.......¦KKKK.K.¦ B: 7 ¦..Q....¦B.BBB..¦.......¦ K: 13 ¦....Q..¦.......¦.....K.¦ ¦.Q.....¦...B...¦K....K.¦ ¦...Q...¦.......¦.......¦ ¦.......¦..BB...¦K.KK.K.¦ ¦.......¦.......¦......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. place q),&.|:,:' Q: ',":#q=. queen [(genboard 9) ┌─────────┐ Q: 65 │Q........│ │..Q......│ │......Q..│ │.........│ │.........│ │.Q.......│ │.....Q...│ │.........│ │.........│ └─────────┘
(":<'.Q'{~coords e. place q),&.|:,:' Q: ',":#q=. queen [(genboard 10)
┌──────────┐ Q: 73 │Q.........│ │..Q.......│ │........Q.│ │..........│ │..........│ │...Q......│ │.........Q│ │..........│ │.....Q....│ │..........│ └──────────┘ </lang>
Pascal
Free Pascal
<lang pascal> program TestMinimalQueen;
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; sol :tPlayGround; pgIdx,minIdx : nativeInt;
procedure pG_Out(pSol:tpPlayGround;lmt: NativeInt); const
ConvChar = '_.Q';
var
row,col: NativeInt;
begin
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; 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);
For col := 0 to lmt do
begin
CPG[pgIdx]:=CPG[pgIdx-1];
if CPG[pgIdx][row,col] <> 0 then
continue;
CPG[pgIdx]:=CPG[pgIdx-1];
RightAscDia(row,col,lmt);
LeftAscDia(row,col,lmt);
pPG := @CPG[pgIdx];
For i := 0 to lmt do
Begin
pPG^[row,i] := 1;
pPG^[i,col] := 1;
end;
pPG^[row,col] := 2;
if check(lmt) then
begin
if minIdx> pgIdx then
begin
minIdx := pgIdx;
sol := CPG[pgIdx];
end;
end
else
if row > lmt then
BREAK
else
For t := row+1 to lmt do
SetQueen(t,lmt);
end;
dec(pgIdx);
end;
var
lmt : NativeInt;
BEGIN
For lmt := 0 to 11 do begin pgIdx := 0; minIdx := 2*(lmt+1); setQueen(0,lmt); writeln(lmt+1:3,minIDX:3);
// pG_Out(@sol,lmt);
end; pG_Out(@sol,lmt);
END.</lang>
- @TIO.RUN:
nxn min. queens 1 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 5 11 6 //Real time: 3.241 s 12 7 .Q.......... ............ ........Q... ............ ...Q........ ............ ............ ..........Q. ............ .....Q...... ..Q......... Q........... Real time: 45.856 s CPU share: 99.24 % // below the time limit of 60 secs
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . .