|
|
!
! Knight's Tour（ナイト・ツアー）
!
! 注意！出発点に戻る経路 Closed Tour のみに、限定して計算。⇔Open Tour
!
! KNIGHTGR.UB
! Original Version 1990/10/01 by unknown
! Modified Version 1997/04/10 by Aiichi Yamasaki
! Modified Version 2009/01/06 uBASIC から、十進Basic へ移植。
!--------------------
OPTION BASE 0
SET TEXT background "OPAQUE"
SET POINT STYLE 4
!
LET DF=0 ! 0:通常 1:探索過程のstep 2:探索完了毎のstep //debug
LET Xw=6 !8 ! 盤の横巾
LET Yw=6 !8 ! 盤の縦巾
!-----
! Schwenk's Theorem
! For any m × n board with m less than or equal to n,
! a closed knight's tour is always possible
! unless one or more of these three conditions are true:
!１）m and n are both odd
!２）m = 1, 2, or 4; m and n are not both 1
!３）m = 3 and n = 4, 6, or 8
!
LET m= MIN(Xw,Yw)
LET n= MAX(Xw,Yw)
!
IF MOD(m,2)=1 AND MOD(n,2)=1 THEN CALL outer
IF (m=1 OR m=2 OR m=4) AND (m<>1 OR n<>1) THEN CALL outer
IF m=3 AND (n=4 OR n=6 OR n=8) THEN CALL outer
SUB outer
beep
PRINT "Xw=";Xw;"Yw=";Yw;" … No Closed Tour."
STOP
END SUB
!-----
LET D0=INT(192/MAX(MAX(Xw,Yw),8)) ! 盤の１目幅
SET WINDOW -55/D0, 445/D0, 370/D0,-130/D0
PLOT TEXT,AT 0,-50/D0:"Knight's Tour"
LET Xct= 0
LET Yct= -30/D0 ! count--time の位置
CALL guide( 205/D0, 10/D0) ! x,y
!-----init
DIM P_(-2 TO Yw+1,-2 TO Xw+1), E_(-2 TO Yw+1,-2 TO Xw+1), I_(Xw*Yw), DX_(7), DY_(7)
MAT READ DX_,DY_
DATA 2, 1,-1,-2,-2,-1, 1, 2
DATA 1, 2, 2, 1,-1,-2,-2,-1
!-----
IF DF<>0 THEN MAT PRINT USING REPEAT$("## ",8): DX_ ! //debug
IF DF<>0 THEN MAT PRINT USING REPEAT$("## ",8): DY_ ! //debug
!-----init P_
MAT P_=CON
FOR y=0 TO Yw-1
FOR x=0 TO Xw-1
LET P_(y,x)=0
NEXT x
NEXT y
!-----init E_
MAT E_=20*CON
FOR y=0 TO Yw-1
FOR x=0 TO Xw-1
LET E_(y,x)=0
NEXT x
NEXT y
FOR y=0 TO Yw-1
FOR x=0 TO Xw-1
LET c=8
FOR i=0 TO 7
LET c=c-P_(y+DY_(i),x+DX_(i))
NEXT i
LET E_(y,x)=c
NEXT x
NEXT y
!-----
IF DF<>0 THEN MAT PRINT USING REPEAT$(" ##",Xw+4) :P_ ! //debug
IF DF<>0 THEN MAT PRINT USING REPEAT$(" ##",Xw+4) :E_ ! //debug
!-----
LET sp=0 ! 0~(Xw*Yw-1) 階層位置（再帰型のStackPointerに相当）
LET xx=0 ! 開始地点
LET yy=0 ! (0,0)
LET I_(sp)=-1 ! 全階層の方向カウンター
LET Count=0
LET t0=TIME
IF DF<>0 THEN CALL PUTL(xx,yy,0,0,2) ! //debug
DO
LET I_(sp)=I_(sp)+1
LET ii=I_(sp)
IF 7< ii THEN
CALL BACK ! １層戻す。
ELSE
IF P_(yy+DY_(ii),xx+DX_(ii))=0 THEN ! 重複検査。
IF DF<>0 THEN CALL PUTL(xx,yy,DX_(ii),DY_(ii),2) ! //debug
LET xx=xx+DX_(ii)
LET yy=yy+DY_(ii)
LET P_(yy,xx)=1
!-----dec E_
LET E_(yy,xx)= E_(yy,xx)+10
FOR i=0 TO 7
LET E_(yy+DY_(i),xx+DX_(i))= E_(yy+DY_(i),xx+DX_(i))-1
NEXT i
IF DF<>0 THEN CALL DISP_E ! 探索過程の配列 E_ モニター //debug
!----- １層進める。
LET sp=sp+1
LET I_(sp)=-1
IF sp=Xw*Yw THEN
CALL FIN ! １経路の完成。
CALL BACK ! １層戻す。
ELSEIF fnCHECK(xx,yy)<>0 THEN ! 次の重複検査前の、予見検査。
CALL BACK ! １層戻す。
END IF
END IF
END IF
LOOP
SUB BACK
LET P_(yy,xx)=0
!-----inc E_
LET E_(yy,xx)= E_(yy,xx)-10
FOR i=0 TO 7
LET E_(yy+DY_(i),xx+DX_(i))= E_(yy+DY_(i),xx+DX_(i))+1
NEXT i
!-----
LET sp=sp-1
IF sp=0 THEN STOP ! 終了、Count：１倍
!IF sp< 0 THEN STOP ! 終了、Count：２倍（開始点も回転、帰路まで別経路になる）
LET ii=I_(sp)
LET xx=xx-DX_(ii)
LET yy=yy-DY_(ii)
IF DF<>0 THEN CALL PUTL(xx,yy,DX_(ii),DY_(ii),0) ! //debug
END SUB
FUNCTION fnCHECK(x,y) ! 予見検査。
LET c=0
IF sp< Xw*Yw-1 THEN
LET fnCHECK=1 ! 帰りの引数＝１
IF ABS(I_(1)-I_(0))=4 THEN EXIT FUNCTION !return(1)
FOR i=0 TO 7
IF E_(y+DY_(i),x+DX_(i))< 2 THEN
IF E_(y+DY_(i),x+DX_(i))=0 THEN EXIT FUNCTION !return(1)
LET c=c-1
END IF
NEXT i
IF c< -1 THEN
IF sp<>1 THEN EXIT FUNCTION !return(1)
END IF
FOR y=0 TO Yw-1
FOR x=0 TO Xw-1
IF E_(y,x)< 2 THEN
IF E_(y,x)=0 THEN EXIT FUNCTION !return(1)
LET c=c+1
IF c>1 THEN EXIT FUNCTION !return(1)
END IF
NEXT x
NEXT y
END IF
LET fnCHECK=0 ! 帰りの引数＝０
END FUNCTION !return(0)
SUB PUTL(x,y,dx,dy,c)
SET LINE COLOR c
PLOT LINES: x,y; x+dx,y+dy
PLOT POINTS: x+dx,y+dy
END SUB
SUB DISP_E
PRINT
MAT PRINT USING REPEAT$(" ##",Xw+4) :E_
IF DF=1 THEN pause ! //debug
END SUB
SUB FIN
!-----disp_A
SET AREA COLOR 0
PLOT AREA :0,0; Xw-1,0; Xw-1,Yw-1; 0,Yw-1
LET x=0
LET y=0
CALL PUTL(x,y,0,0,2)
FOR s=0 TO Xw*Yw-1
CALL PUTL(x,y,DX_(I_(s)),DY_(I_(s)),2)
LET x=x+DX_(I_(s))
LET y=y+DY_(I_(s))
NEXT s
!-----disp cout--time
LET Count=Count+1
LET t1=INT(TIME-t0)
IF t1< 0 THEN LET t1=t1+86400
PLOT TEXT,AT Xct,Yct :"count= "& STR$(Count)& " ----- "&
&& USING$("%%",MOD(INT(t1/3600),24))& ":"&
&& USING$("%%",MOD(INT(t1/60),60))& ":"& USING$("%%",MOD(t1,60))
IF DF=2 THEN pause ! //debug
END SUB
!----------ガイド表示-----
SUB guide(x,y)
PLOT TEXT,AT x,y: "H V 一巡する経路の数"
PLOT TEXT,AT x,y +20/D0,USING "3x4: can't close ### open 参考": 2
PLOT TEXT,AT x,y +40/D0,USING "5x5: can't close ### open 参考": 304
PLOT TEXT,AT x,y +60/D0,USING "5x6: ##,###,###,###,### closed": 8
PLOT TEXT,AT x,y +80/D0,USING "6x6: ##,###,###,###,### closed": 9862
PLOT TEXT,AT x,y+100/D0,USING "8x8: ##,###,###,###,### closed": 26534728821064
!
PLOT TEXT,AT x,y+140/D0:"Knight の移動規則"
LET x=x+2
LET y=y+160/D0+2
SET LINE COLOR 2
SET AREA COLOR 2
LET j=SQR(5)
FOR i=ATN(0.5) TO 2*PI STEP PI/2
DRAW knight WITH ROTATE(i)*SHIFT(x,y)
DRAW knight WITH ROTATE(-i)*SHIFT(x,y)
NEXT i
FOR j=-2 TO 2
FOR i=-2 TO 2
PLOT POINTS: x+i, y+j
NEXT i
NEXT j
END SUB
PICTURE knight
PLOT LINES: 0,0; j,0
PLOT AREA: j-0.4,-0.16; j,0; j-0.4,0.16; j-0.24,0
PLOT POINTS: j,0
END PICTURE
END
|
|