C Count lacings of a shoe with two columns of N eyelets
C subjected to the condition that there is NO direct
C "horizontal" connection between any adjacent eyelet
C pair (e.g. 2<->2*n-1, 3<->2*n-2, 4<->2*n-3,....)
C
C Author: Hugo Pfoertner http:/www.pfoertner.org/
C
C Version history:
C 17.01.2003 Non-straight lacings
C 14.01.2003 Horizontal connection configs (straight lacings)
C 05.01.2003 NEXPER replaced by LPG
C 03.01.2003 Count crossing-free lacings (OEIS sequence A079410)
C 17.12.2002 Initial version
C
C N is the number of eyelets in one row.
C N=8 takes approx 1 day CPU time on an Intel PIII 550MHz,
C     ((2*8-2)!=14! configs to check)
C N=9 is expected to run approx 15*16=240 days on the same CPU.
C
      PARAMETER (N=8, N2=N+N, M=N2-2, N2P=N2+1, N2M=N2-1)
      PARAMETER (NN=N*N+N*N)
      INTEGER E(N2), EE(N,2), A(M)
      INTEGER*8 L
      EQUIVALENCE (E,EE)
C
C FIXED START AND END
      EE(1,1) = 1
      EE(N,2) = N2
C PRESET PERMUTATION ARRAY
      DO 2 I = 1, M
      A(I) = I
2     CONTINUE
C STATUS OF PERMUTATION GENERATION
      NEXT = -1
C COUNTER FOR LEGAL LACINGS
      L = 0
C
      WRITE (*,1003) N
1003  FORMAT ( ' N =', I2, // , ' Non-Straight Lacings', / )
C
10    CONTINUE
C CREATE NEXT PERMUTATION 
      IF ( NEXT .EQ. -1 ) THEN
        NEXT = 1
      ELSE
C Create permutations in lexicographic order
        CALL LPG ( M, A, NEXT )
      ENDIF
      IF ( NEXT .EQ. 0 ) GOTO 200
C INSERT PERMUTED PATH BETWEEN FIXED START AND END
      DO 20 I = 1, M
      E(I+1) = A(I) + 1
20    CONTINUE
C TEST CONDITION THAT THERE IS NO STRAIGHT CONNECTION
C TO THE CORRESPONDING EYELET ON THE OPPOSITE SIDE
      DO 30 I = 2, N2M
      IF ( E(I) .EQ. N2P-E(I-1) ) GOTO 10
      IF ( E(I) .EQ. N2P-E(I+1) ) GOTO 10
C AT LEAST ONE CONNECTION TO OPPOSITE SIDE REQUIRED
      IF ( E(I) .LE. N ) THEN
        IF ( E(I-1) .GT. N ) GOTO 30
        IF ( E(I+1) .GT. N ) GOTO 30
      ELSE
        IF ( E(I-1) .LE. N ) GOTO 30
        IF ( E(I+1) .LE. N ) GOTO 30
      ENDIF
      GOTO 10
30    CONTINUE
C
C COUNT LACINGS
      L = L + 1
C...+....1....+....2....+....3....+....4....+....5....+....6....+....7..
C TO PRINT RESULTS ACTIVATE COMMENTED LINES
C      WRITE (*,1000) L, (E(I),I=1,N2)
C1000  FORMAT (I6, 2I3,:,2I3,:,2I3,:,2I3,:,2I3,:,2I3,:,2I3,:,2I3)
C SKIP BACK TO NEXT PERMUTATION
      GOTO 10
C
200   CONTINUE
C PRINT RESULTS
      WRITE (*,1001) N, L, L/2
1001  FORMAT ( ' N=', I2, ', L=', I12,', LUNDIR:', I11)
      END
....+....1....+....2....+....3....+....4....+....5....+....6....+....7..
Results for N=3 and N=4

 N = 3

 Non-Straight Lacings

      1  1  2  4  5  3  6
      2  1  3  5  4  2  6
      3  1  4  2  3  5  6
      4  1  4  5  3  2  6
      5  1  5  3  2  4  6
      6  1  5  4  2  3  6

 N= 3, L=         6, LUNDIR:        3

....+....1....+....2....+....3....+....4....+....5....+....6....+....7..

 N = 4

 Non-Straight Lacings

      1  1  2  5  3  7  4  6  8
      2  1  2  5  3  7  6  4  8
      3  1  2  5  6  4  3  7  8
      4  1  2  5  6  4  7  3  8
      5  1  2  5  7  3  4  6  8
      6  1  2  6  4  7  3  5  8
      7  1  2  6  4  7  5  3  8
      8  1  2  6  5  3  4  7  8
      9  1  2  6  5  3  7  4  8
     10  1  2  6  7  4  3  5  8
     11  1  3  5  2  6  4  7  8
     12  1  3  5  2  6  7  4  8
     13  1  3  5  6  2  4  7  8
     14  1  3  5  7  4  2  6  8
     15  1  3  5  7  4  6  2  8
     16  1  3  7  4  6  2  5  8
     17  1  3  7  4  6  5  2  8
     18  1  3  7  5  2  4  6  8
     19  1  3  7  5  2  6  4  8
     20  1  3  7  6  4  2  5  8
     21  1  4  6  2  5  3  7  8
     22  1  4  6  2  5  7  3  8
     23  1  4  6  5  2  3  7  8
     24  1  4  6  7  3  2  5  8
     25  1  4  6  7  3  5  2  8
     26  1  4  7  3  5  2  6  8
     27  1  4  7  3  5  6  2  8
     28  1  4  7  5  3  2  6  8
     29  1  4  7  6  2  3  5  8
     30  1  4  7  6  2  5  3  8
     31  1  5  2  3  7  4  6  8
     32  1  5  2  3  7  6  4  8
     33  1  5  2  4  6  7  3  8
     34  1  5  2  6  4  3  7  8
     35  1  5  2  6  4  7  3  8
     36  1  5  2  6  7  3  4  8
     37  1  5  2  6  7  4  3  8
     38  1  5  3  2  6  4  7  8
     39  1  5  3  2  6  7  4  8
     40  1  5  3  4  7  6  2  8
     41  1  5  3  7  4  2  6  8
     42  1  5  3  7  4  6  2  8
     43  1  5  3  7  6  2  4  8
     44  1  5  3  7  6  4  2  8
     45  1  5  6  2  3  7  4  8
     46  1  5  6  2  4  7  3  8
     47  1  5  6  4  7  3  2  8
     48  1  5  7  3  2  6  4  8
     49  1  5  7  3  4  6  2  8
     50  1  5  7  4  6  2  3  8
     51  1  6  2  3  5  7  4  8
     52  1  6  2  4  7  3  5  8
     53  1  6  2  4  7  5  3  8
     54  1  6  2  5  3  4  7  8
     55  1  6  2  5  3  7  4  8
     56  1  6  2  5  7  3  4  8
     57  1  6  2  5  7  4  3  8
     58  1  6  4  2  5  3  7  8
     59  1  6  4  2  5  7  3  8
     60  1  6  4  3  7  5  2  8
     61  1  6  4  7  3  2  5  8
     62  1  6  4  7  3  5  2  8
     63  1  6  4  7  5  2  3  8
     64  1  6  4  7  5  3  2  8
     65  1  6  5  2  3  7  4  8
     66  1  6  5  2  4  7  3  8
     67  1  6  5  3  7  4  2  8
     68  1  6  7  3  5  2  4  8
     69  1  6  7  4  2  5  3  8
     70  1  6  7  4  3  5  2  8
     71  1  7  3  2  5  6  4  8
     72  1  7  3  4  6  2  5  8
     73  1  7  3  4  6  5  2  8
     74  1  7  3  5  2  4  6  8
     75  1  7  3  5  2  6  4  8
     76  1  7  3  5  6  2  4  8
     77  1  7  3  5  6  4  2  8
     78  1  7  4  2  6  5  3  8
     79  1  7  4  3  5  2  6  8
     80  1  7  4  3  5  6  2  8
     81  1  7  4  6  2  3  5  8
     82  1  7  4  6  2  5  3  8
     83  1  7  4  6  5  2  3  8
     84  1  7  4  6  5  3  2  8
     85  1  7  5  2  6  4  3  8
     86  1  7  5  3  2  6  4  8
     87  1  7  5  3  4  6  2  8
     88  1  7  6  2  5  3  4  8
     89  1  7  6  4  2  5  3  8
     90  1  7  6  4  3  5  2  8

 N= 4, L=        90, LUNDIR:       45