Anonymous user
N-queens minimum and knights and bishops: Difference between revisions
N-queens minimum and knights and bishops (view source)
Revision as of 13:20, 28 April 2022
, 2 years ago→{{header|Free Pascal}}: new version.All bishops can be in one row takes x5 time up to 10.
m (use Cbc optimizer only) |
m (→{{header|Free Pascal}}: new version.All bishops can be in one row takes x5 time up to 10.) |
||
Line 629:
=={{header|Pascal}}==
==={{header|Free Pascal}}===
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
<lang pascal>program TestMinimalQueen;
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
Line 635 ⟶ 636:
uses
sysutils;
type
tDeltaKoor = packed record
end;▼
const
cKnightAttacks : array[0..7] of tDeltaKoor =
((dRow:-2;dCol:-1),(dRow:-2;dCol:+1),
(dRow:-1;dCol:-2),(dRow:-1;dCol:+2),
(dRow:+1;dCol:-2),(dRow:+1;dCol:+2),
(dRow:+2;dCol:-1),(dRow:+2;dCol:+1));
KoorCOUNT = 16;
Line 642 ⟶ 654:
tPlayGround = array[tLimit,tLimit] of byte;
tCheckPG = array[0..2*KoorCOUNT] of tplayGround;
tpPlayGround = ^tPlayGround;
Line 650 ⟶ 662:
Qsol,BSol,KSol :tPlayGround;
pgIdx,minIdx : nativeInt;
procedure pG_Out(pSol:tpPlayGround;ConvChar : string;lmt: NativeInt);
Line 661 ⟶ 672:
Begin
for col := 0 to lmt do
write(ConvChar[1+pSol^[row,col]],' ');
writeln;
end;
Line 730 ⟶ 741:
var
pPG :tpPlayGround;
pRow : pByte;
row,col: NativeInt;
Begin
pPG := @CPG[pgIdx];
For row := lmt downto 0 do
pRow := @pPG^[row,0];
For col := lmt downto 0 do
if
EXIT(false);
exit(true);
end;
Line 745 ⟶ 760:
i,col,t: NativeInt;
begin
t := pgIdx+1;
if
EXIT;
//use state before
move(CPG[t-1],CPG[t],SizeOf(tPlayGround));
//first row only check one half -> symmetry
col := col shr 1;
//check every column
For col :=
begin
//copy last state▼
▲ CPG[pgIdx]:=CPG[pgIdx-1];
pPG := @CPG[pgIdx];
if pPG^[row,col] <> 0 then
continue;
//set diagonals
RightAscDia(row,col,lmt);
LeftAscDia(row,col,lmt);
Line 765 ⟶ 787:
pPG^[i,col] := 1;
end;
//now set position of queen
pPG^[row,col] := 2;
Line 783 ⟶ 805:
For t := row+1 to lmt do
SetQueen(t,lmt);
▲ //copy last state
move(CPG[t-1],CPG[t],SizeOf(tPlayGround));
// CPG[pgIdx]:=CPG[pgIdx-1];
end;
dec(pgIdx);
Line 795 ⟶ 821:
EXIT;
inc(pgIdx);
move(CPG[pgIdx-1],CPG[pgIdx],SizeOf(tPlayGround));
▲ For col := 0 to lmt do
col := lmt;
if row = 0 then
col := col shr 1;
For col := col downto 0 do
begin
▲ CPG[pgIdx]:=CPG[pgIdx-1];
pPG := @CPG[pgIdx];
if pPG^[row,col] <> 0 then
Line 821 ⟶ 850:
else
begin
//check same row
//check next row
t := row+1;
if (t <= lmt) then
▲ begin
SetBishop(t,lmt);
▲ inc(t);
▲ if t <= lmt then
▲ SetBishop(t,lmt);
▲ jumpedOver := true;
▲ end;
▲ end;
end;
move(CPG[pgIdx-1],CPG[pgIdx],SizeOf(tPlayGround));
end;
dec(pgIdx);
Line 855 ⟶ 876:
begin
pgIdx := 0;
minIdx :=
setQueen(0,lmt);
write(minIDX:3);
Line 866 ⟶ 886:
begin
pgIdx := 0;
minIdx := 2*
setBishop(0,lmt);
write(minIDX:3);
end;
writeln;
pG_Out(@Qsol,'_.Q',max-1);
writeln;
pG_Out(@Bsol,'_.B',max-1);
END.
</lang>
{{out|@TIO.RUN}}
<pre>
nxn n=: 1 2 3 4 5 6 7 8 9 10
Queens : 1 1 2 3 3 4 4 5 5 5
Bishop : 1 2 3 4 5 6 7 8 9 10
. . . . . . . . . .
. . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . .
. . . . . . . . . .
. . . . . . . .
. . . . . . . . . .
. .
. . . .
. . .
. . . .
. . .
. B . . . . . . .
. . .
. . . .
. . . .
Real time:
</pre>
=={{header|Phix}}==
| |||