Home

More Samples

///////////////////////////////////////////////////////////////////////////////
// Eighteen
///////////////////////////////////////////////////////////////////////////////
// Enigma 1496 Albert Haddad, New Scientist magazine, May 31, 2008
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
// An eight digit "multiplicand" comprising of dots and letters is multiplied
// by 2 resulting in the product EIGHTEEN. Different letters stand for 
// different digits, the same letter stands for the same digit, and a dot can 
// be any digit. 
//
//     . . N I N E . .
//                 * 2
//    ----------------
//  =  E I G H T E E N
//    ----------------
//
// What is the eight-digit product EIGHTEEN?
//
///////////////////////////////////////////////////////////////////////////////
//
// Solve the problem by running the query:
//
//      all Eighteen_Lazy(xlazy)
//
// or 
//      all Eighteen_Fast(xfast)
//
///////////////////////////////////////////////////////////////////////////////
//
// Results:
//
// xlazy = 91637998
// ___ Solution: 1 __________________________________
// 
// Number of solutions: 1   Number of backtracks: 24328306
// Elapsed time: 00:04:14  
//
//
// xfast = 91637998
// ___ Solution: 1 __________________________________
//
// Number of solutions: 1   Number of backtracks: 190
// Elapsed time: 00:00:00
//                             
///////////////////////////////////////////////////////////////////////////////
//
// Notes: Two ways of solving the problem are presented. 
//        One simple but slow, the other a bit more complex but a lot faster. 
//
///////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////
// Just constrain the variables exactly the way the problem specifies.
// No thinking involved. Let the computer do the work. 
local Digit = L[0..9]

pred Eighteen_Lazy(x::L[1..]) iff
    digits ::[0..]->>Digit & digits = [e,i,g,h,t,n] & e <> 0 &
    d1::Digit & d2::Digit & d3::Digit & d4::Digit & d1 <> 0 &
    x = e*10000000 + i*1000000 + g*100000 + h*10000 + t*1000 + e*100 + e*10 + n &   
    (d1*10000000 + d2*1000000 + n*100000 + i*10000 + n*1000 + e*100 + d3*10 + d4)*2 = x 


///////////////////////////////////////////////////////////////////////////////
// Tell the computer how to multiple digit by digit, from the least significant
// digit to the most significant digit, adding carry. 
// (Just like they taught us in elementary school)

local DigitI = I[0..9] 

pred Eighteen_Fast(x::[1..]) iff
    digits ::[0..]->>DigitI & digits = [e,i,g,h,t,n] & e <> 0 &
    d1::DigitI & d2::DigitI & d3::DigitI & d4::DigitI & 
 
    x0 =(d4*2     ) & n = x0 mod 10 & c1 = x0/10 &
    x1 =(d3*2 + c1) & e = x1 mod 10 & c2 = x1/10 &
    x2 =( e*2 + c2) & e = x2 mod 10 & c3 = x2/10 &
    x3 =( n*2 + c3) & t = x3 mod 10 & c4 = x3/10 & 
    x4 =( i*2 + c4) & h = x4 mod 10 & c5 = x4/10 &
    x5 =( n*2 + c5) & g = x5 mod 10 & c6 = x5/10 &
    x6 =(d2*2 + c6) & i = x6 mod 10 & c7 = x6/10 &
    x7 =(d1*2 + c7) & e = x7 mod 10 &  0 = x7/10 &

    x = e*10000000 + i*1000000 + g*100000 + h*10000 + t*1000 + e*100 + e*10 + n    

This page was created by F1toHTML