vendredi 24 septembre 2010

Dudeney number

I discovered yesterday Dudeney Numbers
A Dudeney Numbers is a positive integer that is a perfect cube such that the sum of its decimal digits is equal to the cube root of the number. There are only six Dudeney Numbers and those are very easy to find with CP.
I made my first experience with google cp solver so find these numbers (model below) and must say that I found it very convenient to build CP models in python!
When you take a close look at the line: solver.Add(sum([10**(n-i-1)*x[i] for i in range(n)]) == nb)
It is difficult to argue that it is very far from dedicated optimization languages!

from constraint_solver import pywrapcp



def dudeney(n):

solver = pywrapcp.Solver('Dudeney')

x = [solver.IntVar(range(10),'x'+str(i)) for i in range(n)]

nb = solver.IntVar(range(1,10**n),'nb')

s = solver.IntVar(range(1,9*n+1),'s')



solver.Add(nb == s*s*s)

solver.Add(sum([10**(n-i-1)*x[i] for i in range(n)]) == nb)

solver.Add(sum([x[i] for i in range(n)]) == s)



solution = solver.Assignment()

solution.Add(nb)

collector = solver.AllSolutionCollector(solution)



solver.Solve(solver.Phase(x, solver.INT_VAR_DEFAULT,

solver.INT_VALUE_DEFAULT),[collector])



for i in range(collector.solution_count()):

current = collector.solution(i)

nbsol = current.Value(nb)

print nbsol



print "#fails:",solver.failures()

print "time:",solver.wall_time()



if __name__ == '__main__':

dudeney(6)

4 commentaires:

  1. sorry, but I do not understand
    s = solver.IntVar(range(1,9*n+1),'s')

    RépondreSupprimer
  2. This creates a finite domain integer variable with domain [1..9*n]

    RépondreSupprimer
  3. yes, but (9*n+1)**3 is not equal or close to 10**n

    RépondreSupprimer
  4. Well the largest sum of the digits of an n digits number is 9*n (999 for n=3) that is why the domain for s is range(1,9*n+1).
    Now if n=3 the number we are looking for can be as large as 999 that is why 10**n-1 is the upper bound (domain = range(1,10**n)).
    In python ** is the exponent operator and range(5) generates numbers 0,1,2,3,4.

    RépondreSupprimer