Solving Kakuro puzzle (5x5) in Prolog

Question

Assuming that:

A+B+C=24
E+F+G=11
J+K+L=22
N+O+P=14
A+E=17
B+F+J+N=26
C+G+K+O=15
L+P=13

How could i find a possible solution to the problem, given the constraints above, using the predicate solve/1? My first attempt was below, with no result. Thanks in advance!

solve(L1) :-
    L1 = [A,B,C,E,F,G,J,K,L,N,O,P],
    A is 24-B-C,
    B is 26-F-J-N,
    C is 15-G-K-O,
    E is 11-F-G,
    E is 17-A,
    J is 22-K-L,
    N is 14-O-P,
    L is 13-P,
    write(L1).

Option

Okay, is it better now? – Option

I don't see how you would have gotten "no result" from that code. I would have expected an instantiation error. Please describe your results accurately. Try using CLPFD. For example, A + B + C #= 24 instead of A is 24-B-C. The is/2 requires that variables in the second expression all be instantiated. – Hillell

Answer 1

As @lurker already said in his comment, use CLP(FD) constraints.

In addition, I recommend:

1. instead of solve/1, use a declarative name like solution/1. You should describe what holds for a solution, so that the relation makes sense in all directions, also for example if the solution is already given and you want to validate it.
2. By convention, it makes sense to let variables that stand for lists end with an s.
3. Separate side-effects from pure code. In fact, remove side-effects altogether. Let the prolog-toplevel do the printing for you!

For example:

:- use_module(library(clpfd)).

solution(Ls) :-
    Ls = [A,B,C,E,F,G,J,K,L,N,O,P],
    A #= 24-B-C,
    B #= 26-F-J-N,
    C #= 15-G-K-O,
    E #= 11-F-G,
    E #= 17-A,
    J #= 22-K-L,
    N #= 14-O-P,
    L #= 13-P.

This already works for queries like:

?- solution(Ls), Ls ins 0..sup, label(Ls).
Ls = [6, 3, 15, 11, 0, 0, 9, 0, 13, 14, 0, 0] ;
Ls = [6, 3, 15, 11, 0, 0, 10, 0, 12, 13, 0, 1] ;
Ls = [6, 3, 15, 11, 0, 0, 11, 0, 11, 12, 0, 2] ;
etc.

I leave completing this as an easy exercise.

Oatmeal

Thanks for the help, I also forgot to specify that the solutions have to be between [0-9] which means the query is modified to: solution(Ls), Ls ins 0..9, label(Ls). The problem is that there can't be the same numbers in one line or column. Explain: The lists below shouldn't contain duplicates. L1 = [A,B,C] L2 = [E,F,G] L3 = [J,K,L,N] L4 = [N,O,P] L5 = [A,E] L6 = [B,F,J,N] L7 = [C,G,K,O] L8 = [L,P] How could i express these restrictions? – Option

Try the CLP(FD) constraint all_distinct/1. – Oatmeal

Thanks for your answer, please be aware of a possible mistake. The all_distinct predicate should guarantee the uniqueness of all rows and columns. – Awed