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

おしどりの遊び
21型
　●○●○●○空空
　　　↓
　空空○○○●●●

実際にプログラムで調べてみると

●N= 3
No. 1
  0 212121__ 2
  1 2__12112 5
  2 2211__12 7
  3 221112__ 1
  4 __111222
No. 2
  0 212121__ 5
  1 2121__21 2
  2 2__11221 7
  3 221112__ 1
  4 __111222

●N= 4
No. 1
  0 21212121__ 2
  1 2__1212112 5
  2 2211__2112 8
  3 2211112__2 1
  4 __11112222

●N= 5
No. 1
  0 2121212121__ 2
  1 2__121212112 7
  2 221121__2112 4
  3 221__1122112 10
  4 221111122__2 1
  5 __1111122222

●N= 6
No. 1
  0 212121212121__ 2
  1 2__12121212112 5
  2 2211__21212112 10
  3 221112212__112 6
  4 22111__1222112 12
  5 22111111222__2 1
  6 __111111222222

●N= 7
No. 1
  0 21212121212121__ 2
  1 2__1212121212112 9
  2 22112121__212112 6
  3 22112__112212112 11
  4 2211221112__2112 5
  5 2211__1112222112 14
  6 2211111112222__2 1
  7 __11111112222222
No. 2
  0 21212121212121__ 6
  1 21212__121212112 9
  2 21212211__212112 2
  3 2__1221112212112 11
  4 2211221112__2112 5
  5 2211__1112222112 14
  6 2211111112222__2 1
  7 __11111112222222


n≧4で、n回で移動できそうだ。


（証明）
n≧4で、n回で移動できると仮定する。
つまり
　●○●○ … ●○●○空空
　　　　↓
　空空○○○○ … ●●●●
とする。

このとき、n=k+4（k≧4）について（成り立つことを示す）

０手　●○●○│●○●○ … ●○●○│●○●○空空　2
　　　　　　　　　└── 2*k個 ──┘
と３つの部分に分割する。

１手　●空空○│●○●○ … ●○●○│●○●○○●　2*k+5
２手　●●○○│●○●○ … ●○●○│空空●○○●

仮定から、『 │●○●○ … ●○●○│空空 』の部分は、k回で移動できて
ｋ手　●●○○│空空○○○○ … ●●●●│●○○●　2*k+8

３手　●●○○│○○○○○○ … ●●●●│●空空●　1
４手　空空○○│○○○○○○ … ●●●●│●●●●
となり、k+4回で移動できる。
よって、n=4,5,6,7で成り立っているので、n≧4で成立する。
（証明終り）



実際に、N=9を計算すると

N=9=k+4より、k=5となる。

  1234 567890123456 7890
0 2121 212121212121 21__　2
1 2__1 212121212121 2112　2*k+5=15
2 2211 2121212121__ 2112

2 2211 2121212121__ 2112　2　+4=6　※N=5より
3 2211 2__121212112 2112　7　+4=11
4 2211 221121__2112 2112　4　+4=8
5 2211 221__1122112 2112　10 +4=14
6 2211 221111122__2 2112　1　+4=5
7 2211 __1111122222 2112

7 2211 __1111122222 2112　2*k+8=18
8 2211 111111122222 2__2　1
9 __11 111111122222 2222

LET t0=TIME


PUBLIC NUMERIC N !数字の数
LET N=7

PUBLIC STRING S$ !開始パターン
LET S$=REPEAT$("21",N)&"__"
PRINT S$

PUBLIC STRING G$ !終了パターン
LET G$="__"&REPEAT$("1",N)&REPEAT$("2",N)
PRINT G$

PUBLIC STRING R$(0 TO 100) !手の記録
FOR i=1 TO 100
   LET R$(i)=""
NEXT i
LET R$(0)=S$

PUBLIC NUMERIC S(0 TO 100)
MAT S=ZER

PUBLIC NUMERIC C !解答数
LET C=0

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


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

END


EXTERNAL SUB try(p,B$) !バックトラック法
IF B$=G$ THEN !完成したなら
   LET C=C+1
   PRINT "No.";C

   FOR i=0 TO p-1
      PRINT USING "### ": i;
      PRINT R$(i); S(i)
   NEXT i
   PRINT USING "### ": p;
   PRINT R$(p)

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

   CALL Calc(B$,b12,b21)

   LET y=POS(B$,"__",1) !移動先

   FOR x=1 TO LEN(B$)-1 !移動元の候補
      LET T$=B$(x:x+1)
      SELECT CASE T$
      CASE "11","12","21","22"
         LET M$=B$
         LET M$(x:x+1)="__" !move it
         LET M$(y:y+1)=T$

         CALL Calc(M$,m12,m21)
         IF NOT(m12>b12 OR m21>b21) THEN

            FOR i=0 TO p !盤面の重複を確認する
               IF M$=R$(i) THEN EXIT FOR !既出なら
            NEXT i
            IF i>p THEN !新規なら

            !!!PRINT p+1; M$ !debug
               LET R$(p+1)=M$
               LET S(p)=x
               CALL try(p+1,M$) !次へ

            END IF

         END IF
      CASE ELSE
      END SELECT
   NEXT x

END IF
END SUB

EXTERNAL SUB Calc(T$,a,b) !評価関数
LET a=0
LET b=0
FOR i=1 TO LEN(T$)-1
   IF T$(i:i+1)="12" THEN LET a=a+1
   IF T$(i:i+1)="21" THEN LET b=b+1
NEXT i
END SUB

!おしどりの遊び（21型）の一般手順

LET N=9 !数字の数


!開始パターン
LET S$=REPEAT$("21",N)&"__" !21型

!終了パターン
LET G$="__"&REPEAT$("1",N)&REPEAT$("2",N)


DIM B(4,7) !N=4～7の手順
DATA 2,5, 8, 1, 0, 0,0 !4
DATA 2,7, 4,10, 1, 0,0 !5
DATA 2,5,10, 6,12, 1,0 !6
DATA 2,9, 6,11, 5,14,1 !7
MAT READ B

DIM P(0 TO N-1) !手順
LET M=MOD(N,4)
FOR i=1 TO 7
   LET P(i-1)=B(M+1,i)
NEXT i

!再帰的に４手を付加する
LET M=M+4
DO WHILE M<N
   FOR i=M-1 TO 0 STEP -1 !ｋ手
      LET P(i+2)=P(i)+4 !shift left
   NEXT i

   LET P(0)=2 !１手を付加する
   LET P(1)=2*M+5 !２手
   LET P(M+2)=2*M+8 !３手
   LET P(M+3)=1 !４手

   LET M=M+4
LOOP


!結果を表示する
PRINT "N=";N

LET M$=S$
FOR i=0 TO N-1 !N手の手順を表示する
   PRINT USING "###: ": i;
   PRINT M$; P(i)

   LET x=P(i) !移動元
   LET y=POS(M$,"__") !移動先
   LET w$=M$(x:x+1) !move it
   LET M$(x:x+1)="__"
   LET M$(y:y+1)=w$
NEXT i
PRINT USING "###: ": N;
PRINT M$


END

・並びが反対、空き位置が反対
　　21型
　　空空●○●○●○
　　　　↓
　　●●●○○○空空

　　21型
　　空空●○●○●○
　　　　↓
　　○○○●●●空空


・どちらかの石が一つ多い場合
　●○●○●○●空空
　　　↓
　○○○●●●●空空


・３種類
　●○◎●○◎空空
　　　↓
　●●○○◎◎空空

●N= 2
解なし

●N= 3
No. 1
  0 __121212 4
  1 211__212 2
  2 2__11212 6
  3 22111__2 1
  4 __111222

●N= 4
No. 1
  0 __12121212 3
  1 12__121212 8
  2 1221121__2 2
  3 1__1121222 6
  4 12111__222 1
  5 __11112222
No. 2
  0 __12121212 4
  1 211__21212 2
  2 2__1121212 6
  3 22111__212 9
  4 22111122__ 1
  5 __11112222
No. 3
  0 __12121212 5
  1 1212__1212 8
  2 1212211__2 4
  3 121__11222 6
  4 12111__222 1
  5 __11112222
No. 4
  0 __12121212 7
  1 121212__12 4
  2 121__22112 8
  3 1211122__2 6
  4 12111__222 1
  5 __11112222

●N= 5
No. 1
  0 __1212121212 4
  1 211__2121212 2
  2 2__112121212 10
  3 221112121__2 5
  4 2211__121122 9
  5 22111112__22 1
  6 __1111122222
No. 2
  0 __1212121212 4
  1 211__2121212 9
  2 21112212__12 1
  3 __1122122112 5
  4 2211__122112 10
  5 221111122__2 1
  6 __1111122222
No. 3
  0 __1212121212 4
  1 211__2121212 9
  2 21112212__12 1
  3 __1122122112 10
  4 111122122__2 5
  5 1111__122222 1
  6 __1111122222
No. 4
  0 __1212121212 4
  1 211__2121212 9
  2 21112212__12 5
  3 2111__122212 2
  4 2__111122212 10
  5 221111122__2 1
  6 __1111122222
No. 5
  0 __1212121212 4
  1 211__2121212 11
  2 2111221212__ 5
  3 2111__121222 2
  4 2__111121222 8
  5 2211111__222 1
  6 __1111122222
No. 6
  0 __1212121212 5
  1 1212__121212 8
  2 1212211__212 11
  3 1212211122__ 4
  4 121__1112222 7
  5 121111__2222 1
  6 __1111122222
No. 7
  0 __1212121212 5
  1 1212__121212 10
  2 121221121__2 1
  3 __1221121122 4
  4 221__1121122 9
  5 22111112__22 1
  6 __1111122222
No. 8
  0 __1212121212 5
  1 1212__121212 10
  2 121221121__2 1
  3 __1221121122 9
  4 11122112__22 4
  5 111__1122222 1
  6 __1111122222
No. 9
  0 __1212121212 6
  1 21121__21212 2
  2 2__211121212 10
  3 221211121__2 3
  4 22__11121122 9
  5 22111112__22 1
  6 __1111122222
No. 10
  0 __1212121212 9
  1 12121212__12 2
  2 1__212122112 5
  3 1122__122112 10
  4 112211122__2 3
  5 11__11122222 1
  6 __1111122222
No. 11
  0 __1212121212 9
  1 12121212__12 4
  2 121__2122112 1
  3 __1122122112 5
  4 2211__122112 10
  5 221111122__2 1
  6 __1111122222
No. 12
  0 __1212121212 9
  1 12121212__12 4
  2 121__2122112 1
  3 __1122122112 10
  4 111122122__2 5
  5 1111__122222 1
  6 __1111122222
No. 13
  0 __1212121212 9
  1 12121212__12 6
  2 12121__22112 3
  3 12__11222112 10
  4 121111222__2 7
  5 121111__2222 1
  6 __1111122222
No. 14
  0 __1212121212 10
  1 211212121__2 5
  2 2112__121122 1
  3 __1221121122 4
  4 221__1121122 9
  5 22111112__22 1
  6 __1111122222
No. 15
  0 __1212121212 10
  1 211212121__2 5
  2 2112__121122 1
  3 __1221121122 9
  4 11122112__22 4
  5 111__1122222 1
  6 __1111122222
No. 16
  0 __1212121212 10
  1 211212121__2 5
  2 2112__121122 2
  3 2__211121122 4
  4 221__1121122 9
  5 22111112__22 1
  6 __1111122222

●N= 6
No. 1
  0 __121212121212 3
  1 12__1212121212 12
  2 12211212121__2 5
  3 1221__12121122 11
  4 1221111212__22 2
  5 1__11112122222 8
  6 1211111__22222 1
  7 __111111222222
No. 2
  0 __121212121212 4
  1 211__212121212 2
  2 2__11212121212 8
  3 2211121__21212 11
  4 2211121122__12 6
  5 22111__1222112 12
  6 22111111222__2 1
  7 __111111222222
No. 3
  0 __121212121212 4
  1 211__212121212 11
  2 2111221212__12 5
  3 2111__12122212 2
  4 2__11112122212 8
  5 2211111__22212 13
  6 221111112222__ 1
  7 __111111222222
No. 4
  0 __121212121212 4
  1 211__212121212 13
  2 211122121212__ 5
  3 2111__12121222 2
  4 2__11112121222 8
  5 2211111__21222 11
  6 2211111122__22 1
  7 __111111222222
No. 5
  0 __121212121212 5
  1 1212__12121212 8
  2 1212211__21212 11
  3 1212211122__12 2
  4 1__22111222112 12
  5 11122111222__2 4
  6 111__111222222 1
  7 __111111222222
No. 6
  0 __121212121212 5
  1 1212__12121212 12
  2 12122112121__2 7
  3 121221__121122 11
  4 1212211112__22 4
  5 121__111122222 8
  6 1211111__22222 1
  7 __111111222222
No. 7
  0 __121212121212 5
  1 1212__12121212 12
  2 12122112121__2 9
  3 12122112__1122 4
  4 121__112221122 11
  5 1211111222__22 8
  6 1211111__22222 1
  7 __111111222222
No. 8
  0 __121212121212 6
  1 21121__2121212 2
  2 2__21112121212 8
  3 2212111__21212 11
  4 2212111122__12 4
  5 221__111222112 12
  6 22111111222__2 1
  7 __111111222222
No. 9
  0 __121212121212 7
  1 121212__121212 12
  2 12121221121__2 3
  3 12__1221121122 11
  4 1211122112__22 6
  5 12111__1122222 8
  6 1211111__22222 1
  7 __111111222222
No. 10
  0 __121212121212 8
  1 2112121__21212 3
  2 21__1211221212 12
  3 21211211221__2 2
  4 2__11211221122 6
  5 22111__1221122 11
  6 2211111122__22 1
  7 __111111222222
No. 11
  0 __121212121212 8
  1 2112121__21212 5
  2 2112__11221212 2
  3 2__21111221212 12
  4 22121111221__2 3
  5 22__1111221122 11
  6 2211111122__22 1
  7 __111111222222
No. 12
  0 __121212121212 8
  1 2112121__21212 5
  2 2112__11221212 10
  3 211221112__212 4
  4 211__111222212 2
  5 2__11111222212 12
  6 22111111222__2 1
  7 __111111222222
No. 13
  0 __121212121212 8
  1 2112121__21212 5
  2 2112__11221212 12
  3 21122111221__2 4
  4 211__111221222 2
  5 2__11111221222 10
  6 221111112__222 1
  7 __111111222222
No. 14
  0 __121212121212 8
  1 2112121__21212 11
  2 2112121122__12 4
  3 211__211222112 2
  4 2__11211222112 6
  5 22111__1222112 12
  6 22111111222__2 1
  7 __111111222222
No. 15
  0 __121212121212 8
  1 2112121__21212 11
  2 2112121122__12 6
  3 21121__1222112 2
  4 2__21111222112 4
  5 221__111222112 12
  6 22111111222__2 1
  7 __111111222222
No. 16
  0 __121212121212 9
  1 12121212__1212 4
  2 121__212211212 13
  3 121122122112__ 5
  4 1211__12211222 10
  5 121111122__222 8
  6 1211111__22222 1
  7 __111111222222
No. 17
  0 __121212121212 11
  1 1212121212__12 4
  2 121__212122112 7
  3 121122__122112 12
  4 12112211122__2 5
  5 1211__11122222 8
  6 1211111__22222 1
  7 __111111222222
No. 18
  0 __121212121212 11
  1 1212121212__12 4
  2 121__212122112 9
  3 12112212__2112 5
  4 1211__12222112 12
  5 12111112222__2 8
  6 1211111__22222 1
  7 __111111222222
No. 19
  0 __121212121212 11
  1 1212121212__12 8
  2 1212121__22112 5
  3 1212__11222112 2
  4 1__22111222112 12
  5 11122111222__2 4
  6 111__111222222 1
  7 __111111222222
No. 20
  0 __121212121212 12
  1 21121212121__2 3
  2 21__1212121122 8
  3 2121121__21122 2
  4 2__11211221122 6
  5 22111__1221122 11
  6 2211111122__22 1
  7 __111111222222
No. 21
  0 __121212121212 12
  1 21121212121__2 5
  2 2112__12121122 2
  3 2__21112121122 8
  4 2212111__21122 3
  5 22__1111221122 11
  6 2211111122__22 1
  7 __111111222222

!おしどりの遊び（12型）の一般手順

LET N=14 !数字の数　※N≧7

!開始パターン
LET S$="__"&REPEAT$("12",N)

!終了パターン
LET G$="__"&REPEAT$("1",N)&REPEAT$("2",N)

DIM P(0 TO N) !手順 N+1手

LET M=N-3
CALL oshidori(M, P)
FOR i=M TO 0 STEP -1 !Ｍ手
   LET P(i+1)=P(i)+3 !shift right
NEXT i

LET P(0)=2*M+4 !１手を付加する
LET P(M+1)=2 !２手
LET P(M+2)=2*M+6 !３手
LET P(M+3)=1 !４手

!結果を表示する
PRINT "N=";N

LET M$=S$
FOR i=0 TO N !(N+1)手の手順を表示する
   PRINT USING "###: ": i;
   PRINT M$; P(i)

   LET x=P(i) !移動元
   LET y=POS(M$,"__") !移動先
   LET w$=M$(x:x+1) !move it
   LET M$(x:x+1)="__"
   LET M$(y:y+1)=w$
NEXT i
PRINT USING "###: ": N+1;
PRINT M$

END

EXTERNAL SUB oshidori(N, P()) !21型　2121…21__ → __111…222…
DATA 2,5, 8, 1, 0, 0,0 !4
DATA 2,7, 4,10, 1, 0,0 !5
DATA 2,5,10, 6,12, 1,0 !6
DATA 2,9, 6,11, 5,14,1 !7

DIM B(4,7) !N=4～7の手順
MAT READ B

LET M=MOD(N,4)
FOR i=1 TO 7
   LET P(i-1)=B(M+1,i)
NEXT i

!再帰的に４手を付加する
LET M=M+4
DO WHILE M<N
   FOR i=M-1 TO 0 STEP -1 !ｋ手
      LET P(i+2)=P(i)+4 !shift right
   NEXT i

   LET P(0)=2 !１手を付加する
   LET P(1)=2*M+5 !２手
   LET P(M+2)=2*M+8 !３手
   LET P(M+3)=1 !４手

   LET M=M+4
LOOP
END SUB