mardi 22 mars 2016

Optimizing a Prolog algorithm

I'm trying to learn more advanced Prolog by doing problems I've already solved in Java, and translating parts of the code where possible. I'm currently working on a pebble solitaire problem (http://ift.tt/1XL3LoR), and my code does produce the right answer, for the most part at least... Some inputs take arduous amounts of time to solve, and in some cases, SWI-Prolog runs out of stack (for example start([111,111,111,111,111,45,45,111,45,111,111,111]).

I wonder how I can optimize my program so that it works for all inputs of length 12, and solves them reasonably fast at least.

I tried inserting some cuts where I thought they made sense in the minimizing algorithm, which seemed to have some positive effects. Perhaps there are other things I can do to speed things up that I'm not aware of? Any and all help is greatly appreciated.

``````% 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 pebbles on the board.

pebbles([], 0).

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

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

% Algorithm for minimizing the number of pebbles
% 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 pebble
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) :- pebbles(Y, F),
(nb_getval(min, M),
F < M,
nb_setval(min, F),
!;
true).

% Game predicate.

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

Optimizing a Prolog algorithm