Wie löst man dieses Puzzle in Prolog?

Question

Ich versuche, ein Puzzle in Prolog zu lösen, das beinhaltet, ein Quadrat von Zahlen (eine Liste einer Liste von Zahlen) zu nehmen und die Liste der größten Kombination von Zahlen beginnend an der Spitze und Zeile für Zeile hinunterzugehen. Jede Bewegung muss entweder unten, rechts oder links sein.

Ich habe das schon seit einer Weile versucht, hat jemand einen Platz, den ich anfangen könnte?

Zum Beispiel auf dem Brett

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

der beste Zug [1, 2, 3] für 33 Punkte sein würde.

Answer 1

Also hier ist, wie Sie könnte es tun. Ich weiß, es ist irgendwie wortreich, das wahrscheinlich ist, weil ich entweder in Prolog nicht wirklich fließend bin ...

% 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). 

Sollen wir es ausprobieren? Hier sind Ihre Beispiele:

?- 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

Mein Prolog ist ein bisschen wackelig. Eigentlich erinnere ich mich nur an Prolog, dass es deklarativ ist.

Hier ist ein Haskell-Code, um den Wert des maximalen Pfades zu finden. Die Suche nach der Spur sollte ein einfacher nächster Schritt sein, aber ein bisschen komplizierter, um es zu kodieren, stelle ich mir vor. Ich nehme an, eine sehr elegante Lösung für die Spur wäre die Verwendung von Monaden.

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]] 

Answer 3

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

mit dieser Definition

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.