散歩コースの探索願い

 投稿者：GAI  投稿日：2009年12月19日(土)20時24分57秒
  ある点から東西南北いずれの方向でもいいから１進む。
そこで直角に曲がり２進む。
さらにそこで直角に曲がり３進む。
これを繰り返していき、直角に曲がってから４，５，６，７の距離進んでいき最後８の距離進んだ時に元の出発点に戻るコースどり（前のコースは横切らないこと。）のパターンを調べてほしい。（これを位数８の散歩コースと呼ぶことにします。）
同じく位数１６の散歩コース
位数２４の散歩コースでは何種類が可能か知りたい。 		 

Re: 散歩コースの探索願い

 投稿者：山中和義  投稿日：2009年12月20日(日)11時08分38秒
  > No.900[元記事へ]

GAIさんへのお返事です。

「横切る」や「同一」の判定は、図形が表示されるので、それを見て確認してください。
!散歩コースの探索

PUBLIC NUMERIC N !歩数
LET N=16

DIM d(N),x(0 TO N),y(0 TO N) !各歩数での方向と位置
MAT d=ZER
MAT x=ZER !原点
MAT y=ZER

LET x(1)=1 !１歩目は東へ　※0:東、1:北、2:西、3:南

CALL search(2,d,x,y) !２歩目以降

END


EXTERNAL SUB search(s,d(),x(),y()) !バックトラックで検索する
FOR i=-1 TO 1 STEP 2 !右と左のみ
   LET dd=MOD(d(s-1)+i,4) !１つ前を基準にする

   LET xx=x(s-1) !現在の位置
   LET yy=y(s-1)
   SELECT CASE dd !s歩目の移動距離
   CASE 0 !E
      LET xx=xx+s
   CASE 1 !N
      LET yy=yy+s
   CASE 2 !W
      LET xx=xx-s
   CASE 3 !S
      LET yy=yy-s
   CASE ELSE
   END SELECT
   LET x(s)=xx !進める
   LET y(s)=yy

   LET d(s)=dd !s歩目の方向

   IF s=N THEN !指定の歩数に達したら
      IF x(N)=x(0) AND y(N)=y(0) THEN !元の位置に戻ったら
         MAT PRINT d;

         SET bitmap SIZE 600,600 !作画して交差などを確認する
         SET WINDOW -40,40,-40,40
         CLEAR
         DRAW grid(5,5)
         SET LINE width 2
         SET TEXT HEIGHT 1.5 !※調整が必要である
         SET TEXT JUSTIFY "center","half"
         FOR k=1 TO N
            SET LINE COLOR 1 !奇数と偶数で色分け
            IF MOD(k,2)=0 THEN SET LINE COLOR 4
            PLOT LINES: x(k-1),y(k-1); x(k),y(k) !軌跡
            PLOT TEXT ,AT (x(k-1)+2*x(k))/3,(y(k-1)+2*y(k))/3: STR$(k)
         NEXT k
         SET LINE width 1 !restore it

         pause !OK?
         !INPUT PROMPT "OKかNGを入力してください。": y$

      END IF
   ELSE
      CALL search(s+1,d,x,y) !次へ
   END IF
NEXT i
END SUB

!回答、情報、アルゴリズム、パズル

!１歩目を東（水平方向）へ固定すると
!奇数目は水平方向（東西方向）、偶数目は垂直方向（南北方向）になる。
!式で表現すると
! x=±1±3±5±7
! y=±2±4±6±8
!プラスマイナスの組合せで０になるかどうかの検証になる。
 

Re: 散歩コースの探索願い

 投稿者：山中和義  投稿日：2010年 1月 4日(月)12時29分28秒
  > No.902[元記事へ]

90°の連結等角多角形（ポリオミノ）による閉路

●閉路の候補
東西（奇数）、南北（偶数）の移動に分けて考えると、それぞれの合計が０になるものである。
この組み合わせ（積）の中で、交差するものを除いたものが求めるもの（答え）である。
　位数　奇数　偶数　　　　　積　答え
　　 7　　 1　　 1　 　　　　1　　 1
　　 8　　 1　　 1　 　　　　1　　 1
　　15　　 4　　 4　 　　　 16　　 1
　　16　　 4　　 7　　　　　28　　 3
　　23　　34　　35　　　　1190　　25
　　24　　34　　62　　　　2108　　67
　　：（この範囲は未確認）
　　32　 346　 657　　　227322　　？
　　：（未確認）
　　40　3965　7636　　30276740　　？
　　：（未確認）
　　48 48396 93846　4541771016　　？
　　：（未確認）

先のプログラム（No.958[元記事へ]）では、交差判定による枝刈りを行っているが、N=32は相当時間がかかる。
上記のように処理すると、32や40が計算可能になる。


●候補の個数（、符号パターン）を求めるプログラム
LET t0=TIME

LET N=24 !位数

LET w=INT((N-1)/2)+1 !概算
DIM A(w) !１～ｎまでの奇数列、偶数列

LET m=0
FOR i=1 TO N
   IF MOD(i,2)=1 THEN !奇数なら
   !IF MOD(i,2)=0 THEN !偶数なら　←←←←←
      LET m=m+1
      LET A(m)=i
   END IF
NEXT i
redim A(m)


LET ANSWER_COUNT=0

DIM B(m)
FOR i=0 TO 2^(m-1)-1 !ビットパターンで検証する　※MSB=0
   MAT B=CON
   LET t$=right$(REPEAT$("0",m)&BSTR$(i,2),m) !m桁
   FOR k=1 TO LEN(t$)
      IF t$(k:k)="1" THEN LET B(k)=-1 !0:1、1:-1へ
   NEXT k

   IF DOT(A,B)=0 THEN !±1*1 + ±1*3 + … + ±1*(2*m+1)を計算する
      LET ANSWER_COUNT=ANSWER_COUNT+1
      !!!PRINT "DATA ";CHR$(34);t$;CHR$(34)
   END IF
NEXT i

PRINT "個数=";ANSWER_COUNT !奇数の個数
PRINT


PRINT "計算時間=";TIME-t0

END
 

戻る