Kakuro Puzzle CSP Prolog

Question

Have an exam coming up and answering past paper questions to aid my revision. The question I am trying to answer is: (d) Translate the CSP into a Prolog program that computes just one way of solving this problem using finite domain constraints. [7 marks]

I have written the following code:

  kakuro(L):-
      L = [X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16],
      L ins 1..9,       
      Z1 = [X1, X2],
      all_different(Z1),
      X1 #= 5 - X2,     
      Z2 = [X3, X4, X5, X6],
      all_different(Z2),
      X3 #= 29 - (X4+X5+X6),
      Z3 = [X7, X8],
      all_different(Z3),
      X7 #= 14 - X8,
      Z4 = [X9, X10],
      all_different(Z4),
      X9 #= 4 - X10,
      Z5 = [X11, X12, X13, X14],
      all_different(Z5),
      X11 #= 16 - (X12+X13+X14),
      Z6 = [X15, X16],
      all_different(Z6),
      X15 #= 7 - X16,

      A1 = [X3, X7],
      all_different(A1),
      X3 #= 16 - X7,
      A2 = [X1, X4, X8, X11],
      all_different(A2),
      X1 #= 18 - (X4+X8+X11),
      A3 = [X2, X5],
      all_different(A3),
      X2 #= 13 - X5,
      A4 = [X12, X15],
      all_different(A4),
      X12 #= 14 - X15,
      A5 = [X6, X9, X13, X16],
      all_different(A5),
      X6 #= 11 - (X9+X13+X16),
      A6 = [X10, X14],
      all_different(A6),
      X10 #= 3 - X14,

      labeling([], L).

I think my answer is a bit too long. Is there any way I could shorten it?

Really appreciate any help!

mat mat · Accepted Answer · 2016-05-10T14:29:53

I show you a simplification up to the first empty line:

kakuro(Ls):-
      Lss = [[X1,X2],
             [X3,X4,X5,X6],
             [X7,X8],
             [X9,X10],
             [X11,X12,X13,X14],
             [X15, X16]],
      maplist(all_different, Lss),
      append(Lss, Ls),
      Ls ins 1..9,
      X1 #= 5 - X2,
      X3 #= 29 - (X4+X5+X6),
      X7 #= 14 - X8,
      X9 #= 4 - X10,
      X11 #= 16 - (X12+X13+X14),
      X15 #= 7 - X16,

Notice in particular:

I chose a representation of the puzzle that retains more information about its structure.
The meta-predicate maplist/2 is used to replace many individual calls of all_different/1.
A systematic naming convention: lists end with an "-s", lists of lists end with an "s" appended to that.
append/2 is used to remove one level of nesting.

Another change I strongly recommend: Separate the core relation from labeling/2! This simplifies testing and has many other advantages. The eventual query should look similar to:

?- kakuro(Vs), label(Vs).

or like:

?- kakuro_(Instance, Vs), label(Vs).

I leave further simplifying this, and the remainder of the program, as an exercise for you. Note that the choice of instance representation can help signficantly to shorten the code!

Kakuro Puzzle CSP Prolog

1 Answers