prolog - Prolog でこのパズルを解くには?

Question

Prolog で、数字の 2 乗 (数字のリストのリスト) を取得し、一番上から順に行ごとに数字の最大の組み合わせのリストを返すパズルを解こうとしています。各移動は、下、右、または左のいずれかでなければなりません。

私はしばらくこれをやろうとしてきましたが、誰か私が始められる場所はありますか?

例えばボード上で

 [[0, 2, 1, 0],
  [0, 1, 1, 0],
  [0,10,20,30]]

ベスト ムーブは[1, 2, 3]33 ポイントです。

Answer 1

だからここにあなたがそれを行うことができる方法があります。私はそれがちょっと冗長であることを知っています、それはおそらく私がPrologに堪能ではないからです...

% Lookup a value in a list by it's index.
% this should be built into prolog?
at(0, [H|_], H).
at(N, [_|T], X) :- 
    N > 0,
    N1 is N - 1,
    at(N1, T, X).

% like Haskell's maximumBy; takes a predicate, a 
% list and an initial maximum value, finds the
% maximum value in a list
maxby(_, [], M, M).
maxby(P, [H|T], M0, M) :-
    call(P, H, M0, M1),
    maxby(P, T, M1, M).

% which of two paths has the bigger score?
maxval(path(C,  I), path(C1, _), path(C, I)) :- C >= C1.
maxval(path(C0, _), path(C, I),  path(C, I)) :- C0 < C.

% generate N empty paths as a starting value for
% our search
initpaths(N, Ps) :- 
    findall(path(0, []), 
            between(0, N, _), 
        Ps). 

% given the known best paths to all indexes in the previous
% line and and index I in the current line, select the best
% path leading to I.
select(Ps, I, N, P) :-
    I0 is I-1,
    I1 is I+1,
    select(Ps, I0, N, path(-1, []), P0),
    select(Ps, I,  N, P0, P1),
    select(Ps, I1, N, P1, P).

% given the known best paths to the previous line (Ps),
% an index I and a preliminary choice P0, select the path 
% leading to the index I (in the previous line) if I is within 
% the range 0..N and its score is greater than the preliminary 
% choice. Stay with the latter otherwise.
select(_, I, _, P0, P0) :- I < 0.
select(_, I, N, P0, P0) :- I > N.
select(Ps, I, _, P0, P) :- 
    at(I, Ps, P1),
    maxby(maxval, [P0], P1, P).

% given the known best paths to the previous line (P1),
% and a Row, which is the current line, extend P1 to a 
% new list of paths P indicating the best paths to the
% current line.
update(P1, P, Row, N) :-
    findall(path(C, [X|Is]), 
            ( between(0, N, X)
            , select(P1, X, N, path(C0, Is))
            , at(X, Row, C1)
            , C is C0 + C1),
        P).

% solve the puzzle by starting with a list of empty paths
% and updating it as long as there are still more rows in 
% the square.
solve(Rows, Score, Path) :-
    Rows = [R|_],
    length(R, N0),
    N is N0 - 1,
    initpaths(N, IP),
    solve(N, Rows, IP, Score, Path).
solve(_, [], P, Score, Path) :- 
    maxby(maxval, P, path(-1, []), path(Score, Is0)),
    reverse(Is0, Path).
solve(N, [R|Rows], P0, Score, Path) :-
    update(P0, P1, R, N),
    solve(N, Rows, P1, Score, Path).

試してみませんか？ここにあなたの例があります：

?- solve([[0,2,1,0], [0,1,1,0], [0,10,20,30]], Score, Path).
Score = 33,
Path = [1, 2, 3] ;
false.

?- solve([[0,1,1], [0,2,1], [10,0,0]], Score, Path).
Score = 13,
Path = [1, 1, 0] ;
false.

Answer 2

?- best_path_score([[0, 2, 1, 0],[0, 1, 1, 0],[0,10,20,30]], P, S).
P = [1, 2, 3],
S = 33.

この定義で

best_path_score(Rs, BestPath, BestScore) :-
    aggregate_all(max(Score, Path), a_path(Rs, Path, Score), max(BestScore, BestPath)).

a_path([R|Rs], [P|Ps], Score) :-
    nth0(P, R, S0),
    a_path(Rs, P, Ps, S),
    Score is S0 + S.

a_path([], _, [], 0).
a_path([R|Rs], P, [Q|Qs], T) :-
    ( Q is P - 1 ; Q is P ; Q is P + 1 ),
    nth0(Q, R, S0),
    a_path(Rs, Q, Qs, S),
    T is S0 + S.

Answer 3

私のプロローグは少し不安定です。実際、プロローグについて私が覚えているのは、それが宣言的だということだけです。

以下は、最大パスの値を見つけるための Haskell コードです。トレースを見つけるのは簡単な次のステップですが、コードを作成するのはもう少し複雑だと思います。トレースの非常に洗練された解決策は、モナドを使用することだと思います。

maxValue :: [ [ Int ] ] -> Int
maxValue p = maximum $ maxValueHelper p
maxValueHelper :: [ [ Int ] ] -> [ Int ]
maxValueHelper [ row ] = row
maxValueHelper ( row : restOfRows ) = combine row ( maxValueHelper restOfRows )
combine :: [ Int ] -> [ Int ]-> [ Int ]
combine [ x ] [ y ] = [ x + y ]
combine ( x1 : x2 : lx ) ( y1 : y2 : ly ) =
   let ( z2 : lz ) = combine ( x2 : lx ) ( y2 : ly )
   in
   ( max ( x1 + y1 ) ( x1 + y2 ) : max ( x2 + y1 ) z2 : lz )

main :: IO()
main = print $ maxValue [[0,2,1,0], [0,1,1,0], [0,10,20,30]]