Anonymous user
N-queens minimum and knights and bishops: Difference between revisions
N-queens minimum and knights and bishops (view source)
Revision as of 07:30, 26 April 2022
, 2 years ago→{{header|Free Pascal}}: added bishop
m (→{{header|J}}: remove an overly aggressive optimization..) |
m (→{{header|Free Pascal}}: added bishop) |
||
Line 458:
=={{header|Pascal}}==
==={{header|Free Pascal}}===
At bishops I used a trick that at max only one row is left free.
<lang pascal>program TestMinimalQueen;
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
uses
sysutils;
const
KoorCOUNT = 16;
Line 474 ⟶ 477:
{$ALIGN 32}
CPG :tCheckPG;
pgIdx,minIdx : nativeInt;
jumpedOver : boolean;
procedure pG_Out(pSol:tpPlayGround;ConvChar : string;lmt: NativeInt);
var
row,col: NativeInt;
begin
iF length(ConvChar)<>3 then
EXIT;
for row := lmt downto 0 do
Begin
Line 552 ⟶ 556:
function check(lmt:nativeInt):boolean;
//check, if all fields are attacked
var
pPG :tpPlayGround;
Line 572 ⟶ 577:
EXIT;
inc(pgIdx);
//check every column
For col := 0 to lmt do
begin
//copy last state
CPG[pgIdx]:=CPG[pgIdx-1];
if pPG^[row,col] <> 0 then
continue;
RightAscDia(row,col,lmt);
LeftAscDia(row,col,lmt);
//set row and column as attacked
For i := 0 to lmt do
Begin
Line 586 ⟶ 594:
pPG^[i,col] := 1;
end;
//set position of queen
pPG^[row,col] := 2;
if check(lmt) then
begin
Line 592 ⟶ 602:
begin
minIdx := pgIdx;
end;
end
Line 599 ⟶ 609:
BREAK
else
//check next rows
For t := row+1 to lmt do
SetQueen(t,lmt);
Line 605 ⟶ 616:
end;
procedure SetBishop(row,lmt: NativeInt);
var
pPG :tpPlayGround;
col,t: NativeInt;
begin
if pgIdx = minIDX then
EXIT;
inc(pgIdx);
For col := 0 to lmt do
begin
CPG[pgIdx]:=CPG[pgIdx-1];
pPG := @CPG[pgIdx];
if pPG^[row,col] <> 0 then
continue;
RightAscDia(row,col,lmt);
LeftAscDia(row,col,lmt);
//set position of bishop
pPG^[row,col] := 2;
if check(lmt) then
begin
if minIdx> pgIdx then
begin
minIdx := pgIdx;
Bsol := pPG^;
end;
end
else
if row > lmt then
BREAK
else
begin
//check next row
t := row+1;
if (t <= lmt) then
begin
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;
dec(pgIdx);
end;
var
lmt,max : NativeInt;
BEGIN
write(' nxn n=:');
For lmt := 1 to max do
write(lmt:3);
writeln;
write(' Queens :');
For lmt := 0 to max-1 do
begin
pgIdx := 0;
minIdx := 2*(lmt+1);
jumpedOver := true;
setQueen(0,lmt);
end;
writeln;
write(' Bishop :');
For lmt := 0 to max-1 do
begin
pgIdx := 0;
minIdx := 2*(lmt+1);
jumpedOver := true;
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>
Queens : 1 1 2 3 3 4 4 5 5 5
Bishop : 1 2 3 4 5 6 7 8 9 10
..........
......Q...
..........
Q.........
..........
....Q.....
..........
........Q.
..........
..Q.......
B.........
.....B....
...B......
.....B....
...B......
........B.
....B.....
....B.....
....B.....
B.........
Real time: 4.740 s CPU share: 99.06 %</pre>
=={{header|Phix}}==
| |||