このパズルのプログラムを作ってください

 投稿者:YU  投稿日:2012年 8月26日(日)08時55分20秒
  こんにちは。
こちらの掲示板は十進BASICをDLさせて頂いてからよく拝見しています。

思いついたパズルを何とか形にできないかと無い頭で格闘しています。
でも、どこからどう取り掛かったらいいのやらサッパリで、悶々とする毎日です。
恐れ入りますが、次のようなパズルの解を求めるプログラムを作ってみていただけないでしょうか。

ちょうど“じゃんけん”のような三すくみの関係の「手」があり、下図のようにあらかじめマスに配置された「手」と「自手」が互い
に一手ずつ出し合って対戦していくとき、「始」から「終」まで勝ち進めるような「自手」を求める、というパズルです。

・あらかじめ与えられている条件は、各マスの「手」の配置と「自手」の手数だけで、マス内の手の配置は例えば下図のように。
 自手の手数は例えば「四手」というふうに。
・手(A,B,C)の強弱関係は、たとえば「A>B>C>A…」となっているとします。
・求めたい解は、たとえば手数が四手なら、「ACCB」というふうな形になります。
・最初に対戦するマスは「始」の直下か右隣りのマスで、自手は第一手(上の例ならA)から開始する。自手が勝てばそのマスに進行し、
 次のマスと次の自手で対戦。以下これを繰り返す。
・“あいこ”の場合はその場に留まり、同じマスに対し自手だけを次の手に進めて再戦する。
・次に進行できる(対戦する)マスは現在の位置の縦または横隣りのマスで、斜めには進めない。また、通過済みのマスにも進めない。
・自手が負けるマスには進めない、というより、その対戦自体が無効。
・自手は同じ順番で循環して出す(上の例なら「ACCBACCB……」と繰り返す)。

  ┏━┳━┳━┳━┳━┓
  ┃始┃B┃C┃B┃C┃
  ┣━╋━╋━╋━╋━┫
  ┃C┃A┃A┃C┃B┃
  ┣━╋━╋━╋━╋━┫
  ┃B┃A┃B┃C┃A┃
  ┣━╋━╋━╋━╋━┫
  ┃C┃B┃C┃A┃B┃
  ┣━╋━╋━╋━╋━┫
  ┃A┃C┃A┃C┃終┃
  ┗━┻━┻━┻━┻━┛

こうして対戦を進め「終」まで到達できれば、そのときの自手が「解」(の一つ)となります。

パズルとしては唯一解(仮に進行コースは複数あったとしても自手は唯一つ)でないと問題になりませんが、この条件で解が
どの程度存在し得るのかをまず確かめないことには、そもそもこれがパズルとして成立するのかどうかさえ定かではありません。

そこでお願いですが、マス内の手の配置と自手の手数を任意に設定したとき、解となる自手と、できればその進行コースを求
めてくれるプログラムを作っていただけないでしょうか。
その際、その部分が何を行なっているのかが分かるよう要所要所に注釈を入れていただきながらだと嬉しいです。
それか、フローチャートのような、プログラム全体の流れが把握できるような図なり文章なりを頂けるなら、きっと
他のパズルにも応用できて、なお助かります。

まことに図々しいお願いですが、どうかよろしくお願いいたします。
 

Re: このパズルのプログラムを作ってください

 投稿者:山中和義  投稿日:2012年 8月26日(日)20時35分44秒
  > No.1959[元記事へ]

YUさんへのお返事です。

>   ┏━┳━┳━┳━┳━┓
>   ┃始┃B┃C┃B┃C┃
>   ┣━╋━╋━╋━╋━┫
>   ┃C┃A┃A┃C┃B┃
>   ┣━╋━╋━╋━╋━┫
>   ┃B┃A┃B┃C┃A┃
>   ┣━╋━╋━╋━╋━┫
>   ┃C┃B┃C┃A┃B┃
>   ┣━╋━╋━╋━╋━┫
>   ┃A┃C┃A┃C┃終┃
>   ┗━┻━┻━┻━┻━┛



LET M=5 !マスの大きさ M×N
LET N=5

DATA 9,1,2,1,2 !A=0,B=1,C=2
DATA 2,0,0,2,1
DATA 1,0,1,2,0
DATA 2,1,2,0,1
DATA 0,2,0,2,9

LET P=4 !自手の手数


PRINT "最少手数=";M+N-2

PUBLIC NUMERIC C !解の個数
LET C=0

DIM A(M,N) !マスの手
MAT READ A

DIM R(M,N)
MAT R=(-1)*CON

DIM B(P) !自手のパターン(並び)
FOR i=0 TO 3^P-1 !3^P通り
   LET t=i
   FOR J=1 TO P !3進法p桁へ
      LET B(P-J+1)=MOD(t,3)
      LET t=INT(t/3)
   NEXT J
   MAT PRINT USING REPEAT$(" #",P): B;
   PRINT " の場合"

   LET X=1 !Y行X列 ※左上がスタート位置
   LET Y=1
   LET R(Y,X)=0 !進路
   CALL try(0,Y,X,M,N,A,P,B,R)
NEXT i

END


EXTERNAL SUB try(S,Y,X,M,N,A(,),P,B(),R(,)) !バックトラック法で検索する
IF X>1 THEN !左端以外なら左へ(列の範囲を確認する)
   IF R(Y,X-1)<0 THEN !未踏なら
      CALL Judge(S,Y,X-1,M,N,A,P,B,R)
   END IF
END IF

IF X<N THEN !右端以外なら右へ(列の範囲を確認する)
   IF R(Y,X+1)<0 THEN !未踏なら
      IF Y=M AND X+1=N THEN !右下なら、ゴール!
         LET C=C+1 !結果を表示する
         PRINT "No.";C
         MAT PRINT USING REPEAT$(" ##",N): R; !進路
         PRINT " ";S+1;"手" !手数
      ELSE
         CALL Judge(S,Y,X+1,M,N,A,P,B,R)
      END IF
   END IF
END IF

IF Y>1 THEN !上端以外なら上へ(行の範囲を確認する)
   IF R(Y-1,X)<0 THEN !未踏なら
      CALL Judge(S,Y-1,X,M,N,A,P,B,R)
   END IF
END IF

IF Y<M THEN !下端以外なら下へ(行の範囲を確認する)
   IF R(Y+1,X)<0 THEN !未踏なら
      IF Y+1=M AND X=N THEN !右下なら、ゴール!
         LET C=C+1
         PRINT "No.";C
         MAT PRINT USING REPEAT$(" ##",N): R; !進路
         PRINT " ";S+1;"手" !手数
      ELSE
         CALL Judge(S,Y+1,X,M,N,A,P,B,R)
      END IF
   END IF
END IF
END SUB

EXTERNAL SUB Judge(S,Y,X,M,N,A(,),P,B(),R(,)) !対戦を判定する
FOR L=1 TO P !連続P回の引き分けまで
   LET SS=S+L
   LET me=B(MOD(SS-1,P)+1) !自手(巡回させる)を得る
   LET you=A(Y,X)
   LET W=MOD(you-me+3,3) !判定 ※0=引き分け,1=勝ち,2=負け

   IF W=2 THEN !負けなら
      EXIT FOR !終了!!!

   ELSEIF W=1 THEN !勝ちなら、進める
      LET R(Y,X)=SS !仮に進める
      CALL try(SS,Y,X,M,N,A,P,B,R) !次の対戦へ
      LET R(Y,X)=-1 !元に戻す

      EXIT FOR !終了!!!
   END IF
NEXT L
END SUB


実行結果

最少手数= 8
0 0 0 0 の場合
0 0 0 1 の場合
0 0 0 2 の場合
0 0 1 0 の場合
0 0 1 1 の場合
0 0 1 2 の場合
0 0 2 0 の場合
0 0 2 1 の場合
No. 1
  0  1 -1 -1 -1
  4  3 11 12 13
  5  7  9 16 15
-1 -1 20 19 -1
-1 -1 23 24 -1  25 手
No. 2
  0  1 -1 -1 -1
  4  3 11 12 13
  5  7  9 16 15
-1 -1 -1 19 21
-1 -1 -1 -1 -1  22 手
No. 3
  0  1 -1 -1 -1
  4  3 11 12 13
  5  7  9 16 15
-1 -1 -1 19 -1
-1 -1 -1 20 -1  21 手
No. 4
  0  1 -1 -1 -1
  4  3 11 12 13
  5  7  9 -1 15
-1 -1 20 19 17
-1 -1 23 24 -1  25 手
No. 5
  0  1 -1 -1 -1
  4  3 11 12 13
  5  7  9 -1 15
-1 -1 -1 19 17
-1 -1 -1 20 -1  21 手
No. 6
  0  1 -1 -1 -1
  4  3 11 12 13
  5  7  9 -1 15
-1 -1 -1 -1 17
-1 -1 -1 -1 -1  18 手
0 0 2 2 の場合
0 1 0 0 の場合
0 1 0 1 の場合
0 1 0 2 の場合
No. 7
  0  1  2 -1 -1
-1 -1  4 -1 -1
-1 -1  5  6  8
-1 -1 -1 -1  9
-1 -1 -1 -1 -1  10 手
No. 8
  0  1  2 -1 -1
-1 -1  4 -1 -1
-1 -1  5  6 -1
-1 -1 -1  8  9
-1 -1 -1 -1 -1  10 手
No. 9
  0  1  2 -1 -1
-1 -1  4 -1 -1
-1 -1  5 -1 -1
-1 -1  6  8  9
-1 -1 -1 -1 -1  10 手
0 1 1 0 の場合
0 1 1 1 の場合
0 1 1 2 の場合
0 1 2 0 の場合
0 1 2 1 の場合
No. 10
  0  1  2 -1 -1
-1 -1  3 -1 -1
-1 -1  5  6  7
-1 -1 -1 -1  9
-1 -1 -1 -1 -1  10 手
No. 11
  0  1  2 -1 -1
-1 -1  3 -1 -1
-1 -1  5  6 -1
-1  9  8  7 -1
-1 10 11 12 -1  13 手

 :
 :

 

Re: このパズルのプログラムを作ってください

 投稿者:YU  投稿日:2012年 8月27日(月)23時25分7秒
  > No.1960[元記事へ]

山中和義さんへのお返事です。

さっそく作って下さって、ありがとうございます!
こんなふうにすればいいんですね!

といっても、細かい部分の具体的な作業の内容がまだ十分に理解できていませんが、
大まかな流れは何となく分かりました。これが自由に使えるようになれば、これから
いろいろなパズルが作れそうだと思うと、とても楽しみです♪

適当に設定したこの例でも2000通り以上も解が出てくるんですね!
このままではとてもパズルにはなりそうもありません。
でも、通過することができないマスを設けるなど、何らかの制限が必要なことが分かり、
それはそれで大いに助かりました。
作って下さったこのプログラムを基に、このやり方をちゃんと自分のモノにして
これからいろんな要素を組み込んでいきたいと思います。


迅速なご応答を下さったのに、お礼が遅くなって申し訳ありません。
初心者の質問で煩わしいかと思いますが、これからもよろしくお願いいたします。
どうもありがとうございました。
 

戻る