十進BASIC 第2掲示板 過去ログ

 21 00654321 4
 20 30654021 3
 19 30654201 2
 18 30654210 1
 17 30054216 6
 16 30504216 5
 15 30540216 4
 14 03540216 3
 13 23540016 2
 12 23540106 1
 11 23540160 6
 10 23045160 5
  9 23405160 4
  8 20435160 3
  7 02435160 2
  6 12435060 1
  5 12435006 6
  4 12430056 5
  3 12030456 4
  2 12003456 3
  1 10023456 2
  0 00123456 1

!□□１２３４５のように数字が並んでいる。□は空白を意味する。
!これらの数字を、次のルールに従って並べ替える。
!（ルール）
!　1.１→２→３→４→５→１→２→ … と数字の順番に数字を、どちらかの空白に移動する。
!　2.１回の操作で動かせる数字は、ひとつだけとする。
!
!このとき、次のように数字を並べ替えるには、最低何回の操作が必要であろうか？
!　□□１２３４５ → □□５４３２１


!n=5の場合　PentiumⅢ700MHz,192MB,WindowsMe、２進モードにて
! 13 0054321 4
! 12 0354021 3
! 11 2354001 2
! 10 2354010 1
!  9 2304510 5
!  8 2340510 4
!  7 2043510 3
!  6 0243510 2
!  5 1243500 1
!  4 1243005 5
!  3 1203045 4
!  2 1200345 3
!  1 1002345 2
!  0 0012345 1
!計算時間= 4.45000000000073


LET t0=TIME

LET N=5 !数字 １～Ｎ

LET S$="00" !初期 001234…N
FOR i=1 TO N
   LET S$=S$&STR$(i)
NEXT i

LET G$="00" !完成形 00N…4321
FOR i=N TO 1 STEP -1
   LET G$=G$&STR$(i)
NEXT i

DIM M$(100000),L(100000),O(100000) !盤面
LET M$(1)=S$
LET L(1)=0
LET O(1)=1 !移動させる数字
LET CNT=1

LET p=1
DO WHILE p<=CNT !収束したら、終了！

   LET w=O(p) !順番に　1,2,3,4,…,N,1,2,3,4,…
   LET w$=STR$(MOD(w-1,N)+1)

   LET y=0
   FOR z=1 TO 2 !２箇所
      LET T$=M$(p)

      LET x=POS(T$,w$) !移動元位置
      LET y=POS(T$,"0",y+1) !移動先位置
      LET T$(x:x)="0"
      LET T$(y:y)=w$
      !!!PRINT x;y;T$ !debug

      FOR i=1 TO CNT !新規盤面か？
         IF M$(i)=T$ AND O(i)=w+1 THEN EXIT FOR
      NEXT i
      IF i>CNT THEN !登録する
         LET CNT=CNT+1

         LET M$(CNT)=T$ !盤面
         LET L(CNT)=p !元
         LET O(CNT)=w+1 !手数
      END IF

      IF T$=G$ THEN EXIT DO !完成なら、終了！

   NEXT z

   LET p=p+1
LOOP


PRINT p;CNT !debug

CALL PrintOut(CNT)
SUB PrintOut(t)
   DO WHILE t>0 !手を遡る
      PRINT USING "### ":O(t)-1; !盤面
      PRINT M$(t); MOD(O(t)-1,N)+1

      LET t=L(t) !次へ
   LOOP
END SUB

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

END

LET t0=TIME


PUBLIC NUMERIC N !数字１～Ｎ
PUBLIC NUMERIC cMAX !見つかった最少手数
PUBLIC NUMERIC B(100) !最初のＮ手、最後のＮ手

!LET N=2
!LET cMAX=3
!DATA 2,3 !最初の2手　※数字を移動させる空白位置。1を２、2を３を意味する。
!DATA 3,4 !最後の2手　※数字を移動させる空白位置。2を３、1を４を意味する。

!LET N=3
!LET cMAX=5
!DATA 1,2, 3 !最初の3手
!DATA 3, 5,4 !最後の3手

!LET N=4
!LET cMAX=6
!DATA 1,2, 4,3 !最初の4手
!DATA 4,3, 6,5 !最後の4手

!LET N=5
!LET cMAX=13
!DATA 1,2, 4,3, 6 !最初の5手　※数字を移動させる空白位置。1を２、2を１、3を４、4を３、5を６を意味する。
!DATA 4,3,  7,6,5 !最後の5手　※数字を移動させる空白位置。4を４、5を３、1を７、2を６、3を５を意味する。

!LET N=6
!LET cMAX=21
!DATA 1,2, 4,3, 6,7 !最初の6手
!DATA 5,4,3,  8,7,6 !最後の6手

!LET N=7
!LET cMAX=25
!DATA 1,2, 4,5,3, 7,8 !最初の7手
!DATA 5,4,3,  9,8,7,6 !最後の7手

!LET N=8
!LET cMAX=28
!DATA 1,2, 4,5,3, 7,8,9 !最初の8手
!DATA 6,5,4,3, 10,9,8,7 !最後の8手

!LET N=9
!LET cMAX=41
!DATA 1,2, 4,5,6,3, 8,9,10 !最初の9手
!DATA 6,5,4,3, 11,10,9,8,7 !最後の9手

!LET N=10
!LET cMAX=55
!DATA 1,2, 4,5,6,3, 8,9,10,11 !最初の10手
!DATA 7,6,5,4,3, 12,11,10,9,8 !最後の10手

LET N=11
LET cMAX=61
DATA 1,2, 4,5,6,7,3, 9,10,11,12 !最初の11手
DATA 7,6,5,4,3, 13,12,11,10,9,8 !最後の11手

!LET N=12
!LET cMAX=78
!DATA 1,2, 4,5,6,7,3, 9,10,11,12,13 !最初の12手
!DATA 8,7,6,5,4,3, 14,13,12,11,10,9 !最後の12手


PRINT "N=";N; "cMAX=";cMAX !debug

MAT B=ZER
FOR i=1 TO N
   READ B(i)
NEXT i
FOR i=cMax-N+1 TO cMax
   READ B(i)
NEXT i
MAT PRINT B; !debug

PUBLIC NUMERIC SPC !空きの数
LET SPC=2

PUBLIC STRING S$ !開始パターン
LET S$=REPEAT$("0",SPC)
FOR i=1 TO N
   LET S$=S$&fnSTR1$(i)
NEXT i
!!!PRINT S$ !debug

PUBLIC STRING G$ !終了パターン
LET G$=REPEAT$("0",SPC)
FOR i=N TO 1 STEP -1
   LET G$=G$&fnSTR1$(i)
NEXT i
!!!PRINT G$ !debug

PUBLIC NUMERIC C !解答数
LET C=0

DIM A(cMAX) !手数

CALL try(0,S$,A)
IF C=0 THEN PRINT "解なし"


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

END


EXTERNAL SUB try(p,M$,A()) !深さ優先探索
IF M$=G$ THEN !完成なら
   LET C=C+1
   PRINT "No.";C

   MAT PRINT A; !debug
   LET T$=S$ !盤面を表示する
   FOR i=0 TO p-1 !手を再現する
      LET w$=fnSTR1$(MOD(i,N)+1) !移動させる数字
      PRINT USING "## ": i; !盤面
      PRINT T$; " ";w$

      LET x=POS(T$,w$) !移動元
      LET y=A(i+1) !移動先
      LET T$(x:x)="0" !move it
      LET T$(y:y)=w$
   NEXT i
   PRINT USING "## ": p; !盤面
   PRINT T$
   PRINT

   LET cMAX=p !最少手数を更新する

ELSE
   IF p+1>cMAX THEN EXIT SUB !高々

   LET w$=fnSTR1$(MOD(p,N)+1) !移動させる数字

   LET y=0
   FOR z=1 TO SPC !２つの空きへ
      LET y=POS(M$,"0",y+1) !移動先
      IF B(p+1)=0 OR y=B(p+1) THEN

         LET x=POS(M$,w$) !移動元
         LET T$=M$ !move it
         LET T$(x:x)="0"
         LET T$(y:y)=w$
         !PRINT p;T$ !debug

         IF N>8 AND p+1=INT((cMAX-2*N)/N)*N THEN !チェックポイント！　※N=9,10,11
            LET v=N-INT((N+1)/2)-2
            IF T$(3:3+v)=G$(5:5+v) THEN
               LET A(p+1)=y !手を記録する
               CALL try(p+1,T$,A) !次へ
            END IF
         ELSEIF N>8 AND p+1=INT((cMAX-N)/N)*N THEN !チェックポイント！　※N=7はNG
            LET v=N-INT((N+1)/2)-1
            IF T$(3:3+v)=G$(4:4+v) THEN
               LET A(p+1)=y !手を記録する
               CALL try(p+1,T$,A) !次へ
            END IF
         ELSE
            LET A(p+1)=y !手を記録する
            CALL try(p+1,T$,A) !次へ
         END IF

      END IF
   NEXT z

END IF
END SUB


!Ｎ進法表記

EXTERNAL FUNCTION fnVAL1(x$) !１文字の数字を数値に変換する
LET fnVAL1=POS("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ",x$)-1
END FUNCTION

EXTERNAL FUNCTION fnSTR1$(x) !１桁の数値を数字に変換する
LET fnSTR1$=MID$("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ",x+1,1)
END FUNCTION