The 7-Digits Puzzle (Puzzle7)

Run LPL Code  ,  PDF Document

Problem

Use each digit from 1 to 7 exactly once, and place them into the circles of Figure 1 in such a way that the sum along each of the five lines is the same.

Modeling Steps

The key observations are: There are 7 circles and 7 digits. On each line we have 3 circles, hence 3 digits to place. Which digit should be at the center? Or: what numbers should be at the two ends of a line? Once answered these questions, it is easy to see the solution. Two observations lead to the number in the center: (1) The sum must be even, since otherwise at least four lines must have two even and one odd numbers, but there are only three numbers in {1,…, 7} that are even. (2) the sum of all numbers is 28. The sum on the three lines through the center is 28 + 2D and it must be divisible by 3. Since the sum is even, 28 + 2D can only be 36. Hence the sum is 12 and D = 4.

Let’s now formulate this problem as a mathematical model: Seven integer variables x_i ∈{1,…, 7} with i,j ∈ I = {A,…, G} are to be determined and all must be different from each other. Furthermore, an additional variable z is introduced for the sum on each line.

Note that: Depending on the notation of the formulation, the sentence “all must be different from each other” could directly be interpreted as a predicate in the modeling formulation (as done here) or be translated as a set of inequalities as follows:

In the LPL language the predicate is directly integrated as a “global constraint” with the keyword alldiff (another way in LPL is to use the function Alldiff()).

For each of the five straight lines a constraint is specified and the whole model can be formulated as follows :

model Puzzle7 "The 7-Digits Puzzle"; 
 
  set i,j := ['A','B','C','D','E','F','G']; 
 
  alldiff variable x{i} [1..7]; 
 
  variable z; 
 
  constraint 
 
    L1: x['A'] + x['D'] + x['G'] = z; 
 
    L2: x['A'] + x['C'] + x['F'] = z; 
 
    L3: x['B'] + x['E'] + x['G'] = z; 
 
    L4: x['B'] + x['D'] + x['F'] = z; 
 
    L5: x['C'] + x['D'] + x['E'] = z; 
 
  solve; 
 
  Write('%s , z=%d' n',{i} Format('%s=%d ', i, x), z)); 
 
  --draw the solution 
 
  parameter X{i}:=[10 50 10 30 50 10 50]; 
 
            Y{i}:=[10 10 50 50 50 90 90]; 
 
  set li{i,j}:=[('A','F') ('A','G') ('B','F') ('B','G') ('C','E')]; 
 
  Draw.Scale(10,5); 
 
  Draw.DefFont('Verdana',20,0,2); 
 
  {li[i,j]} Draw.Line(X[i],Y[i],X[j],Y[j]); 
 
  {i} Draw.Circle(i&'='&x,X,Y,3,1,0); 
 
  --{i} Draw.Circle(i&'',X,Y,3,1,0); 
 
end

Solution

The solution is given in Figure 2. The sum on each line is z = 12.

References