N-queens minimum and knights and bishops: Difference between revisions
N-queens minimum and knights and bishops (view source)
Revision as of 21:14, 11 July 2022
, 1 year agoAdded Perl
m (→{{header|Raku}}: simplify) |
SqrtNegInf (talk | contribs) (Added Perl) |
||
Line 1,081:
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}}
<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
}
}
}</lang>
{{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}}==
| |||