CODEWITHSUNDEEP
prolog
Germán Faller
Germán Faller

Reputation: 566

Prolog Skip some backtracking branches

I'm trying to generate some Kakuros, generate not solve.

I have all rules to generate it, but the firsts results are senseless, those are like squares.

Now I want to skip some branches, 15000 for example, to see the kakuro generated at that point.

I have tried with an Auxiliary Variable, but when it fails, the Kakuro Generator start again.

Kakuro Example

Upvotes: 1

Views: 617

Answers (1)

Marijn
Marijn

Reputation: 1915

You can keep a dynamic counter-like predicate in the knowledge base that gets increased every time the main predicate is executed. The value of the counter is changed with assert and retract, i.e., it is not a variable within your main predicate but a globally stored value.

Within your main predicate, if you add the condition that the counter should be higher than some skip value, then you force backtracking over the actual rules for a specified number of iterations.

As an example, consider the built-in predicate permutation/2 which computes permutations of a list (note: tested using SWI-Prolog, other interpreters have different built-in predicates). Example output:

?- permutation([1,2,3,4,5],L).
L = [1, 2, 3, 4, 5] ;
L = [1, 2, 3, 5, 4] ;
L = [1, 2, 4, 3, 5] ;
L = [1, 2, 4, 5, 3] ;
L = [1, 2, 5, 3, 4] ;
L = [1, 2, 5, 4, 3] ;

If you want to skip the first 5 iterations in your query, you can use the following code:

:- dynamic iteration_nr/1.

iteration_nr(0).

get_permutations(L1,L2,Skip) :-
    permutation(L1,L2),
    iteration_nr(N),
    N2 is N+1,
    retract(iteration_nr(N)),
    asserta(iteration_nr(N2)),
    Skip < N2.     % force backtracking here if counter < Skip

Example output:

?- get_permutations([1,2,3,4,5],L2,5).
L2 = [1, 2, 5, 4, 3] ;
L2 = [1, 3, 2, 4, 5] ;
L2 = [1, 3, 2, 5, 4]

Note that asserta is used here (i.e., assert at the start) instead of plain assert, which is deprecated. Note also that the counter will keep the value, so when you run this a second time in the same session the results will be different. To reset the counter you can use a separate initialization predicate, for example:

init_and_get_permutations(L1,L2,Skip) :-
    retractall(iteration_nr(_)),
    asserta(iteration_nr(0)),
    get_permutations(L1,L2,Skip).

Further note: the use of assert and retract is not really considered 'clean' Prolog programming, because it is procedural and changes the knowledge base. However, for some applications it can be useful.

Upvotes: 1

Related Questions