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|Go}}: Further speed up, about 4 times quicker than before.) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
(16 intermediate revisions by 7 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#}}==
<
// Minimum knights to attack all squares not occupied on an NxN chess board. Nigel Galloway: May 12th., 2022
type att={n:uint64; g:uint64}
Line 35 ⟶ 38:
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>
Line 125 ⟶ 128:
=={{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
Timing is for an Intel Core i7-8565U machine running Ubuntu 20.04.
<
import (
Line 247 ⟶ 250:
storeLayout(piece)
return
}
if countSoFar <= maxCount {
si := ti
sj := tj
if piece == "K" {
si = si - 2
sj = sj - 2
if si < 0 {
si = 0
}
if sj < 0 {
sj = 0
}
}
for i := si; i < n; i++ {
for j := sj; j < n; j++ {
Line 327 ⟶ 336:
elapsed := time.Now().Sub(start)
fmt.Printf("Took %s\n", elapsed)
}</
{{out}}
Line 412 ⟶ 421:
. . . . . . . . . .
Took
</pre>
Line 419 ⟶ 428:
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 519 ⟶ 528:
end.
end.
}}</
Task output:
<
+--+--+--+ B: 1
|B |Q |K | Q: 1
Line 599 ⟶ 608:
|. . . . . . . . . . |. . . . . . . . . . |
+--------------------+--------------------+
</syntaxhighlight>
=={{header|Julia}}==
Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support.
<
import Cbc
Line 716 ⟶ 725:
"\nKnights:\n", examples[3])
</
<pre>
Squares Queens Bishops Knights
Line 769 ⟶ 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 775 ⟶ 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 1,041 ⟶ 1,268:
pG_Out(@Bsol,'_.B',max-1);
END.
</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
Line 1,072 ⟶ 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 1,098 ⟶ 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,173 ⟶ 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,181 ⟶ 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,197 ⟶ 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,204 ⟶ 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,215 ⟶ 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,240 ⟶ 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,363 ⟶ 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,392 ⟶ 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,420 ⟶ 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,456 ⟶ 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,561 ⟶ 1,995:
print()
print()
</
<pre>
Squares Queens Bishops Knights
Line 1,614 ⟶ 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,631 ⟶ 2,241:
var minCount
var layout
var isAttacked = Fn.new { |piece, row, col|
if (piece == "Q") {
Line 1,640 ⟶ 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,655 ⟶ 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,667 ⟶ 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,684 ⟶ 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,699 ⟶ 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,709 ⟶ 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,732 ⟶ 2,373:
n = n + 1
}
}
System.print("Took %(System.clock - start) seconds.")</syntaxhighlight>
{{out}}
Line 1,772 ⟶ 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,790 ⟶ 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>
|