N-queens minimum and knights and bishops: Difference between revisions

Content added Content deleted
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: Line 629:
=={{header|Pascal}}==
=={{header|Pascal}}==
==={{header|Free Pascal}}===
==={{header|Free Pascal}}===
The first Q,B in the first row is only placed lmt..mid because of symmetry reasons.<br>
At bishops I used a trick that at max only one row is left free.
14 Queens takes 2 min @home ~2.5x faster than TIO.RUN
<lang pascal>program TestMinimalQueen;
<lang pascal>program TestMinimalQueen;
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
Line 635: Line 636:
uses
uses
sysutils;
sysutils;
type
tDeltaKoor = packed record
⚫
dRow,
⚫
dCol : Int8;
⚫
end;
const
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;
KoorCOUNT = 16;


Line 642: Line 654:


tPlayGround = array[tLimit,tLimit] of byte;
tPlayGround = array[tLimit,tLimit] of byte;
tCheckPG = array[0..KoorCOUNT] of tplayGround;
tCheckPG = array[0..2*KoorCOUNT] of tplayGround;
tpPlayGround = ^tPlayGround;
tpPlayGround = ^tPlayGround;


Line 650: Line 662:
Qsol,BSol,KSol :tPlayGround;
Qsol,BSol,KSol :tPlayGround;
pgIdx,minIdx : nativeInt;
pgIdx,minIdx : nativeInt;
jumpedOver : boolean;


procedure pG_Out(pSol:tpPlayGround;ConvChar : string;lmt: NativeInt);
procedure pG_Out(pSol:tpPlayGround;ConvChar : string;lmt: NativeInt);
Line 661: Line 672:
Begin
Begin
for col := 0 to lmt do
for col := 0 to lmt do
write(ConvChar[1+pSol^[row,col]]);
write(ConvChar[1+pSol^[row,col]],' ');
writeln;
writeln;
end;
end;
Line 730: Line 741:
var
var
pPG :tpPlayGround;
pPG :tpPlayGround;
pRow : pByte;
row,col: NativeInt;
row,col: NativeInt;
Begin
Begin
pPG := @CPG[pgIdx];
pPG := @CPG[pgIdx];
For row := lmt downto 0 do
For row := lmt downto 0 do
⚫
begin
pRow := @pPG^[row,0];
For col := lmt downto 0 do
For col := lmt downto 0 do
if pPG^[row,col] = 0 then
if pRow[col] = 0 then
EXIT(false);
EXIT(false);
⚫
end;
exit(true);
exit(true);
end;
end;
Line 745: Line 760:
i,col,t: NativeInt;
i,col,t: NativeInt;
begin
begin
t := pgIdx+1;
if pgIdx = minIDX then
if t = minIDX then
EXIT;
EXIT;
inc(pgIdx);
pgIdx:= t;
//use state before
⚫
// CPG[pgIdx]:=CPG[pgIdx-1];
move(CPG[t-1],CPG[t],SizeOf(tPlayGround));
⚫
col := lmt;
//first row only check one half -> symmetry
⚫
if row = 0 then
col := col shr 1;

//check every column
//check every column
For col := 0 to lmt do
For col := col downto 0 do
begin
begin
⚫
//copy last state
⚫
CPG[pgIdx]:=CPG[pgIdx-1];
pPG := @CPG[pgIdx];
pPG := @CPG[pgIdx];
if pPG^[row,col] <> 0 then
if pPG^[row,col] <> 0 then
continue;
continue;
//set diagonals

RightAscDia(row,col,lmt);
RightAscDia(row,col,lmt);
LeftAscDia(row,col,lmt);
LeftAscDia(row,col,lmt);
Line 765: Line 787:
pPG^[i,col] := 1;
pPG^[i,col] := 1;
end;
end;
//set position of queen
//now set position of queen
pPG^[row,col] := 2;
pPG^[row,col] := 2;


Line 783: Line 805:
For t := row+1 to lmt do
For t := row+1 to lmt do
SetQueen(t,lmt);
SetQueen(t,lmt);
⚫
//copy last state
⚫
t := pgIdx;
move(CPG[t-1],CPG[t],SizeOf(tPlayGround));
// CPG[pgIdx]:=CPG[pgIdx-1];
end;
end;
dec(pgIdx);
dec(pgIdx);
Line 795: Line 821:
EXIT;
EXIT;
inc(pgIdx);
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
begin
⚫
CPG[pgIdx]:=CPG[pgIdx-1];
pPG := @CPG[pgIdx];
pPG := @CPG[pgIdx];
if pPG^[row,col] <> 0 then
if pPG^[row,col] <> 0 then
Line 821: Line 850:
else
else
begin
begin
//check same row
⚫
SetBishop(row,lmt);
//check next row
//check next row
t := row+1;
t := row+1;
if (t <= lmt) then
if (t <= lmt) then
⚫
begin
SetBishop(t,lmt);
SetBishop(t,lmt);
//left out max one row on field
if jumpedOver then
Begin
⚫
inc(t);
jumpedOver := false;
⚫
if t <= lmt then
⚫
SetBishop(t,lmt);
⚫
jumpedOver := true;
⚫
end;
⚫
end;
end;
end;
move(CPG[pgIdx-1],CPG[pgIdx],SizeOf(tPlayGround));
end;
end;
dec(pgIdx);
dec(pgIdx);
Line 855: Line 876:
begin
begin
pgIdx := 0;
pgIdx := 0;
minIdx := 2*(lmt+1);
minIdx := lmt;
jumpedOver := true;
setQueen(0,lmt);
setQueen(0,lmt);
write(minIDX:3);
write(minIDX:3);
Line 866: Line 886:
begin
begin
pgIdx := 0;
pgIdx := 0;
minIdx := 2*(lmt+1);
minIdx := 2*lmt+1;
jumpedOver := true;
setBishop(0,lmt);
setBishop(0,lmt);
write(minIDX:3);
write(minIDX:3);
end;
end;
writeln;
writeln;

pG_Out(@Qsol,'_.Q',max-1);
pG_Out(@Qsol,'_.Q',max-1);
writeln;
writeln;

pG_Out(@Bsol,'_.B',max-1);
pG_Out(@Bsol,'_.B',max-1);
END.</lang>
END.
</lang>
{{out|@TIO.RUN}}
{{out|@TIO.RUN}}
<pre>
<pre>

nxn n=: 1 2 3 4 5 6 7 8 9 10
nxn n=: 1 2 3 4 5 6 7 8 9 10
Queens : 1 1 2 3 3 4 4 5 5 5
Queens : 1 1 2 3 3 4 4 5 5 5
Bishop : 1 2 3 4 5 6 7 8 9 10
Bishop : 1 2 3 4 5 6 7 8 9 10
..........
. . . . . . . . . .
......Q...
. . . . . . . Q . .
..........
. . . . . . . . . .
Q.........
. Q . . . . . . . .
..........
. . . . . . . . . .
....Q.....
. . . . . Q . . . .
..........
. . . . . . . . . .
........Q.
. . . . . . . . . Q
..........
. . . . . . . . . .
..Q.......
. . . Q . . . . . .




B.........
. . . . . . . . . .
.....B....
. . . . B . . . . .
...B......
. . . . . . B . . .
.....B....
. . . . B . . . . .
...B......
. . . . . . B . . .
........B.
. B . . . . . . . .
....B.....
. . . B . B . . . .
....B.....
. . . . . B . . . .
....B.....
. . . . . . . . B .
B.........
. . . . B . . . . .


Real time: 4.740 s CPU share: 99.06 %</pre>
Real time: 25.935 s CPU share: 99.27 % //@home AMD 5600G real 0m10,784s
</pre>


=={{header|Phix}}==
=={{header|Phix}}==
Retrieved from "https://rosettacode.org/wiki/N-queens_minimum_and_knights_and_bishops"