Bir Prolog algoritması

Question

optimize Zaten Java çözdük sorunları yaparak daha gelişmiş mantıksal programlama öğrenmeye çalışıyorum. Şu anda sorunun Mancala tipi üzerinde çalışıyorum ve benim kod çoğunlukla en azından ... Bazı girişler çözmek için zamanın çetin miktarda almak, doğru cevabı üretmek etmez ve bazı durumlarda, bilgisayar biterse yığının (örneğin başlar ([111,111,111,111,111,45,45,111,45,111,111,111]).

Ben uzunluğu 12 tüm girişler için çalışır böylece benim programı optimize edebilirsiniz acaba, ve onları en azından makul hızlı çözer.

onların bazı olumlu etkileri var gibiydi minimum yapacak algoritması, içinde mantıklı düşünce nerede

bazı kesimler eklemeye çalıştık. Belki ben? Herhangi ve tüm farkında değilim şeyleri hızlandırmak için yapabileceğiniz başka şeyler yardım büyük takdir edilmektedir.

durumda size, taşların bakılmaksızın numaralarını çalışan farklı bir yaklaşım, daha mantıklı bir çözüm, ilgilendiğiniz içinde

% Facts. 

empty(45). % "-" 

occupied(111). % "o" 

% Executes a move and updates the board. 

executeMove([_, _, _ | R], 0, 1, 2, X, Y, Z, [X, Y, Z | R]). 

executeMove([A, B, C | R], I, J, K, X, Y, Z, [A | T]) :- K1 is K - 1, 
               J1 is J - 1, 
               I1 is I - 1, 
               executeMove([B, C | R], I1, J1, K1, X, Y, Z, T). 

% Tests if a move to the left can be made, 
% i.e. there exists a substring "-oo". 

tryLeft(L, I, J, K) :- I > 1,   
         nth0(I, L, X), 
         occupied(X), 
         nth0(J, L, Y), 
         occupied(Y),        
         nth0(K, L, Z), 
         empty(Z). 

% Tests if a move to the right can be made, 
% i.e. there exists a substring "oo-".      

tryRight(L, I, J, K) :- I < 10,   
         nth0(I, L, X), 
         occupied(X),  
         nth0(J, L, Y), 
         occupied(Y),        
         nth0(K, L, Z), 
         empty(Z). 

% Calculates the number of stones on the board. 

stones([], 0). 

stones([111|T], N) :- stones(T, N1), 
       N is N1 + 1, 
       !. 

stones([_|T], N) :- stones(T, N). 

% Algorithm for minimizing the number of stones 
% on a board. Currently too inefficient. 

tryMove(L, I) :- (
       I < 12,    % Iterate over the entire board 
       nth0(I, L, P),  % Get the Ith character 
       (     % If that character is a stone 
        occupied(P);  % then we might be able to move 
        I1 is I + 1,  % Otherwise, next iteration 
        tryMove(L, I1) 
       ), 
       (
        J is I + 1, 
        K is J + 1, 
        tryRight(L, I, J, K), % Test if a move can be made 
        executeMove(L, I, J, K, 45, 45, 111, Y), % Update the board 
        tryMove(Y, 0), % Test algorithm using the new board 
        calculate(Y); % Possibly update the minimum 
        true 
       ),    % Reset to the previous board 
       (
        J is I - 1, 
        K is J - 1, 
        tryLeft(L, I, J, K), % Test if a move can be made 
        executeMove(L, K, J, I, 111, 45, 45, Y), % Update the board 
        tryMove(Y, 0), % Test algorithm using the new board 
        calculate(Y); % Possibly update the minimum 
        true 
       ),    % Reset to the previous board 
       I2 is I + 1, 
       tryMove(L, I2); % Iterate 
       true    % Guarantees true output 
       ). 

% Reduces code duplication. 

calculate(Y) :- stones(Y, F), 
      (nb_getval(min, M), 
      F < M, 
      nb_setval(min, F), 
      ; 
      true). 

% Game predicate. 

start(L) :- stones(L, E), 
     nb_setval(min, E), 
     tryMove(L, 0), 
     nb_getval(min, M), 
     write(M), 
     nl. 

Answer 1

:

stones :- 
    member(Ps, [ 
     [o,o,o,o,o,-,-,o,-,o,o,o], 
     % from doc example 
     [-,-,-,o,o,-,-,-,-,-,-,-], 
     [-,o,-,-,o,-,o,o,-,-,-,-], 
     [-,o,-,-,-,-,o,o,o,-,-,-], 
     [o,o,o,o,o,o,o,o,o,o,o,o], 
     [o,o,o,o,o,o,o,o,o,o,-,o] 
    ]), 
    aggregate(min(N, [Last|Steps]), (
     stones([Ps], [Last|Steps]), 
     aggregate_all(count, member(o, Last), N) 
    ), min(Min, Sol)), 
    writeln(Min:Sol). 

stones([I|R], Steps) :- 
    move(I, T), 
    stones([T,I|R], Steps). 
stones(Solution, Solution). 

move(Ps, Moved) :- 
    append(L, [-,o,o|R], Ps), 
    append(L, [o,-,-|R], Moved). 
move(Ps, Moved) :- 
    append(L, [o,o,-|R], Ps), 
    append(L, [-,-,o|R], Moved). 

verimleri değiştirmek eğer

?- stones. 
3:[[o,-,o,-,-,-,-,-,-,-,-,o],[o,-,-,o,o,-,-,-,-,-,-,o],[o,o,o,-,o,-,-,-,-,-,-,o],[o,o,o,-,-,o,o,-,-,-,-,o],[o,o,o,o,o,-,o,-,-,-,-,o],[o,o,o,o,o,-,-,o,o,-,-,o],[o,o,o,o,o,-,-,o,-,o,o,o]] 
true ; 
1:[[-,-,o,-,-,-,-,-,-,-,-,-],[-,-,-,o,o,-,-,-,-,-,-,-]] 
true ; 
2:[[-,o,-,o,-,-,-,-,-,-,-,-],[-,o,-,-,o,o,-,-,-,-,-,-],[-,o,-,-,o,-,o,o,-,-,-,-]] 
true ; 
3:[[-,o,-,-,-,o,-,-,o,-,-,-],[-,o,-,-,-,-,o,o,o,-,-,-]] 
true ; 
12:[[o,o,o,o,o,o,o,o,o,o,o,o]] 
true ; 
1:[[-,o,-,-,-,-,-,-,-,-,-,-],[-,-,o,o,-,-,-,-,-,-,-,-],[o,o,-,o,-,-,-,-,-,-,-,-],[o,o,-,-,o,o,-,-,-,-,-,-],[o,o,o,o,-,o,-,-,-,-,-,-],[o,o,o,o,-,-,o,o,-,-,-,-],[o,o,o,o,o,o,-,o,-,-,-,-],[o,o,o,o,o,o,-,-,o,o,-,-],[o,o,o,o,o,o,o,o,-,o,-,-],[o,o,o,o,o,o,o,o,-,-,o,o],[o,o,o,o,o,o,o,o,o,o,-,o]] 
true.