あるパズルの質問

 投稿者：GAI  投稿日：2010年 6月11日(金)18時30分9秒
  ９個の数字 111222333 が右のように並んでいる。             (111,222,333)

これに対して下のような操作を何回か行って右の形にしたい。  (123,231,312)

３つの成分(111等を成分と呼ぶことにする)のうちの１つから後ろから何個かを取ってそれを順序を変えないで他の成分の後ろに付け加える。

できるだけ短い手数でするにはどのようにすればよいか。

これに対して次のようにすれば６手でできる。

(111,222,333)→(1,222,33311)→(12,22,33311)→(12,2,333112)→(12,23112,33)→(123,23112,3)→(123,231,312)

これに対して
(1111,2222,3333,4444)に対して上の操作をできるだけ少ない回数行って

(1234,2341,3412,4123)にする手順を探したいのですが、可能ですか？ 		 

Re: あるパズルの質問

 投稿者：山中和義  投稿日：2010年 6月11日(金)23時22分48秒
  > No.1249[元記事へ]

GAIさんへのお返事です。

> (1234,2341,3412,4123)にする手順を探したいのですが、可能ですか？

元の数は剰余とみて
( 1111, 2222, 3333, 4444 )
を
( 1555, 2266, 3337, 4444 )
のように変更して考えてみると 
 12 手 ( 1234, 2345, 3456, 4567 )
 11 手 ( 1234, 2345567, 3456, 4 )
 10 手 ( 1234, 23, 3456, 445567 )
  9 手 ( 1234456, 23, 3, 445567 )
  8 手 ( 1234456, 2, 33, 445567 )
  7 手 ( 1, 2234456, 33, 445567 )
  6 手 ( 15567, 2234456, 33, 44 )
  5 手 ( 15567, 223, 33, 444456 )
  4 手 ( 15567, 22, 333, 444456 )
  3 手 ( 1556, 22, 3337, 444456 )
  2 手 ( 1556, 226, 3337, 44445 )
  1 手 ( 155, 2266, 3337, 44445 )
  0 手 ( 1555, 2266, 3337, 4444 )
「場合の数」を減ら工夫
・成分の一番左は基準のため不動とする。
・移動先の数値に連続するように移動する数字の数を選ぶ。
（元からの順を考慮すると、並びは左から昇順になる）

また、３つの数字では（提示された例とは異なりますが、上の規則を適用すると） 
 6 手 ( 123, 234, 345 )
 5 手 ( 12334, 2, 345 )
 4 手 ( 1, 22334, 345 )
 3 手 ( 145, 22334, 3 )
 2 手 ( 145, 22, 3334 )
 1 手 ( 14, 225, 3334 )
 0 手 ( 144, 225, 333 )
 

Ｎ色混合(111,222,333)→(123,231,312)型

 投稿者：山中和義  投稿日：2010年 6月17日(木)11時06分36秒
  > No.1249[元記事へ]

攻略法の１つを示します。（必勝パターン）
!(111,222,333)→(123,231,312)型　※N*(N-1)回

LET N=5 !成分の数


DIM P$(N) !各成分の初期値
FOR i=1 TO N
   LET P$(i)=REPEAT$(fnSTR1$(i),N)
NEXT i
LET S=0 !第s手目
CALL PrintOut(S)


!●前半 - 右端へ収集する　計(N-1)+Σ[k=1,N-2]{k}=N*(N-1)/2回

!■前半の展開
!　目標　10手 (1234,234,34,4,555551111222334)

!Step.1　※(N-1)回
!　右端成分に、１つずつ連続する数字の個数が少なくなるように「並び」の順に数字を集める。

LET y=N !xからyへ移動
FOR i=1 TO N-1
   LET x=i
   LET w$=RIGHT$(P$(x),N-i) !target
   CALL move(x,y,w$,x) !move it
NEXT i
PRINT

!Step.2　※Σ[k=1,N-2]{k}回
!　左端成分から右端手前の成分までは、残りの数字を使って、
!　各成分で１つずつ数字の個数が少なくなるように「並び」の順に数字を集める。
!理由
!　(1,2-2,3-3-3,4-4-4-4,555551111222334)
!　　 ↑　 ↑　　↑
!　　１個、２個、３個をそれぞれ移動させる

FOR k=1 TO N-2
   LET x=k+1 !この位置の左側へ
   LET w$=RIGHT$(P$(x),k) !target
   FOR y=1 TO k
      CALL move(x,y,w$,1) !move it
   NEXT y
NEXT k
PRINT
PRINT



!●後半 - 右端 -5-5-5-51-1-1-12-2-23-34 を分配する　Σ[k=1,N-1]{k}=N*(N-1)/2回

!■後半の展開
!・右端成分の数字列を「並び」になるように数字列を分割する。
!　※ハイフォンの数が移動回数となる。
!・その「並び」を置ける位置へ移動させる。最後の２文字を埋めるのは、「並び」が２文字に限る。
!　例 -51は、２番目の成分234を埋める。
!　※最終パターンを最後２文字が「並び」になるように分割する。これを目安にする。
!
!　目標　10手 (1234-5,234-51,34-5-12,4-5-1-23,5-1-2-34)
!
!理由
!　-5-5-5-51　４個
!　-1-1-12　　３個
!　-2-23　　　２個
!　-34　　　　１個をそれぞれ移動させる

LET x=N !右端の移動させる数字列
LET w$=RIGHT$(P$(x),N*(N+1)/2-1)

FOR k=N-1 TO 1 STEP -1

   LET w1=fnVAL1(LEFT$(w$,1))

   FOR j=1 TO k-1 !最初に１文字を埋める　※-5-5-5,-1-1,-2
      FOR y=1 TO N !左端から一巡内で順に探す
         LET t=LEN(P$(y))
         !PRINT x;y;w$;L !debug

         IF t>=N OR t=N-2 THEN !「Ｎ文字揃っている」か「残りが２文字」なら、スキップする
         !nop
         ELSE
            LET pp=fnVAL1(RIGHT$(P$(y),1)) !結合部分が「並び」になるなら
            IF pp+1=w1 OR pp+1=w1+N THEN
               CALL move(x,y,w$,1) !move it
               EXIT FOR
            END IF
         END IF
      NEXT y
      IF y>N THEN !場所がない（発生しないはず）
         PRINT "アルゴリズムのエラーです。"
         STOP
      END IF
   NEXT j


   LET y=N-k+1 !最後に２文字を埋める　※-51,-12,-23,-34
   CALL move(x,y,w$,2) !move it

NEXT k


SUB move(x,y,w$,L) !xからyへ移動
   LET P$(x)=LEFT$(P$(x),LEN(P$(x))-LEN(w$)) !move it
   LET P$(y)=P$(y)&w$

   LET S=S+1 !dump it
   CALL PrintOut(S)

   LET x=y !配置位置を記録する
   LET w$=RIGHT$(w$,LEN(w$)-L) !L文字切り出す。次へ
END SUB

SUB PrintOut(S) !成分を表示する
   PRINT USING "### 手 ( ":S;
   PRINT P$(1);
   FOR t=2 TO N
      PRINT ", ";P$(t);
   NEXT t
   PRINT " )";

   PRINT USING " ## → ## ":x,y; !移動詳細
   PRINT " ";w$
END SUB


!Ｎ進法表記

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

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

END

実行結果 
  0 手 ( 11111, 22222, 33333, 44444, 55555 )  0 →  0
  1 手 ( 1, 22222, 33333, 44444, 555551111 )  1 →  5  1111
  2 手 ( 1, 22, 33333, 44444, 555551111222 )  2 →  5  222
  3 手 ( 1, 22, 333, 44444, 55555111122233 )  3 →  5  33
  4 手 ( 1, 22, 333, 4444, 555551111222334 )  4 →  5  4

  5 手 ( 12, 2, 333, 4444, 555551111222334 )  2 →  1  2
  6 手 ( 1233, 2, 3, 4444, 555551111222334 )  3 →  1  33
  7 手 ( 123, 23, 3, 4444, 555551111222334 )  1 →  2  3
  8 手 ( 123444, 23, 3, 4, 555551111222334 )  4 →  1  444
  9 手 ( 1234, 2344, 3, 4, 555551111222334 )  1 →  2  44
 10 手 ( 1234, 234, 34, 4, 555551111222334 )  2 →  3  4


 11 手 ( 123455551111222334, 234, 34, 4, 5 )  5 →  1  55551111222334
 12 手 ( 12345, 234, 345551111222334, 4, 5 )  1 →  3  5551111222334
 13 手 ( 12345, 234, 345, 4551111222334, 5 )  3 →  4  551111222334
 14 手 ( 12345, 23451111222334, 345, 45, 5 )  4 →  2  51111222334
 15 手 ( 12345, 23451, 345, 45111222334, 5 )  2 →  4  111222334
 16 手 ( 12345, 23451, 345, 451, 511222334 )  4 →  5  11222334
 17 手 ( 12345, 23451, 3451222334, 451, 51 )  5 →  3  1222334
 18 手 ( 12345, 23451, 34512, 451, 5122334 )  3 →  5  22334
 19 手 ( 12345, 23451, 34512, 4512334, 512 )  5 →  4  2334
 20 手 ( 12345, 23451, 34512, 45123, 51234 )  4 →  5  34
 

戻る