N-queens minimum and knights and bishops: Difference between revisions
Content added Content deleted
(Added Go) |
m (added Pascal only for Queens.) |
||
Line 301: | Line 301: | ||
. . . . . |
. . . . . |
||
</pre> |
</pre> |
||
=={{header|Pascal}}== |
|||
==={{header|Free Pascal}}=== |
|||
<lang pascal> |
|||
program TestMinimalQueen; |
|||
const |
|||
KoorCOUNT = 16; |
|||
type |
|||
tLimit = 0..KoorCOUNT-1; |
|||
tPlayGround = array[tLimit,tLimit] of byte; |
|||
tCheckPG = array[0..KoorCOUNT] of tplayGround; |
|||
tpPlayGround = ^tPlayGround; |
|||
var |
|||
{$ALIGN 32} |
|||
CPG :tCheckPG; |
|||
sol :tPlayGround; |
|||
pgIdx,minIdx : nativeInt; |
|||
procedure pG_Out(pSol:tpPlayGround;lmt: NativeInt); |
|||
const |
|||
ConvChar = '_.Q'; |
|||
var |
|||
row,col: NativeInt; |
|||
begin |
|||
for row := lmt downto 0 do |
|||
Begin |
|||
for col := 0 to lmt do |
|||
write(ConvChar[1+pSol^[row,col]]); |
|||
writeln; |
|||
end; |
|||
writeln; |
|||
end; |
|||
procedure LeftAscDia(row,col,lmt: NativeInt); |
|||
var |
|||
pPG :tpPlayGround; |
|||
j: NativeInt; |
|||
begin |
|||
pPG := @CPG[pgIdx]; |
|||
if row >= col then |
|||
begin |
|||
j := row-col; |
|||
col := lmt-j; |
|||
row := lmt; |
|||
repeat |
|||
pPG^[row,col] := 1; |
|||
dec(col); |
|||
dec(row); |
|||
until col < 0; |
|||
end |
|||
else |
|||
begin |
|||
j := col-row; |
|||
row := lmt-j; |
|||
col := lmt; |
|||
repeat |
|||
pPG^[row,col] := 1; |
|||
dec(row); |
|||
dec(col); |
|||
until row < 0; |
|||
end; |
|||
end; |
|||
procedure RightAscDia(row,col,lmt: NativeInt); |
|||
var |
|||
pPG :tpPlayGround; |
|||
j: NativeInt; |
|||
begin |
|||
pPG := @CPG[pgIdx]; |
|||
j := row+col; |
|||
if j <= lmt then |
|||
begin |
|||
col := j; |
|||
row := 0; |
|||
repeat |
|||
pPG^[row,col] := 1; |
|||
dec(col); |
|||
inc(row); |
|||
until col < 0; |
|||
end |
|||
else |
|||
begin |
|||
col := lmt; |
|||
row := j-lmt; |
|||
repeat |
|||
pPG^[row,col] := 1; |
|||
inc(row); |
|||
dec(col); |
|||
until row > lmt; |
|||
end; |
|||
end; |
|||
function check(lmt:nativeInt):boolean; |
|||
var |
|||
pPG :tpPlayGround; |
|||
row,col: NativeInt; |
|||
Begin |
|||
pPG := @CPG[pgIdx]; |
|||
For row := lmt downto 0 do |
|||
For col := lmt downto 0 do |
|||
if pPG^[row,col] = 0 then |
|||
EXIT(false); |
|||
exit(true); |
|||
end; |
|||
procedure SetQueen(row,lmt: NativeInt); |
|||
var |
|||
pPG :tpPlayGround; |
|||
i,col,t: NativeInt; |
|||
begin |
|||
if pgIdx = minIDX then |
|||
EXIT; |
|||
inc(pgIdx); |
|||
For col := 0 to lmt do |
|||
begin |
|||
CPG[pgIdx]:=CPG[pgIdx-1]; |
|||
if CPG[pgIdx][row,col] <> 0 then |
|||
continue; |
|||
CPG[pgIdx]:=CPG[pgIdx-1]; |
|||
RightAscDia(row,col,lmt); |
|||
LeftAscDia(row,col,lmt); |
|||
pPG := @CPG[pgIdx]; |
|||
For i := 0 to lmt do |
|||
Begin |
|||
pPG^[row,i] := 1; |
|||
pPG^[i,col] := 1; |
|||
end; |
|||
pPG^[row,col] := 2; |
|||
if check(lmt) then |
|||
begin |
|||
if minIdx> pgIdx then |
|||
begin |
|||
minIdx := pgIdx; |
|||
sol := CPG[pgIdx]; |
|||
end; |
|||
end |
|||
else |
|||
if row > lmt then |
|||
BREAK |
|||
else |
|||
For t := row+1 to lmt do |
|||
SetQueen(t,lmt); |
|||
end; |
|||
dec(pgIdx); |
|||
end; |
|||
var |
|||
lmt : NativeInt; |
|||
BEGIN |
|||
For lmt := 0 to 11 do |
|||
begin |
|||
pgIdx := 0; |
|||
minIdx := 2*(lmt+1); |
|||
setQueen(0,lmt); |
|||
writeln(lmt+1:3,minIDX:3); |
|||
// pG_Out(@sol,lmt); |
|||
end; |
|||
pG_Out(@sol,lmt); |
|||
END.</lang> |
|||
{{out|@TIO.RUN}} |
|||
<pre> |
|||
nxn min. queens |
|||
1 1 |
|||
2 1 |
|||
3 2 |
|||
4 3 |
|||
5 3 |
|||
6 4 |
|||
7 4 |
|||
8 5 |
|||
9 5 |
|||
10 5 |
|||
11 6 //Real time: 3.241 s |
|||
12 7 |
|||
.Q.......... |
|||
............ |
|||
........Q... |
|||
............ |
|||
...Q........ |
|||
............ |
|||
............ |
|||
..........Q. |
|||
............ |
|||
.....Q...... |
|||
..Q......... |
|||
Q........... |
|||
Real time: 45.856 s CPU share: 99.24 % // below the time limit of 60 secs</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{libheader|Phix/pGUI}} |
{{libheader|Phix/pGUI}} |