|
|
> No.3084[元記事へ]
GAIさんへのお返事です。
> この手数を更に減らすことは不可能だと思います。
いろいろやってみました。確かに52手が最少です。
> ただ角から移動することは一度も検討してはいないが・・・
同様な流れ（決り手）になるもので検索すると、5分程度で見つかりました。
角を左へ
0: 飛銀金 金銀角
×銀金玉金銀×
↓
xx: 角飛銀金玉銀金
× 銀金銀金×
飛車を右へ
↓
40: 角銀金金飛銀金
×銀金玉 銀×
40: 角銀金玉飛銀金
×銀金金 銀×
↓ 11手
51: 角銀金 金銀飛
×銀金玉金銀×
51 手
角を左へ
0: 飛銀金 金銀角
×銀金玉金銀×
1: 飛銀金玉金銀角
×銀金 金銀×
2: 飛銀金玉金銀角
×銀金金 銀×
3: 飛銀金玉金 角
×銀金金銀銀×
4: 飛銀金玉 金角
×銀金金銀銀×
5: 飛銀金玉銀金角
×銀金金銀 ×
6: 飛銀金玉銀金
×銀金金銀角×
7: 飛銀金玉銀 金
×銀金金銀角×
8: 飛銀金玉銀銀金
×銀金金 角×
9: 飛銀金玉銀銀金
×銀金 金角×
10: 飛銀金玉 銀金
×銀金銀金角×
11: 飛銀金玉角銀金
×銀金銀金 ×
12: 飛銀金玉角銀金
×銀金銀 金×
13: 飛銀金 角銀金
×銀金銀玉金×
14: 飛銀金銀角銀金
×銀金 玉金×
15: 飛銀金銀 銀金
×銀金角玉金×
16: 飛銀金銀玉銀金
×銀金角 金×
17: 飛銀金 玉銀金
×銀金角銀金×
18: 飛銀 金玉銀金
×銀金角銀金×
19: 飛銀角金玉銀金
×銀金 銀金×
20: 飛銀角金玉銀金
×銀 金銀金×
21: 飛 角金玉銀金
×銀銀金銀金×
22: 飛銀角金玉銀金
× 銀金銀金×
23: 飛銀 金玉銀金
×角銀金銀金×
24: 飛銀銀金玉銀金
×角 金銀金×
25: 飛 銀金玉銀金
×角銀金銀金×
26: 飛銀金玉銀金
×角銀金銀金×
27: 角飛銀金玉銀金 ←←←
× 銀金銀金×
飛車を右へ
28: 角飛 金玉銀金
×銀銀金銀金×
29: 角 飛金玉銀金
×銀銀金銀金×
30: 角銀飛金玉銀金
×銀 金銀金×
31: 角銀飛金玉銀金
×銀金 銀金×
32: 角銀飛 玉銀金
×銀金金銀金×
33: 角銀 飛玉銀金
×銀金金銀金×
34: 角銀金飛玉銀金
×銀金 銀金×
35: 角銀金飛 銀金
×銀金玉銀金×
36: 角銀金飛銀銀金
×銀金玉 金×
37: 角銀金飛銀銀金
×銀金玉金 ×
38: 角銀金飛 銀金
×銀金玉金銀×
39: 角銀金 飛銀金
×銀金玉金銀×
40: 角銀金金飛銀金 ←←←
×銀金玉 銀×
41: 角銀金金飛 金
×銀金玉銀銀×
42: 角銀金金飛金
×銀金玉銀銀×
43: 角銀金金飛金銀
×銀金玉銀 ×
44: 角銀金金飛 銀
×銀金玉銀金×
45: 角銀金金 飛銀
×銀金玉銀金×
46: 角銀金金金飛銀
×銀金玉銀 ×
47: 角銀金金金飛
×銀金玉銀銀×
48: 角銀金金金 飛
×銀金玉銀銀×
49: 角銀金金金銀飛
×銀金玉 銀×
50: 角銀金金 銀飛
×銀金玉金銀×
51: 角銀金 金銀飛
×銀金玉金銀×
上記の流れを見つける専用（枝刈りの部分）のプログラムです。
前出の飛車を移動させて、その後角を移動させる場合も同じようなものになります。
!パズル - 将棋駒の入れ替え
!7×2 飛車と角を入れ替える
! 飛銀金 金銀角 → 角銀金 金銀飛
! ×銀金玉金銀× ×銀金玉金銀×
!答え 51手
LET t0=TIME
PUBLIC NUMERIC xSIZE,ySIZE !盤の大きさ
LET xSIZE=7
LET ySIZE=2
DECLARE STRING INIT$ !初期の状態
LET INIT$="飛銀金 金銀角×銀金玉金銀×"
PUBLIC STRING GOAL$ !完成の状態
LET GOAL$="角銀金 金銀飛×銀金玉金銀×"
PUBLIC NUMERIC LIM !手数の上限 →最少手数
LET LIM=52
!---------- ↓↓↓↓↓ ---------- 盤面の正当性を確認する
IF LEN(INIT$)<>ySIZE*xSIZE THEN
PRINT "盤の大きさ（xSIZE,ySIZE）と駒の数（INIT$）が合いません。"
STOP
END IF
IF LEN(GOAL$)<>ySIZE*xSIZE THEN
PRINT "盤の大きさ（xSIZE,ySIZE）と駒の数（GOAL$）が合いません。"
STOP
END IF
FOR p=1 TO ySIZE*xSIZE !盤を走査して空白を見つける
IF INIT$(p:p)=" " THEN EXIT FOR
NEXT p
IF p>ySIZE*xSIZE THEN
PRINT "空白がありません。"
STOP
END IF
!---------- ↑↑↑↑↑ ----------
PUBLIC STRING KO$(5) !駒の種類と移動可能範囲 ※８近傍 動きは将棋と同じ
!DATA "×○××歩××××"
DATA "○○○×銀×○×○"
DATA "○○○○金○×○×"
DATA "○○○○玉○○○○"
DATA "×○×○飛○×○×"
DATA "○×○×角×○×○"
FOR i=1 TO UBOUND(KO$)
READ KO$(i)
NEXT i
PUBLIC STRING STK$(0 TO 200) !局面の記録 ※スタック
FOR i=0 TO 200
LET STK$(i)=""
NEXT i
PUBLIC NUMERIC C !解の個数
LET C=0
LET STK$(0)=INIT$
CALL backtrack(1,p) !１手目
IF C=0 THEN PRINT "解なし"
PRINT "計算時間=";TIME-t0;"秒"
END
EXTERNAL SUB backtrack(L,p) !１手ずつ打っていき、行き詰まれば元に戻ってやり直す
LET bd$=stk$(L-1) !現在の局面
!---------- ↓↓↓↓↓ ---------- 枝刈り
IF L<=30 THEN !飛車の移動
FOR i=1 TO ySIZE*xSIZE !誘導
IF bd$(i:i)="角" THEN EXIT FOR
NEXT i
IF L>15 AND (i=13 OR i=7) THEN EXIT SUB
IF L>20 AND (i=5 OR i=13 OR i=7) THEN EXIT SUB
IF L>24 AND NOT(i=1 OR i=9 OR i=3 OR i=11) THEN EXIT SUB
IF L>27 AND NOT(i=1 OR i=9) THEN EXIT SUB
IF bd$(9:9)="角" AND bd$(1:1)="銀" THEN EXIT SUB !禁じ手
IF bd$(1:1)="角" THEN !決り手
PRINT L
IF NOT(bd$(6:7)="銀金" AND bd$(13:13)="金") THEN EXIT SUB !決り手
END IF
ELSE !角の移動
IF NOT(bd$(1:1)="角") THEN EXIT SUB
FOR i=1 TO ySIZE*xSIZE !誘導
IF bd$(i:i)="飛" THEN EXIT FOR
NEXT i
IF L>35 AND (i=1 OR i=2 OR i=9 OR i=3 OR i=10) THEN EXIT SUB
IF L>40 AND NOT(bd$(2:3)="銀金" AND bd$(9:10)="銀金") THEN EXIT SUB !決り手
IF bd$(6:6)="飛" AND bd$(7:7)="金" THEN EXIT SUB !禁じ手
END IF
!---------- ↑↑↑↑↑ ----------
LET px=MOD(p-1,xSIZE)+1 !水平・垂直の座標へ
LET py=INT((p-1)/xSIZE)+1
FOR d=1 TO 9 !隣接する駒を探す
IF d=5 THEN
ELSE
LET mx=px + MOD(d-1,3)-1 !移動元の座標 ※dを水平・垂直の差分dx,dyへ
LET my=py + INT((d-1)/3)-1
IF (mx>=1 AND mx<=xSIZE) AND (my>=1 AND my<=ySIZE) THEN !盤内か確認する
LET mp=(my-1)*xSIZE + mx !連番へ
LET t$=bd$(mp:mp)
IF t$="×" OR t$=" " THEN
ELSE
FOR a=1 TO UBOUND(KO$) !駒の属性を得る
IF t$=KO$(a)(5:5) THEN EXIT FOR
NEXT a
IF KO$(a)(10-d:10-d)="×" THEN !移動可能範囲なら
ELSE
LET w$=bd$
LET w$(p:p)=t$ !移動させる
LET w$(mp:mp)=" "
IF w$=GOAL$ THEN !完成なら、手順を記録しておく
LET C=C+1
PRINT L;"手"
FOR i=0 TO L-1
PRINT STR$(i);": ";STK$(i)
NEXT i
PRINT STR$(L);": ";w$
LET LIM=L !上限を狭める
ELSE
FOR t=L TO 0 STEP -1 !最近の局面から順に新しい手かどうか確認する
IF STK$(t)=w$ THEN EXIT FOR
NEXT t
IF t<0 THEN
LET STK$(L)=w$ !記録して、次の局面へ
IF L<LIM THEN CALL backtrack(L+1,mp) !上限まで
END IF
END IF
END IF
END IF
END IF
END IF
NEXT d
END SUB
|
|