////////////////////////////////////////////////////////////////////////////////////////
//
// Dean Clark's Problem (Clock Triplets Problem)
//
// The problem was originally posed by Dean Clark and then presented
// to a larger audience by Martin Gardner. 
//
// The problem was discussed in Dr. Dobbs's Journal, May 2004 in an article 
// by Timothy Rolfe. According to the article, in his August 1986 column for 
// Isaac Asimov's Science Fiction Magazine, Martin Gardner presented this problem:
// 
//     Now for a curious little combinatorial puzzle involving the twelve
//     numbers on the face of a clock. Can you rearrange the numbers (keeping
//     them in a circle) so no triplet of adjacent numbers has a sum higher 
//     than 21? This is the smallest value that the highest sum of a triplet
//     can have.
// 
// Timothy Rolfe solves the problem using a rather complex algorithm and also 
// presents a generic algorithm for numbers other than 12 (clock numbers) and 
// 21 (highest sums of triplets). The main emphasis of the algorithm was put
// on the computational speed. The article stressed the fact that a simple 
// backtracking algorithm would be simply too slow due to the number of permutations.
// 
// In this F1 sample, we achieve reasonable computational speeds while the code
// is quite simple. The code, in the spirit of logical programming, does not require
// us to specify any particular algorithm. 
// 
// Similar to Timothy Rolfe, we also use two optimizations to cut down on identical
// solutions: 
// 
// 1.  We nail down one number (number 12 to position 0). This reduces the
//     number of solutions by 12.
// 2.  We remove "mirror" solutions by postulating that the number right of 12 is
//     greater then the number left of 12. This reduces the number of solutions 
//     by one half.
// 
// These optimizations can be removed by simply commenting out the corresponding line.
// 
// To solve the original problem, run the query
// 
//         all Cloque(x) 
// 
// The above query will generate all 261 solutions in about 12 seconds using a modest
// AMD Athlon 1600+.
// 
// The code for a general solution of the problem is in the predicate CloqueMN.
// 
// For example, using the query:
// 
//        all CloqueMN(x,12,21)
// 
// solves the original problem,
//
//        all CloqueMN(x,13,23)
//
// will generate all solutions for a clock with 13 numbers with the highest sum of any
// triplet being 23.
//
////////////////////////////////////////////////////////////////////////////////////////

pred Cloque(x::[0..11]->>L[1..12]) iff   // 6264 solutions with no optimizations
    x(0) = 12 &     // Optimization 1: nail down number 12 (522 solutions)
    x(1) > x(11) &  // Optimization 2: remove mirror solutions (261 solutions)
    x(0)  + x(1)  + x(2)  <= 21 &
    x(1)  + x(2)  + x(3)  <= 21 &
    x(2)  + x(3)  + x(4)  <= 21 &
    x(3)  + x(4)  + x(5)  <= 21 &
    x(4)  + x(5)  + x(6)  <= 21 &
    x(5)  + x(6)  + x(7)  <= 21 &
    x(6)  + x(7)  + x(8)  <= 21 &
    x(7)  + x(8)  + x(9)  <= 21 &
    x(8)  + x(9)  + x(10) <= 21 &
    x(9)  + x(10) + x(11) <= 21 &
    x(10) + x(11) + x(0)  <= 21 &
    x(11) + x(0)  + x(1)  <= 21 

// This is the code for the general case of an array of "m" elements
// with the maximum value of the sum of any three consequitive elements being "n"

pred CloqueMN(x::[0..]->>L[1..], m:<I,n:<I) iff
    Len(x,m) &          // Set the length of the array to be "m"
    x(0) = m &          // Optimization 1: nail down number "m" (reduce solutions to solutions/m)
    x(1) > x(m-1) &     // Optimization 2: remove mirror solutions (reduce solutions by one half)
    CloqueMNEx(x,m,n,0) // Set the constraints for "m" and "n"

local pred CloqueMNEx(x::[0..]->>L[1..], m:<I,n:<I,i:<I) iff
    if i < m then 
        j = (i+1) mod m & k = (i+2) mod m &
        x(i) <= m & x(j) <= m & x(k) <= m &
        x(i) + x(j) + x(k) <= n &
        CloqueMNEx(x,m,n,i+1)
    end
  

This page was created by F1toHTML