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
