Saturday, September 4, 2010

One to nine puzzle

The problem

Find a number using the digits 1 through 9 once each, such that

  • the number is divisible by 9
  • if the right most digit is removed, the number is divisible by 8
  • if the next right most digit is removed, the number is divisible by 7
  • ... until there is only one digit left, which is divisible by 1

Brute force

The first thing to do, is see if brute force will work. Often it will, and even if it doesn't solve the problem, thinking this approach through can help find a better solution.

We could loop throuch each possible nine digit number, and see if it meets all the rules. We might do it like this:

for i in 123456789 to 987654321 do
    # check if i contains each digit once
    # check if i is divisible by 9
    # check if floor (i/10) is divisible by 8
    # ...

That might not be too bad, but it will check 864,197,532 numbers, and the logic in the loop isn't that clean. Instead of checking if each digit is used once, we could generate all permutations of 123456789 instead. That way, every number meets the criteria of using each digit once. Also, we would only check 9!, or 362,880 values, checking far fewer numbers than the first idea.

Not so brute force

If we look closer at the problem we can see that we have a number of the form abcdefghi. "a" must be divisible by 1. "ab" must be divisible by 2. "abc" must be divisible by 3, and so on. Using that information, we could first check "ab", before appending any more digits to it, and wipe out a lot of possible numbers. For example, we know that "21" can never be the start of our answer, since 21 is not divisible by 2. Of the 72 possible two digit starting values, about half will fail this test. That will take us down to 180,000 values or so! Then, we can eliminate about 2/3's of the rest by checking all of the first three digits, and go down again to about 60,000 possible values.

We can get this solution to work with a recursive function. The inputs will be a list of digits left to use, and the current number we are considering (the first n digits). We will write the function so that the current number is always valid, so it contains no duplicate digits, and it follows the divisibility rules. Also, the digits to use list contains exactly the digits we need to make a valid solution, and no more.

def fast(nums=range(1,10),acc=0,d=1):

    if not nums:
        # we have reached the end... print the answer!
        print "result: ", acc
    else:
        for n in nums:
            # update the number with a new digit at the end.
            newnum = n + 10*acc
            if newnum % d == 0:
                # this is a valid partial solution.
                # Call recusively with a new list of nums.
                tmp = [x for x in nums if x is not n]
                fast(tmp,n+10*acc,d+1)

I abused the default arguments of the function so it can be called without any arguments. The new function runs in less than two milliseconds, which is about 1/300,000th of the brute force timing.

If you only want the answer, the brute force solution is good enough. But, you can work at it to find a cleaner answer, and then learn a technique that can help in other problems.

No comments: