Previous Up No next

Hamilton path programs

Below some more Hamilton path counting programs. I think these were developed rather late, as it uses some ideas from the PASCAL programs.

Program HAM

The following program is coded completely in Acorn Basic. 
    1 a
   10 INPUT"N",N
   20 INPUT"M",M
   30 DIMFF100,BB100
   35 DIMRR3;RR0=1;RR1=N+1;RR2=-1;RR3=-N-1
   36 DIMGG(N*M)
   40 FORI=0TO(N+1)
   50 FORJ=0TO(M+1)
   55 P=I+(N+1)*J
   60 IFI=0ORJ=0ORI=N+1ORJ=M+1 FFP=1;BBP=0;G.90
   65 FFP=0
   70 IFI=1ORJ=1ORI=N ORJ=M BBP=1;G.90
   80 BBP=0
   90 N.;N.
  100 L=M*N-1
  110 INPUT"I",I
  120 INPUT"J",J
  130 P=I+(N+1)*J;R=0
  140 B=BBP
  150 GOS.c
  160 PR.C
  170 END
 1000 cG=0;C=0
 1001 bPR.'"NEXT "GGG
 1005 G=G+1;FFP=1;P=P+RRR;GOS.t
 1010 IFG=L C=C+1;G.1800
 1030 X=RR((R+1)&3)
 1040 Y=RRR
 1050 Z=RR((R+3)&3)
 1100 IFB=1ORBBP=0G.1300
 1101 PR.'"HIT BORDER"
 1110 B=1
 1120 GOS.l;IFFF(P+R)=0GGG=1130;G.b
 1130 GOS.r;IFFF(P+R)=0GGG=1140;G.b
 1140 GOS.r;IFFF(P+R)=0GGG=1150;G.b
 1150 GOS.l;B=0;G.e
 1300 IFFF(P+Y)=1G.1600
 1310 PR.'"AHEAD FREE";IFFF(P+X)=1G.1500
 1320 PR.'"RIGHT FREE";IFFF(P+Z)=1G.1400
 1330 PR.'"LEFT  FREE";IFFF(P+Y+X)=1ORFF(P+Y+Z)=1G.e
 1340 GOS.l;GGG=1350;G.b
 1350 GOS.r;GGG=1360;G.b
 1360 GOS.r;GGG=1370;G.b
 1370 GOS.l;G.e
 1400 PR.'"LEFT  PIN";IFFF(P+Y+X)=1PR.'"BLOCK RIGHT/AHEAD";G.e
 1410 GOS.r;GGG=1420;G.b
 1420 GOS.l;GGG=1800;G.b
 1500 PR.'"RIGHT PIN";IFFF(P+Z)=1;G.1550
 1510 IFFF(P+Y+Z)=1G.e
 1520 GOS.l;GGG=1530;G.b
 1530 GOS.r;GGG=1800;G.b
 1550 PR.'"LEFT  PIN";GGG=1800;G.b
 1600 PR.'"AHEAD PIN";IFFF(P+X)=1G.1650
 1610 PR.'"RIGHT FREE";IFFF(P+Z)=0G.e
 1620 PR.'"LEFT  PIN";GOS.r;GGG=1630;G.b
 1630 GOS.l;G.e
 1650 PR.'"RIGHT PIN";IFFF(P+Z)=1G.e
 1660 PR.'"LEFT  FREE";GOS.l;GGG=1670;G.b
 1670 GOS.r
 1800 A=A
 1900 eP=P-RRR;FFP=0;GOS.t
 1910 G=G-1;IFG>0 PR.'"GOTO "GG(G);G.GG(G)
 1920 R.
 2000 lR=R+3;IFR>3 R=R-4
 2001 R.
 2010 rR=R+1;IFR>3 R=R-4
 2011 R.
 3000 tPR.'"G="G'
 3010 FORJ=0TOM+1
 3020 FORI=0TOM+1
 3025 IFP=I+(N+1)*J PR."P";G.3050
 3030 IFFF(I+(N+1)*J)=1PR."*";G.3050
 3040 PR." "
 3050 N.;PR.":"';N.
 3060 R.

Program MACHAM

This program seems to be a machine language implementation of the above. I faintly remember that it is not working properly. 
  900 DIMLL9,MM1,RR10,KK0
  901 FORI=1TO9;LLI=TOP;N.
  902 FORI=1TO10;RRI=TOP;N.
  903 MM0=TOP;MM1=TOP;KK0=TOP
  910 DIMS4;S?0=1;S?1=32;S?2=255;S?3=224
  920  G=#8100
  921  Q=#8101
  922  R=#8102
  923  L=#8103
  924  X=#8104
  925  Y=#8105
  926  Z=#8106
  927  C=#8107
  928  D=#8108
  930  F=#8000
  931  B=#8010
  932  H=#8120
  940 GOS.a
  950 INPUTI
  960 GOS.a
  970 END
  990 aDIMP(-1)
 1000 [:LL0 LDA@0;STA G
 1001 :LL1 JSR#FFE3;LDX G;STA H,X
 1002  INC G;STX Q;INC F,X
 1010  LDA G;CMP L;BNE LL2
 1011  JSR KK0; JMP LL9
 1012 :LL2
 1030  LDA R;CLC;ADC@1;AND@3;TAX
 1031  LDA S,X;STA X
 1040  LDX R;LDA S,X;STA Y
 1050  LDA R;CLC;ADC@3;AND@3;TAX
 1051  LDA S,X;STA Z
 1100  LDA B; BNE LL3
 1101  LDX Q; LDA B,X; BEQ LL3
 1110  INC D
 1120  JSR MM1;LDA P;CLC
 1121  ADC R;TAX;LDA F,X;BNE RR1
 1122  LDA@1;JMP LL1
 1130 :RR1 JSR MM0;LDA P;CLC
 1131  ADC R;TAX;LDA F,X;BNE RR2
 1132  LDA@2;JMP LL1
 1140 :RR2 JSR MM0;LDA P;CLC
 1141  ADC R;TAX;LDA F,X;BNE RR3
 1142  LDA@3;JMP LL1
 1150 :RR3 JSR MM1;DEC D;JMP LL9
 1300 :LL3 LDY Q
 1301  TYA;CLC;ADC Y
 1302   TAX;LDA F,X;BEQ P+5;JMP LL7
 1310  TYA;CLC;ADC X
 1311   TAX;LDA F,X;BNE LL5
 1320  TYA;CLC;ADC Z
 1321   TAX;LDA F,X;BNE LL4
 1330  TYA;CLC;ADC Y;CLC;ADC X
 1331   TAX;LDA F,X;BEQ P+5;JMP LL9
 1335  TYA;CLC;ADC Y;CLC;ADC Z
 1336   TAX;LDA F,X;BEQ P+5;JMP LL9
 1340  JSR MM1;LDA@4;JMP LL1
 1350 :RR4 JSR MM0;LDA@5;JMP LL1
 1360 :RR5 JSR MM0;LDA@6;JMP LL1
 1370 :RR6 JSR MM1;JMP LL9
 1400 :LL4
 1401  TYA;CLC;ADC Y;CLC;ADC X
 1402   TAX;LDA F,X;BNE LL7
 1420 :RR7 JSR MM1;LDA@11;JMP LL1
 1500 :LL5
 1501  TYA;CLC;ADC Z
 1502   TAX;LDA F,X;BNE LL6
 1510  TYA;CLC;ADC Y;CLC;ADC Z
 1511   TAX;LDA F,X;BNE LL9
 1520  JSR MM1;LDA@8;JMP LL1
 1530 :RR8 JSR MM0;LDA@11;JMP LL1
 1550 :LL6 LDA@11;JMP LL1
 1600 :LL7
 1601  TYA;CLC;ADC X
 1602   TAX;LDA F,X;BNE LL9
 1610  TYA;CLC;ADC X
 1611   TAX;LDA F,X;BNE LL8
 1620 JSR MM0;LDA@9;JMPLL1
 1630 :RR9 JSR MM1;JMPLL9
 1650 :LL8
 1651  TYA;CLC;ADC Z
 1652   TAX;LDA F,X;BEQ LL8
 1660  JSR MM1;LDA@10;JMPLL1
 1670 :RR10 JSR MM0
 1900 :LL9
 1901  LDY R;LDA Q;SEC;SBC S,Y
 1902  STA Q; TAX; DEC F,X
 1910  DEC G;LDX G; LDA H,X
 1921  CMP@1;BNE P+5;JMP RR1
 1922  CMP@2;BNE P+5;JMP RR2
 1923  CMP@3;BNE P+5;JMP RR3
 1924  CMP@4;BNE P+5;JMP RR4
 1925  CMP@5;BNE P+5;JMP RR5
 1926  CMP@6;BNE P+5;JMP RR6
 1927  CMP@7;BNE P+5;JMP RR7
 1928  CMP@8;BNE P+5;JMP RR8
 1929  CMP@9;BNE P+5;JMP RR9
 1930  CMP@10;BNE P+5;JMP RR10
 1931  CMP@11;BNE P+5;JMP LL9
 1940  RTS
 2000 :MM0 LDA R;CLC;ADC@1;AND@3;RTS
 2010 :MM0 LDA R;CLC;ADC@3;AND@3;RTS
 2020 :KK0 INC C;RTS
 2030 ];R.
 3000 gINPUT"N"N;INPUT"M"M
 3010 FORI=0TON+1;FORJ=0TOM+1
 3020 IFI=0ORJ=0ORI=N+1ORJ=M+1 F?(I+#20*J)=1
 3030 F?(I+#20*J)=0
 3040 IFI=1ORJ=1ORI=N ORJ=M B?(I+#20*J)=1
 3050 B?(I+#20*J)=0
 3060 N.;N.
 3070 ?Q=#21;?R=0;?C=0;?D=1
 3080 LINKLL0
 3090 PR.?C