プロジェクトオイラー Problem 244 「スライダー」 †

Problem 244 「スライダー」 †

おそらく15パズルはご存知だろう. ここでは, 数字の書かれたタイルの代わりに, 7枚の赤いタイルと8枚の青いタイルを使用する.

移動は, タイルの動いた方向(Left, Right, Up, Down)の大文字のイニシャルで表す. すなわち, 最初の状態 (S) から文字列 LULUR を経て状態 (E) にたどり着く.

(S)  , (E) 

各経路は, 以下に示す擬似コードによってチェックサムが計算される:

checksum = 0
checksum = (checksum × 243 + m1) mod 100 000 007
checksum = (checksum × 243 + m2) mod 100 000 007
…
checksum = (checksum × 243 + mn) mod 100 000 007

mk は移動の文字列の k 番目の文字のアスキーコードの値である. アスキーコードは以下の通り:

L	76
R	82
U	85
D	68

上で例に挙げた文字列 LULUR の場合, チェックサムは 19761398 になるだろう.

では, 状態 (S) から始めて, 状態 (T) に到達する最短の経路を全て求めよ.

(S)  , (T) 

最小の長さとなる経路のチェックサム全ての合計を求めよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20244

解法
盤面を一マス2ビットで表現します。
隙間　11
赤　10
青　01
右上から左氏へビットであらわしてあとは同じ手数で同じ盤面のものを統合しながら動的計画法でアセプトです。
最短手数を残すたびに一手先を計算するたびに一手前の盤面と同じになったらそれを削除します。
そして解の手が見つかったらその時点で計算を終了します。
コードのほとんどの処理がＤＰが苦手なＰｒｏｌｏｇ言語にＤＰを行わせるための処理になっており計算本体はかなりコンパクトにまとめたつもりです。


コード実行結果
% 6,090,943 inferences, 1.469 CPU in 1.488 seconds (99% CPU, 4147025 Lips)
出てきた答えのＬｉｓｔ2つ目が答え。


modN(100000007):-!.
seed([[2779096487,0,1]]):-!.
goal([1721329307,_,_]):-!.


move_next_pos(P1,[P2,Mk]):-
      member([D,Mk],[[-1,82],[1,76]]),
      P2 is P1+D,
      0=<P2,
      P2=<15,
      P1//4=:=P2//4.
move_next_pos(P1,[P2,Mk]):-
      member([D,Mk],[[4,85],[-4,68]]),
      P2 is P1+D,
      0=<P2,
      P2=<15.

dells([],List,List):-!.
dells(_,[],[]):-!.
dells([[E,_,_]|Rest],[[E,_,_]|Rest1],Result):-
      !,
      dells(Rest,Rest1,Result).
dells([[E,S1,C1]|Rest],[[E1,CheckSum,Count]|Rest1],[[E1,CheckSum,Count]|Result]):-
      E>E1,
      !,
      dells([[E,S1,C1]|Rest],Rest1,Result).
dells([_|Rest],Es,Result):-
      !,
      dells(Rest,Es,Result).

calc_next(Boards,[E1,CheckSum1,Count]):-
      member([E,CheckSum,Count],Boards),
      between(0,15,P1),
      Bit1 is 3<<(P1*2),
      (E/\Bit1)=:=Bit1,
      move_next_pos(P1,[P2,Mk]),
      Bit2 is 3<<(P2*2),
      Bit3 is (E /\ (3<<(P2*2))),
      Bit4 is (Bit3>>(P2*2))<<(P1*2),
      E1 is E-Bit1-Bit3+Bit2+Bit4,
      modN(Mod),
      CheckSum1 is (CheckSum*243+Mk*Count) mod Mod.

union_sum([],E,[E]):-!.
union_sum([[E,CheckSum,Count]|Rest],[E,CheckSum1,Count1],Result):-
      !,
        modN(Mod),
      CheckSum2 is (CheckSum+CheckSum1 ) mod Mod,
      Count2 is Count+Count1,
      union_sum(Rest,[E,CheckSum2,Count2],Result).
union_sum([[E,CheckSum,Count]|Rest],E1,[E1|Result]):-
      !,
      union_sum(Rest,[E,CheckSum,Count],Result).

dp(_,NowList):-
      goal(X),
      member(X,NowList),
      !,
      write(X).
dp(OldList,NowList):-
      write(s),nl,
      findall(E,calc_next(NowList,E),NextList1),
      msort(NextList1,[Top|NextList2]),
      union_sum(NextList2,Top,NextList3),
      dells(OldList,NextList3,NextList4),
      dp(NowList,NextList4).


main244:-
      seed(Seed),
      dp([],Seed).