Page 1 of 1

### Need Help - Kakuro

Posted: 6 Apr 2016 0:30
i am trying to use prolog to solve kakuro.
the question is to fill in the white squares with digits 1 through 9 so that they sum to the numbers shown in the dark squares. A dark square is shown with one or two sums, separated by a diagonal line. A sum above the diagonal denotes the total of the row of white squares to its right; A sum below the diagonal is the total of the column of white squares beneath it. Moreover, in any contiguous run of the whites squares all the digits must be different, that is, a digit can occur only once within a sum. Zero is also precluded from the sum. The challenge is to use finite domain constraint logic programming to solve the Kakuro puzzle given in Attachment (diagram1), The solution should print its solution in the format given below,Note that the example just illustrates layout; it cannot be a solution since the third column contains a line that contains three ones.
<pre>************
***35****35*
***2938**28*
**28*2358*32
*3512**23*93
*28*3258*328
**92*329*21*
*318*5913*13
*53*28**2345
*84*8125*21*
**13**5329**
**12****58**</pre>
and i have been given the predicates file spec.pl-

Code: Select all

``````% black(R, C).
black(1, 1).
black(1, 2).
black(1, 3).
black(1, 4).
black(1, 5).
black(1, 6).
black(1, 7).
black(1, 8).
black(1, 9).
black(1, 10).
black(1, 11).
black(1, 12).

black(2, 1).
black(2, 2).
black(2, 3).
black(2, 6).
black(2, 7).
black(2, 8).
black(2, 9).
black(2, 12).

black(3, 1).
black(3, 2).
black(3, 3).
black(3, 8).
black(3, 9).
black(3, 12).

black(4, 1).
black(4, 2).
black(4, 5).
black(4, 10).

black(5, 1).
black(5, 6).
black(5, 7).
black(5, 10).

black(6, 1).
black(6, 4).
black(6, 9).

black(7, 1).
black(7, 2).
black(7, 5).
black(7, 9).
black(7, 12).

black(8, 1).
black(8, 5).
black(8, 10).

black(9, 1).
black(9, 4).
black(9, 7).
black(9, 8).

black(10, 1).
black(10, 4).
black(10, 9).
black(10, 12).

black(11, 1).
black(11, 2).
black(11, 5).
black(11, 6).
black(11, 11).
black(11, 12).

black(12, 1).
black(12, 2).
black(12, 5).
black(12, 6).
black(12, 7).
black(12, 8).
black(12, 11).
black(12, 12).

% across(R, C, L, S)
across(2,4,2,4).
across(2,10,2,4).
across(3,4,4,12).
across(3,10,2,6).
across(4,3,2,6).
across(4,6,4,10).
across(4,11,2,3).
across(5,2,4,12).
across(5,8,2,3).
across(5,11,2,6).
across(6,2,2,6).
across(6,5,4,10).
across(6,10,3,7).
across(7,3,2,7).
across(7,6,3,8).
across(7,10,2,8).
across(8,2,3,11).
across(8,6,4,15).
across(8,11,2,8).
across(9,2,2,4).
across(9,5,2,6).
across(9,9,4,14).
across(10,2,2,12).
across(10,5,4,15).
across(10,10,2,11).
across(11,3,2,8).
across(11,7,4,11).
across(12,3,2,11).
across(12,9,2,7).

% down(R, C, L, S)
down(5,2,2,3).
down(8,2,3,8).
down(4,3,9,45).
down(2,4,4,13).
down(7,4,2,6).
down(11,4,2,3).
down(2,5,2,8).
down(5,5,2,3).
down(9,5,2,6).
down(3,6,2,3).
down(6,6,5,16).
down(3,7,2,5).
down(6,7,3,10).
down(10,7,2,5).
down(4,8,5,20).
down(10,8,2,4).
down(4,9,2,5).
down(8,9,2,3).
down(11,9,2,5).
down(2,10,2,3).
down(6,10,2,3).
down(9,10,4,12).
down(2,11,9,45).
down(4,12,3,7).
down(8,12,2,4).``````
i just wrote my code but it doesn't work. could any one help me please? thank you
here is my code

Code: Select all

``````:- use_module(library(clpfd)).
:- [spec].

kakuro(M):-
%matrix(12, M),
checkRow(M, 1, 1),
transpose(M, MT),
checkColumn(MT),
labeling([], M).

checkRow([], _, _).
checkRow(M, 1, 1):-
((across(C, R, L, S), generate(S, L, Mg), match([M|Ms], Mg));
(black(R, C),M = *)),
checkRow(Ms, C, R + 1).

checkColumn([], _, _).
checkColumn(M, 1, 1):-
(down(R, C, L, _), length(Mg, L), Mg ins 1..9, all_different(Mg), match([M|Ms], Mg)),
checkColumn(Ms, R, C + 1).

generate(_, N, Sum):-
length(M, N),M ins 1..9,
all_different(M),
plus(M, Sum).

gt(M, N):-
length(M, N),
M ins 1..9.

return(M, N):-N is M.

plus([],0).
plus([H|T], S):-
plus(T, R),
S is H+R.

length_list(N, List) :-
length(List, N).

generate_matrix(Matrix) :-
Rows=12,Columns=12,
length_list(Rows, Matrix),
maplist(length_list(Columns), Matrix).

test(M):-
generate_matrix(M),
labeling([_,_,_,_,_,_,_,_,_,_,_,_], M). ``````

Posted: 6 Apr 2016 0:49
While I don't have a solution I can offer a suggestion that might help some.

I've played this 'game' before and I find it challenging (but fun!).

It is similar to Sudoku (each number can only be used once in a column or row) but with the added twist of summing the numbers.

I suggest looking at the Sudoku example VIP did a few years ago and adapt that by adding the extra rules needed for the summing and comparison to the target values.

It will serve two purposes: 1. give you a clearer understanding of VIP and 2. give you a different perspective on how to solve the problem.

Good luck.

P.

Posted: 6 Apr 2016 10:36
Your algorithm is a generate and test algorithm. Your algorithm doesn't work, but I understand what you attempt to do, so I will describe your algorithm as (I believe) you intended it.

M is the result and it is supposed to be a list of rows where each row is a list of the column values of that row. You intend to insert * where the matrix is black.

You will generate M row by row (with backtracking possibilities where things could have been differently chosen), and then test the columns afterwards, backtracking if the test fails.

The first mistake you have made (given the description above) is that you actually don't go through the matrix row by row.

Code: Select all

``````kakuro(M) :-
generateRows(1, M),
transpose(M, MT),
checkColumns(MT).

generateRows(13, []) :-
!.

generateRows(R, [Row|Rest]) :-
generateRow(R, 1, Row),
generateRows(R+1, Rest).``````
To generate a row you will insert * if the field is black and generate otherwise generate a sum for the following fields.

Code: Select all

``````generateRow(R, 13, []) :-
!.

generateRow(R, C, Row) :-
across(C, R, L, S),
!,
generateSum(L, S, Sum),
generateRow(R, C+L, Rest),
Row = append(Sum, Rest).

generateRow(R, C, [*|Rest]) :-
generateRow(R, C+1, Rest).``````
I don't need to check for black, because either a field is part of a sum, or it is black. Second clause deals with all fields that are part of a sum, so the remaining fields must be black.

I will not continue with the rest of the algorithm you also have to do a little homework yourself .

But I cannot help moralizing : If you had used Visual Prolog instead of whatever-untyped-Prolog then you would have known that you do not handle your matrix as a list of rows (you would get type errors).

Posted: 6 Apr 2016 21:04
Thank you for help.
i everything i can but still doesnt work
i think i should use findall as well?

Posted: 7 Apr 2016 8:35
I think you should test you sub predicates first, for example the one that creates numbers with a given sum.

Code: Select all

``````test_sum() :-
Length = 4,
Sum = 22,
generateSum(Length, Sum, Seq),
write(Seq, "\n"),
fail.
test_sum().``````
Which should write something like:

<pre>[1, 4, 8, 9]
[1, 4, 9, 8]
[1, 5, 7, 9]
[1, 5, 9, 7]
...</pre>