Archive

Archive for November, 2013

Solving a summarum puzzle in prolog

November 24, 2013 Leave a comment

At breakfast today I spotted a puzzle called summarum in the newspaper. It looked like this (please excuse the poor art… Smile)

summarum2

Each row, column and block should sum up to the number associated. Number 5 in the middle is given. It seemed like a pure constraint problem that would be very simple to solve in prolog. I gave it a try.

:- use_module(library(clpfd)).

solution(X, R1, R2, R3, C1, C2, C3, B1, B2, B3, B4) :-
    length(X, Size),
    X ins 1..Size,
    all_distinct(X),
    X = [X1, X2, X3, X4, X5, X6, X7, X8, X9],
    X1 + X2 + X3 #= R1,
    X4 + X5 + X6 #= R2,
    X7 + X8 + X9 #= R3,
    X1 + X4 + X7 #= C1,
    X2 + X5 + X8 #= C2,
    X3 + X6 + X9 #= C3,
    X1 + X2 + X4 + X5 #= B1,
    X2 + X3 + X5 + X6 #= B2,
    X4 + X5 + X7 + X8 #= B3,
    X5 + X6 + X8 + X9 #= B4,
    label(X).

The variables are labeled according to the picture below:

summarum3

Execute to following line for the specific instance:

solution([X1,X2,X3,X4,X5,X6,X7,X8,X9], 13, 18, 14, 14, 14, 17, 20, 24, 17, 21), X5=5.

Which (spoiler alert!) gives:

X1 = 3,
X2 = 8,
X3 = 2,
X4 = 4,
X5 = 5,
X6 = 9,
X7 = 7,
X8 = 1,
X9 = 6 .

A good start this sunday morning… Smile

Categories: Uncategorized