Description:
DxDの大きさの盤面があり、各マスには1からD^2-1までの数値と、'X'が1つずつ存在している。
'X'と、'X'の上下左右に隣接している数字の場所を引っくり返すという操作を1手とする。
N手以内(0<=N<=15)で初期盤面から終了盤面へと変化させる事が出来るか?
可能な時は、最短手数を求めよ。
Answer:
まともにやると、4^15 = 10億盤面の探索となり、時間が足りない。
BFSで枝刈りを行うか、両側探索を行えば良い。
N-Puzzle問題では、各駒のゴールまでのステップ数の和/2が楽観的なゴールまでの手数の良い推量になるので、指定手数以内に辿り着けない枝を刈れば間に合う。
両側探索は、スタートから8手、ゴールから7手全生成し、双方に含まれる盤面の内、手数の和が最も小さくなるものを選べば良い。
Source: