N-queens problem: Difference between revisions
Content added Content deleted
m (→{{header|C}}: adjusted formatting) |
(→{{header|Fortran}}: adding F77... could be optimized a bit, to be continued ;-)) |
||
Line 1,146: | Line 1,146: | ||
|###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| Q |###| |###| |###| |###| |###| | |
|###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| Q |###| |###| |###| |###| |###| | |
||
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</pre> |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</pre> |
||
===Alternate Fortran 77 solution=== |
|||
<lang fortran> |
|||
C This one enumerates permutations, skipping impossible "branches" |
|||
C See the 2nd program for Scheme on the "Permutations" page for the main idea |
|||
program qtest |
|||
integer n |
|||
do 10 n=1,16 |
|||
call queens(n) |
|||
10 continue |
|||
end |
|||
subroutine queens(n) |
|||
implicit none |
|||
integer a,i,j,m,n,s,z |
|||
logical chk |
|||
dimension a(n),s(n) |
|||
do 10 i=1,n |
|||
a(i)=i |
|||
s(i)=0 |
|||
10 continue |
|||
m=0 |
|||
i=1 |
|||
20 if(i.gt.n) then |
|||
m=m+1 |
|||
go to 60 |
|||
end if |
|||
j=i |
|||
30 z=a(i) |
|||
a(i)=a(j) |
|||
a(j)=z |
|||
if(chk(n,a,i)) then |
|||
s(i)=j |
|||
i=i+1 |
|||
go to 20 |
|||
end if |
|||
j=j+1 |
|||
if(j.le.n) go to 30 |
|||
50 j=j-1 |
|||
if(j.eq.i) go to 60 |
|||
z=a(i) |
|||
a(i)=a(j) |
|||
a(j)=z |
|||
go to 50 |
|||
60 i=i-1 |
|||
if(i.eq.0) go to 70 |
|||
j=s(i) |
|||
j=j+1 |
|||
if(j.le.n) go to 30 |
|||
go to 50 |
|||
70 print *,n,m |
|||
end |
|||
C TODO : replace the following loop with a single test on diagonals already visited |
|||
C This would need keeping track of "up" and "down" diagonals in vectors of size 2*n-1 |
|||
function chk(n,a,i) |
|||
implicit none |
|||
logical chk |
|||
integer n,a,i,j |
|||
dimension a(n) |
|||
chk=.true. |
|||
j=1 |
|||
10 if(j.eq.i) return |
|||
if(iabs(a(i)-a(j)).eq.iabs(i-j)) go to 20 |
|||
j=j+1 |
|||
go to 10 |
|||
20 chk=.false. |
|||
end</lang> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |