8パズル

 投稿者:永野護  投稿日:2011年 1月23日(日)10時49分52秒
  8パズル(3×3)を解くプログラムをつくっています。評価関数としては目標状態と現在の不一致の駒の枚数としてみましたが、千日手になってうまくいきませんでした。
不一致の駒の枚数とマンハッタン距離の和を評価関数とすべきなのでしょうか。
いつもいつもお頼みするばかりで誠に恐縮なのですが山登り法で8パズルを解く方法
をご教授してもらえないでしょうか。
謹具
 

Re: 8パズル

 投稿者:山中和義  投稿日:2011年 1月26日(水)15時23分5秒
  > No.1485[元記事へ]

永野護さんへのお返事です。

> 8パズル(3×3)を解くプログラムをつくっています。

千日手は、過去と同じ盤面になって無限ループになるからです。
履歴をとって、チェックする必要があります。

評価関数はどちらを使ってもうまくいかない場合があります。
局所的な判断ですから、それが大局的に最適かどうかは分かりません。
たとえば、
DATA 6,2,9
DATA 1,7,3
DATA 5,4,8
の場合は、解けません。

マンハッタン距離によるサンプル

LET M=3 !MxNパズル
LET N=3

!DATA 1,6,2 !開始の盤面 ※9は空きを意味する
!DATA 5,7,3
!DATA 9,4,8
DATA 6,9,2
DATA 1,7,3
DATA 5,4,8
DIM B(M*N)
MAT READ B

DATA 1,2,3 !終了の盤面
DATA 4,5,6
DATA 7,8,9
DIM G(M*N)
MAT READ G

DIM H(0 TO 1000,M*N) !盤面の履歴(手順)

CALL hill_climb_search(0,M,N,B,G,H)

END


EXTERNAL SUB hill_climb_search(p,M,N,B(),G(),H(,)) !山登り法
PRINT p;"手" !debug
!!!IF p>=100 THEN EXIT SUB !上限を設定する

FOR j=1 TO M*N !p手目の盤面を記録する
   LET H(p,j)=B(j)
NEXT j


LET C=0 !不一致の駒(数字)の枚数
FOR i=1 TO M*N
   IF B(i)<>G(i) THEN LET C=C+1
   IF B(i)=9 THEN LET sp=i !空きを探す
NEXT i
IF C=0 THEN !終了の盤面なら
   FOR i=p TO 0 STEP -1 !履歴(手順)を表示する
      PRINT i;": ";
      FOR j=1 TO M*N !盤面を表示する
         PRINT H(i,j);
      NEXT j
      PRINT
   NEXT i
   !STOP !1つのみ!!!

ELSE
   DIM S(M*N) !save it
   MAT S=B

   LET E0=cost(M,N,B,G) !現状の盤面の評価値を得る


   !空きの上下左右の位置にある駒(数字)を移動させる
   PRINT sp !debug
   IF sp>N THEN !1行目以外なら、上の数字を移動させる
      LET B(sp)=B(sp-M)
      LET B(sp-M)=9
      IF cost(M,N,B,G)<=E0 THEN !評価値が良くなれば
         MAT PRINT B; !debug
         CALL history(p,M,N,B,H, rc) !新規の盤面なら
         IF rc=0 THEN CALL hill_climb_search(p+1,M,N,B,G,H)
      END IF
      MAT B=S !restore it
   END IF
   IF sp<=M*N-N THEN !M行目以外なら、下の数字を移動させる
      LET B(sp)=B(sp+M)
      LET B(sp+M)=9
      IF cost(M,N,B,G)<=E0 THEN
         MAT PRINT B; !debug
         CALL history(p,M,N,B,H, rc)
         IF rc=0 THEN CALL hill_climb_search(p+1,M,N,B,G,H)
      END IF
      MAT B=S
   END IF
   IF MOD(sp-1,M)>0 THEN !1列目以外なら、左の数字を移動させる
      LET B(sp)=B(sp-1)
      LET B(sp-1)=9
      IF cost(M,N,B,G)<=E0 THEN
         MAT PRINT B; !debug
         CALL history(p,M,N,B,H, rc)
         IF rc=0 THEN CALL hill_climb_search(p+1,M,N,B,G,H)
      END IF
      MAT B=S
   END IF
   IF MOD(sp-1,M)<M-1 THEN !N列目以外なら、右の数字を移動させる
      LET B(sp)=B(sp+1)
      LET B(sp+1)=9
      IF cost(M,N,B,G)<=E0 THEN
         MAT PRINT B; !debug
         CALL history(p,M,N,B,H, rc)
         IF rc=0 THEN CALL hill_climb_search(p+1,M,N,B,G,H)
      END IF
      MAT B=S
   END IF

END IF
END SUB

EXTERNAL SUB history(p,M,N,B(),H(,), rc) !同じ盤面かどうか確認する
LET rc=1
FOR i=0 TO p
   FOR j=1 TO M*N
      IF H(i,j)<>B(j) THEN EXIT FOR !並びが異なるなら
   NEXT j
   IF j>M*N THEN EXIT SUB !既出なら
NEXT i
LET rc=0
END SUB

EXTERNAL FUNCTION cost(M,N,B(),G()) !評価関数
LET c=0
FOR i=1 TO M*N
   LET Bx=MOD(B(i)-1,N) !列番号0~N-1
   LET By=INT((B(i)-1)/M) !行番号0~M-1
   LET Gx=MOD(G(i)-1,N)
   LET Gy=INT((G(i)-1)/M)
   !!!PRINT Bx;By; Gx;Gy !debug
   LET c=c+ABS(Bx-Gx)+ABS(By-Gy) !マンハッタン距離
NEXT i
LET cost=c
END FUNCTION
 

8パズル

 投稿者:永野護  投稿日:2011年 1月26日(水)16時15分22秒
  山中様、大変お手数をおかけしました。貴重なプログラムを作って頂いた事に
心より感謝します。お忙しい中、本当にすいませんでした。山登り法というのは完全ではないということがわかりました。
私としては解が1つあればよかったのですが。パズルの問題というのはどれもロジックが難しいです。
私が住んでいる高知市も最低気温は氷点下のときがあります。まだまだ寒い日が続きますが、くれぐれもお体を大切になさって下さい。
謹具
 

Re: 8パズル

 投稿者:山中和義  投稿日:2011年 1月28日(金)16時36分5秒
  > No.1487[元記事へ]

永野護さんへのお返事です。

3x3の場合、盤面の数は181,440通り。最適解の最長手数は、31手です。
これより、手数の上限を設ければバックトラック法で解を見つけることができます。
1つ見つかれば、これを上限として、それより手数が少ないものを見つけようとします。
探索途中で、より手数が少ないものが、より早く見つかれば、処理時間は速くなります。


!M行N列パズル 最適解の最長手数
!
!3x3の場合、盤面の数は181,440通り。31手
!
!  DATA 6,4,7 ![1]
!  DATA 8,5,9
!  DATA 3,2,1
!
!  DATA 8,6,7 ![2]
!  DATA 2,5,4
!  DATA 3,9,1
!の2つ。


LET M=3 !M行N列パズル
LET N=3

DATA 6,2,9 !開始の盤面 ※9は空きを意味する
DATA 1,7,3
DATA 5,4,8
DIM B(M*N)
MAT READ B
MAT PRINT B; !debug

DATA 1,2,3 !終了の盤面
DATA 4,5,6
DATA 7,8,9
DIM G(M*N)
MAT READ G
MAT PRINT G; !debug

PUBLIC NUMERIC cMAX
LET cMAX=31

DIM H(0 TO cMAX,M*N) !盤面の履歴(手順)

CALL hill_climb_search(0,M,N,B,G,H)

END


EXTERNAL SUB hill_climb_search(p,M,N,B(),G(),H(,)) !山登り法
!!!PRINT p;"手" !debug

FOR j=1 TO M*N !p手目の盤面を記録する
   LET H(p,j)=B(j)
NEXT j


LET c=cost(M,N,B,G)
IF p+c-1>cMax THEN EXIT SUB !残り手数(予想)と上限から、これ以降の展開は諦める

IF c=0 THEN !終了の盤面なら
   LET cMAX=p

   FOR i=0 TO p !履歴(手順)を表示する
      PRINT i;": ";
      FOR j=1 TO M*N !盤面を表示する
         PRINT H(i,j);
      NEXT j
      PRINT
   NEXT i
   PRINT

   !STOP !1つのみ!!!

ELSE
   DIM S(M*N) !save it
   MAT S=B

   !空きの上下左右の位置にある駒(数字)を移動させる
   FOR sp=1 TO M*N !空きを探す
      IF B(sp)=M*N THEN EXIT FOR
   NEXT sp
   IF sp>N THEN CALL move(sp-N,sp) !1行目以外なら、上の数字を移動させる
   IF sp<=M*N-N THEN CALL move(sp+N,sp) !M行目以外なら、下の数字を移動させる
   IF MOD(sp-1,N)>0 THEN CALL move(sp-1,sp) !1列目以外なら、左の数字を移動させる
   IF MOD(sp-1,N)<N-1 THEN CALL move(sp+1,sp) !N列目以外なら、右の数字を移動させる

END IF

SUB move(i,j) !i位置からj位置へ移動する
   LET B(j)=B(i) !数字を移動する
   LET B(i)=M*N !空きにする

   CALL history(p,M,N,B,H, rc) !新規の盤面なら
   IF rc=0 THEN CALL hill_climb_search(p+1,M,N,B,G,H)

   MAT B=S !restore it
END SUB
END SUB

EXTERNAL SUB history(p,M,N,B(),H(,), rc) !同じ盤面かどうか確認する
LET rc=1 !既出
FOR i=0 TO p
   FOR j=1 TO M*N
      IF H(i,j)<>B(j) THEN EXIT FOR !並びが異なるなら
   NEXT j
   IF j>M*N THEN EXIT SUB !すべて同じなら
NEXT i
LET rc=0 !新規
END SUB

EXTERNAL FUNCTION cost(M,N,B(),G()) !評価関数
LET c=0
FOR i=1 TO M*N
   IF B(i)<>G(i) THEN LET c=c+1 !不一致の駒(数字)の枚数
NEXT i
LET cost=c
END FUNCTION
 

8パズル

 投稿者:永野護  投稿日:2011年 1月30日(日)11時39分53秒
  山中様、回答ありがとうございました。
お手数をおかけしました。

敬具
 

戻る