DOBON.NETお気楽掲示板

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 検索

■1523 / 親記事) 　Ｐｒｏｌｏｇの練習にライツアウトの最長手数を求める
  ▼■
□投稿者/ 堀江伸一 -(2013/06/14(Fri) 18:06:53)
  • アイコンＳＷＩ-Ｐｒｏｌｏｇでライツアウトの最長手数を求めるプログラムを書いてみました。

    ０手で解けるのは１通り。
    最短１手で解ける盤面は２５通り。
    最短２手で解ける盤面は３００通り。
    、、、
    という感じで答えを表示します。
    コードを書いてみましたが４手あたりを求める計算をさせてる時点でパソコンが凄い音を立て計算時間もやたらかかりまあす。
    これを高速かつ低メモリで解けるようにするにはどうすれば良いでしょうか？

    後私の書き込みにマナー違反な面があればご指摘下さい。
    できるだけネットのマナーを守りたいと考えています。

    盤面の状態は左上から右下について点灯してたら１消灯してたら0としてビット列と解釈して自然数として表し。
    Ｎ手目の状態を一つずつ調べ、次の状態は２５個のどれかのボタンを押して次の状態がＮ-1手目の状態と同じでないならＮ+1手目として登録するという処理になっています。
    宜しくお願いします。

    push_button2(N,State,NextState):-
    R is N // 5,
    C is N mod 5,
    nth0(C,[3,7,14,28,24],XorM),
    nth0(C,[1,2,4,8,16],XorU),
    XorM1 is XorM<<(5*R),
    (R>0 -> XorU1 is XorU<<(5*(R-1));XorU1 is 0),
    (R<4 -> XorD1 is XorU<<(5*(R+1));XorD1 is 0),
    NextState is State xor (XorU1 \/ XorM1 \/ XorD1).

    b_search(_,Down,Up,_):-Up<Down,fail.
    b_search(List,Down,Up,No):-
    Down=<Up,
    M is (Down+Up)//2,
    nth0(M,List,X),
    (X<No->Down1 is M+1,b_search(List,Down1,Up,No);true),
    (X>No->Up1 is M-1,b_search(List,Down,Up1,No);true),
    true.
    push_one(NowList,OldList,NextState,OldSize,NowSize):-
    select(State,NowList,_),
    between(0,24,N),
    push_button2(N,State,NextState),
    not(b_search(OldList,0,OldSize,NextState)),
    not(b_search(NowList,0,NowSize,NextState)),
    true.

    next_search(P,OldList,Now):-
    length(Now,NowSize),
    length(OldList,OldSize),
    NowSize1 is NowSize-1,
    OldSize1 is OldSize-1,
    write([P,NowSize]),
    P<4,
    findall(State,(push_one(Now,OldList,State,OldSize1,NowSize1)),Next),
    sort(Next,Next1),
    write('ok'),nl,
    P1 is P+1,
    next_search(P1,Now,Next1).
引用返信 削除キー/


スレッド内ページ移動 / << 0 >>

このスレッドに書きこむ
Pass/

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 検索

- Child Tree -