散歩コースの探索願い

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

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 !1歩目は東へ ※0:東、1:北、2:西、3:南

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

END


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

   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

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

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

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

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

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

●閉路の候補
東西(奇数)、南北(偶数)の移動に分けて考えると、それぞれの合計が0になるものである。
この組み合わせ(積)の中で、交差するものを除いたものが求めるもの(答え)である。
 位数 奇数 偶数     積 答え
   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) !1~nまでの奇数列、偶数列

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
 

戻る