N-queens minimum and knights and bishops: Difference between revisions
N-queens minimum and knights and bishops (view source)
Revision as of 09:07, 6 January 2024
, 4 months ago→{{header|Wren}}: Changed to Wren S/H
(→{{header|Phix}}: updated, much faster) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
(21 intermediate revisions by 8 users not shown) | |||
Line 4:
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#}}==
<
//
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
</syntaxhighlight>
{{out}}
<pre>
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~.~.~.
.~.~.~.~.~
</pre>
=={{header|Go}}==
This was originally a translation of the Wren entry but was substantially improved by [[User:Petelomax|Pete Lomax]] using suggestions from the talk page and has been improved further since then, resulting in an overall execution time of about 22.4 seconds.
Timing is for an Intel Core i7-8565U machine running Ubuntu 20.04.
<
import (
Line 85 ⟶ 137:
"math"
"strings"
"time"
)
Line 104 ⟶ 157:
}
} else if piece == "B" {
if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] {
return true
Line 140 ⟶ 190:
}
return false
}
func abs(i int) int {
if i < 0 {
i = -i
}
return i
}
func attacks(piece string, row, col, trow, tcol int) bool {
if piece == "Q" {
return row == trow || col == tcol || abs(row-trow) == abs(col-tcol)
} else if piece == "B" {
return abs(row-trow) == abs(col-tcol)
} else { // piece == "K"
rd := abs(trow - row)
cd := abs(tcol - col)
return (rd == 1 && cd == 2) || (rd == 2 && cd == 1)
}
}
Line 157 ⟶ 226:
}
func placePiece(piece string, countSoFar, maxCount int) {
if countSoFar >= minCount {
return
}
allAttacked := true
ti := 0
tj := 0
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if !isAttacked(piece, i, j) {
allAttacked = false
ti = i
tj = j
break
}
Line 178 ⟶ 251:
return
}
if countSoFar <= maxCount {
si = si -
sj = sj -
if si < 0
if 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 195 ⟶ 287:
func main() {
start := time.Now()
pieces := []string{"Q", "B", "K"}
limits := map[string]int{"Q": 10, "B":
names := map[string]string{"Q": "Queens", "B": "Bishops", "K": "Knights"}
for _, piece := range pieces {
Line 207 ⟶ 300:
board[i] = make([]bool, n)
}
diag1[i][j] = i + j
}
}
}
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] {
Line 234 ⟶ 334:
}
}
elapsed := time.Now().Sub(start)
fmt.Printf("Took %s\n", elapsed)
}</syntaxhighlight>
{{out}}
Line 275 ⟶ 377:
6 x 6 : 6
7 x 7 : 7
8 x 8 : 8
9 x 9 : 9
10 x 10 : 10
Bishops on a
.
. . .
. . . B . B . . . .
. . . B . B . B . .
B . . . . . . . . .
. .
. . . . . B . . . .
. . . . . B . . . .
. . . . . B . . . .
. . . . . . . . . .
Knights
Line 294 ⟶ 402:
4 x 4 : 4
5 x 5 : 5
6 x 6 : 8
7 x 7 : 13
8 x 8 : 14
9 x 9 : 14
10 x 10 : 16
Knights on a
. . K K . . . . . .
. . K K . . . K K .
. . . . . . . K K .
. . . . . . . . . .
. . . . . . . . . .
. K K . . . . . . .
. K K . . . K K . .
. . . . . . K K . .
. . . . . . . . . .
Took 22.383253365s
</pre>
=={{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">
genboard=: {{
safelen=:2*len=: {.y
Line 407 ⟶ 528:
end.
end.
}}</
Task output:
<
+--+--+--+ B: 1
|B |Q |K | Q: 1
Line 487 ⟶ 608:
|. . . . . . . . . . |. . . . . . . . . . |
+--------------------+--------------------+
</syntaxhighlight>
=={{header|Julia}}==
Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support.
<
import Cbc
Line 604 ⟶ 725:
"\nKnights:\n", examples[3])
</
<pre>
Squares Queens Bishops Knights
Line 657 ⟶ 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>
Line 663 ⟶ 1,002:
The first Q,B in the first row is only placed lmt..mid because of symmetry reasons.<br>
14 Queens takes 2 min @home ~2.5x faster than TIO.RUN
<
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
Line 929 ⟶ 1,268:
pG_Out(@Bsol,'_.B',max-1);
END.
</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
Line 960 ⟶ 1,299:
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}}==
{{libheader|Phix/pGUI}}
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/minqbn.htm here],
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.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\minQBN.exw
Line 986 ⟶ 1,518:
The window title shows additional information for the selected item.
"""</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">maxq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">--
<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;">--
<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>
Line 1,061 ⟶ 1,596:
-- 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;">
<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
Line 1,069 ⟶ 1,604:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- this cheeky little fella cuts more than half off the
-- last phase of 10N... (a circumstantial optimisation)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
Line 1,085 ⟶ 1,623:
<span style="color: #004080;">cdCanvas</span> <span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdcanvas</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">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>
Line 1,092 ⟶ 1,630:
<span style="color: #004080;">sequence</span> <span style="color: #000000;">state</span>
<span style="color: #000080;font-style:italic;">-- eg go straight for 16N on 10x10, avoid disproving 15N (from OEIS)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">cheats</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">,</span><span style="color: #000000;">24</span><span style="color: #0000FF;">,</span><span style="color: #000000;">29</span><span style="color: #0000FF;">,</span><span style="color: #000000;">33</span><span style="color: #0000FF;">}}</span>
<span style="color: #000080;font-style:italic;">-- some more timings with cheat mode ON:
-- 11Q: 1s, 12Q: 1.2s, 13Q: 1 min 7s, 14Q: 3 min 35s
-- 11N: 1 min 42s, 12N: gave up</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">reset</span><span style="color: #0000FF;">()</span>
Line 1,103 ⟶ 1,649:
<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;">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>
Line 1,128 ⟶ 1,675:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">IupSetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">timer</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"RUN"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
Line 1,251 ⟶ 1,798:
<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: #000000;">2</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: #004600;">CD_AMBER</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mnm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mm_baby</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">piece</span><span style="color: #0000FF;">,</span><span style="color: #000000;">col</span><span style="color: #0000FF;">,</span><span style="color: #000000;">row</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bn</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;">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>
Line 1,280 ⟶ 1,826:
<span style="color: #008080;">function</span> <span style="color: #000000;">help</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">IupMessage</span><span style="color: #0000FF;">(</span><span style="color: #000000;">title</span><span style="color: #0000FF;">,</span><span style="color: #000000;">help_text</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_IGNORE</span> <span style="color: #000080;font-style:italic;">-- (don't open browser help!)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
Line 1,308 ⟶ 1,854:
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">36</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">/</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">
<span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">
<span style="color: #7060A8;">IupUpdate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 1,344 ⟶ 1,890:
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</
=={{header|Python}}==
{{trans|Julia}}
<
from mip import Model, BINARY, xsum, minimize
Line 1,449 ⟶ 1,995:
print()
print()
</
<pre>
Squares Queens Bishops Knights
Line 1,502 ⟶ 2,048:
. . . . . . N N . .
. . . . . . . . . .
</pre>
=={{header|Raku}}==
Due to the time it's taking only a subset of the task are attempted.
{{trans|Go}}
<syntaxhighlight lang="raku" line># 20220705 Raku programming solution
my (@board, @diag1, @diag2, @diag1Lookup, @diag2Lookup, $n, $minCount, $layout);
my %limits = ( my @pieces = <Q B K> ) Z=> 7,7,6; # >>=>>> 10;
my %names = @pieces Z=> <Queens Bishops Knights>;
sub isAttacked(\piece, \row, \col) {
given piece {
when 'Q' {
(^$n)>>.&{ return True if @board[$_;col] || @board[row;$_] }
return True if @diag1Lookup[@diag1[row;col]] ||
@diag2Lookup[@diag2[row;col]]
}
when 'B' {
return True if @diag1Lookup[@diag1[row;col]] ||
@diag2Lookup[@diag2[row;col]]
}
default { # 'K'
return True if (
@board[row;col] or
row+2 < $n && col-1 >= 0 && @board[row+2;col-1] or
row-2 >= 0 && col-1 >= 0 && @board[row-2;col-1] or
row+2 < $n && col+1 < $n && @board[row+2;col+1] or
row-2 >= 0 && col+1 < $n && @board[row-2;col+1] or
row+1 < $n && col+2 < $n && @board[row+1;col+2] or
row-1 >= 0 && col+2 < $n && @board[row-1;col+2] or
row+1 < $n && col-2 >= 0 && @board[row+1;col-2] or
row-1 >= 0 && col-2 >= 0 && @board[row-1;col-2]
)
}
}
return False
}
sub attacks(\piece, \row, \col, \trow, \tcol) {
given piece {
when 'Q' { row==trow || col==tcol || abs(row - trow)==abs(col - tcol) }
when 'B' { abs(row - trow) == abs(col - tcol) }
default { my (\rd,\cd) = ((trow - row),(tcol - col))>>.abs; # when 'K'
(rd == 1 && cd == 2) || (rd == 2 && cd == 1) }
}
}
sub storeLayout(\piece) {
$layout = [~] @board.map: -> @row {
[~] ( @row.map: { $_ ?? piece~' ' !! '. ' } ) , "\n"
}
}
sub placePiece(\piece, \countSoFar, \maxCount) {
return if countSoFar >= $minCount;
my ($allAttacked,$ti,$tj) = True,0,0;
for ^$n X ^$n -> (\i,\j) {
unless isAttacked(piece, i, j) {
($allAttacked,$ti,$tj) = False,i,j andthen last
}
last unless $allAttacked
}
if $allAttacked {
$minCount = countSoFar;
storeLayout(piece);
return
}
if countSoFar <= maxCount {
my ($si,$sj) = $ti,$tj;
if piece eq 'K' {
($si,$sj) >>-=>> 2;
$si = 0 if $si < 0;
$sj = 0 if $sj < 0;
}
for ($si..^$n) X ($sj..^$n) -> (\i,\j) {
unless isAttacked(piece, i, j) {
if (i == $ti && j == $tj) || attacks(piece, i, j, $ti, $tj) {
@board[i][j] = True;
unless piece eq 'K' {
(@diag1Lookup[@diag1[i;j]],@diag2Lookup[@diag2[i;j]])=True xx *
}
placePiece(piece, countSoFar+1, maxCount);
@board[i][j] = False;
unless piece eq 'K' {
(@diag1Lookup[@diag1[i;j]],@diag2Lookup[@diag2[i;j]])=False xx *
}
}
}
}
}
}
for @pieces -> \piece {
say %names{piece}~"\n=======\n";
loop ($n = 1 ; ; $n++) {
@board = [ [ False xx $n ] xx $n ];
unless piece eq 'K' {
@diag1 = ^$n .map: { $_ ... $n+$_-1 } ;
@diag2 = ^$n .map: { $n+$_-1 ... $_ } ;
@diag2Lookup = @diag1Lookup = [ False xx 2*$n-1 ]
}
$minCount = 2³¹ - 1; # golang: math.MaxInt32
my \nSQ = $n*$n;
for 1..nSQ -> \maxCount {
placePiece(piece, 0, maxCount);
last if $minCount <= nSQ
}
printf("%2d x %-2d : %d\n", $n, $n, $minCount);
if $n == %limits{piece} {
printf "\n%s on a %d x %d board:\n", %names{piece}, $n, $n;
say $layout andthen last
}
}
}</syntaxhighlight>
{{out}}
<pre>
Queens
=======
1 x 1 : 1
2 x 2 : 1
3 x 3 : 1
4 x 4 : 3
5 x 5 : 3
6 x 6 : 4
7 x 7 : 4
Queens on a 7 x 7 board:
. Q . . . . .
. . . . . Q .
. . . . . . .
Q . . . . . .
. . . . Q . .
. . . . . . .
. . . . . . .
Bishops
=======
1 x 1 : 1
2 x 2 : 2
3 x 3 : 3
4 x 4 : 4
5 x 5 : 5
6 x 6 : 6
7 x 7 : 7
Bishops on a 7 x 7 board:
. . . . . B .
. . B . . . .
. . B . B . .
. . . . . . B
. . . B . . .
. . . B . . .
. . . . . . .
Knights
=======
1 x 1 : 1
2 x 2 : 4
3 x 3 : 4
4 x 4 : 4
5 x 5 : 5
6 x 6 : 8
Knights on a 6 x 6 board:
K . . . . K
. . . . . .
. . K K . .
. . K K . .
. . . . . .
K . . . . K
</pre>
=={{header|Wren}}==
===CLI===
{{libheader|Wren-fmt}}
This was originally based on the Java code [https://www.geeksforgeeks.org/minimum-queens-required-to-cover-all-the-squares-of-a-chess-board/ here] which uses a backtracking algorithm and which I extended to deal with bishops and knights as well as queens when translating to Wren. I then used the more efficient way for checking the diagonals described [https://www.geeksforgeeks.org/n-queen-problem-using-branch-and-bound/ here] and have now incorporated the improvements made to the Go version.
Although 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.
<
var board
Line 1,519 ⟶ 2,241:
var minCount
var layout
var isAttacked = Fn.new { |piece, row, col|
if (piece == "Q") {
Line 1,528 ⟶ 2,250:
diag2Lookup[diag2[row][col]]) return true
} else if (piece == "B") {
if (diag1Lookup[diag1[row][col]] ||
diag2Lookup[diag2[row][col]]) return true
Line 1,543 ⟶ 2,264:
}
return false
}
var attacks = Fn.new { |piece, row, col, trow, tcol|
if (piece == "Q") {
return row == trow || col == tcol || (row-trow).abs == (col-tcol).abs
} else if (piece == "B") {
return (row-trow).abs == (col-tcol).abs
} else { // piece == "K"
var rd = (trow - row).abs
var cd = (tcol - col).abs
return (rd == 1 && cd == 2) || (rd == 2 && cd == 1)
}
}
Line 1,555 ⟶ 2,288:
var placePiece // recursive function
placePiece = Fn.new { |piece, countSoFar, maxCount|
if (countSoFar >= minCount) return
var allAttacked = true
var ti = 0
var tj = 0
for (i in 0...n) {
for (j in 0...n) {
if (!isAttacked.call(piece, i, j)) {
allAttacked = false
ti = i
tj = j
break
}
Line 1,572 ⟶ 2,309:
return
}
var sj
for (i in si...n)
for
board[i][j] =
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,587 ⟶ 2,334:
}
var start = System.clock
var pieces = ["Q", "B", "K"]
var limits = {"Q": 10, "B":
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"}
for (piece in pieces) {
Line 1,597 ⟶ 2,345:
board = List.filled(n, null)
for (i in 0...n) board[i] = List.filled(n, false)
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, maxCount)
if (minCount <= n*n) break
}
Fmt.print("$2d x $-2d : $d", n, n, minCount)
if (n == limits[piece]) {
Line 1,620 ⟶ 2,373:
n = n + 1
}
}
System.print("Took %(System.clock - start) seconds.")</syntaxhighlight>
{{out}}
Line 1,660 ⟶ 2,414:
5 x 5 : 5
6 x 6 : 6
7 x 7 : 7
8 x 8 : 8
9 x 9 : 9
10 x 10 : 10
Bishops on a
. . .
. . . B . B . . . .
. . . B . B . B . .
B . .
. . . . . . . . . .
. . . . . B . . . .
. . . . . B . . . .
. . . . . B . . . .
. . . . . . . . . .
Knights
Line 1,678 ⟶ 2,440:
4 x 4 : 4
5 x 5 : 5
6 x 6 : 8
7 x 7 : 13
8 x 8 : 14
9 x 9 : 14
10 x 10 : 16
Knights on a
. . K K . . . . . .
. . K K . . . K K .
. . . . . . . K K .
. . . . . . . . . .
. . . . . . . . . .
. K K . . . . . . .
. K K . . . K K . .
. . . . . . K K . .
. . . . . . . . . .
Took 1276.522608 seconds.
</pre>
===Embedded===
{{libheader|Wren-linear}}
This is the first outing for the above module which is a wrapper for GLPK.
As there are quite a lot of variables and constraints in this task, I have used MathProg scripts to solve it rather than calling the basic API routines directly. The script file needs to be changed for each chess piece and each value of 'n' as there appear to be no looping constructs in MathProg itself.
Despite this, the program runs in only 3.25 seconds which is far quicker than I was expecting.
I have borrowed one or two tricks from the Julia/Python versions in formulating the constraints.
<syntaxhighlight lang="wren">import "./linear" for Prob, Glp, Tran, File
import "./fmt" for Fmt
var start = System.clock
var queenMpl = """
var x{1..n, 1..n}, binary;
s.t. a{i in 1..n}: sum{j in 1..n} x[i,j] <= 1;
s.t. b{j in 1..n}: sum{i in 1..n} x[i,j] <= 1;
s.t. c{k in 2-n..n-2}: sum{i in 1..n, j in 1..n: i-j == k} x[i,j] <= 1;
s.t. d{k in 3..n+n-1}: sum{i in 1..n, j in 1..n: i+j == k} x[i,j] <= 1;
s.t. e{i in 1..n, j in 1..n}:
sum{k in 1..n} x[i,k] +
sum{k in 1..n} x[k,j] +
sum{k in (1-n)..n: 1 <= i + k && i + k <= n && 1 <= j + k && j + k <=n} x[i+k,j+k] +
sum{k in (1-n)..n: 1 <= i - k && i - k <= n && 1 <= j + k && j + k <=n} x[i-k, k+j] >= 1;
minimize obj: sum{i in 1..n, j in 1..n} x[i,j];
solve;
end;
"""
var bishopMpl = """
var x{1..n, 1..n}, binary;
s.t. a{k in 2-n..n-2}: sum{i in 1..n, j in 1..n: i-j == k} x[i,j] <= 1;
s.t. b{k in 3..n+n-1}: sum{i in 1..n, j in 1..n: i+j == k} x[i,j] <= 1;
s.t. c{i in 1..n, j in 1..n}:
sum{k in (1-n)..n: 1 <= i + k && i + k <= n && 1 <= j + k && j + k <=n} x[i+k,j+k] +
sum{k in (1-n)..n: 1 <= i - k && i - k <= n && 1 <= j + k && j + k <=n} x[i-k, k+j] >= 1;
minimize obj: sum{i in 1..n, j in 1..n} x[i,j];
solve;
end;
"""
var knightMpl = """
set deltas, dimen 2;
var x{1..n+4, 1..n+4}, binary;
s.t. a{i in 1..n+4}: sum{j in 1..n+4: j < 3 || j > n + 2} x[i,j] = 0;
s.t. b{j in 1..n+4}: sum{i in 1..n+4: i < 3 || i > n + 2} x[i,j] = 0;
s.t. c{i in 3..n+2, j in 3..n+2}: x[i, j] + sum{(k, l) in deltas} x[i + k, j + l] >= 1;
s.t. d{i in 3..n+2, j in 3..n+2}: sum{(k, l) in deltas} x[i + k, j + l] + 100 * x[i, j] <= 100;
minimize obj: sum{i in 3..n+2, j in 3..n+2} x[i,j];
solve;
data;
set deltas := (1,2) (2,1) (2,-1) (1,-2) (-1,-2) (-2,-1) (-2,1) (-1,2);
end;
"""
var mpls = {"Q": queenMpl, "B": bishopMpl, "K": knightMpl}
var pieces = ["Q", "B", "K"]
var limits = {"Q": 10, "B": 10, "K": 10}
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"}
var fname = "n_pieces.mod"
Glp.termOut(Glp.OFF)
for (piece in pieces) {
System.print(names[piece])
System.print("=======\n")
for (n in 1..limits[piece]) {
var first = "param n, integer, > 0, default %(n);\n"
File.write(fname, first + mpls[piece])
var mip = Prob.create()
var tran = Tran.mplAllocWksp()
var ret = tran.mplReadModel(fname, 0)
if (ret != 0) System.print("Error on translating model.")
if (ret == 0) {
ret = tran.mplGenerate(null)
if (ret != 0) System.print("Error on generating model.")
if (ret == 0) {
tran.mplBuildProb(mip)
mip.simplex(null)
mip.intOpt(null)
Fmt.print("$2d x $-2d : $d", n, n, mip.mipObjVal.round)
if (n == limits[piece]) {
Fmt.print("\n$s on a $d x $d board:\n", names[piece], n, n)
var cols = {}
if (piece != "K") {
for (i in 1..n*n) cols[mip.colName(i)] = mip.mipColVal(i)
for (i in 1..n) {
for (j in 1..n) {
var char = (cols["x[%(i),%(j)]"] == 1) ? "%(piece) " : ". "
System.write(char)
}
System.print()
}
} else {
for (i in 1..(n+4)*(n+4)) cols[mip.colName(i)] = mip.mipColVal(i)
for (i in 3..n+2) {
for (j in 3..n+2) {
var char = (cols["x[%(i),%(j)]"] == 1) ? "%(piece) " : ". "
System.write(char)
}
System.print()
}
}
}
}
}
tran.mplFreeWksp()
mip.delete()
}
System.print()
}
File.remove(fname)
System.print("Took %(System.clock - start) seconds.")</syntaxhighlight>
{{out}}
<pre>
Queens
=======
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.
</pre>
|