title: Python: Code to find a number where first N digits are divisible by N (from 0-9)
body: <p>I've been trying to write a recursive solution to a program to find a number where first N digits are divisible by N.</p>
  
  <p>As an example: 3816547290, 3 is divisible by 1, 38 is divisible by 2, 381 is divisible by 3 and so on...</p>
  
  <p>My recursive solution works fine while going "into" the recursion, but has issues when the stack unwinds (i.e. I don't specifically know how to backtrack or take steps on the way out</p>
  
  <pre><code>ARR = [0]*10
  ARR[0] = 1 #dummy entry
  def numSeq(pos, num):
  
      if all(ARR):
          print num
          return True
  
      if (pos&gt;0) and (num%pos) != 0:
          return False
  
      for i in xrange(1,10):
          if ARR[i] == 1:
              continue
          new_num = num*10 + i
          if new_num%(pos+1) == 0:
              ARR[i] = 1
          numSeq(pos+1,new_num)
  </code></pre>
  
  <p>The problem with this code seems to be that it follows the number generation correctly while going into the recursion...so it correctly generates the number 123654 which is divisible by 6 and follows first N digits being divisible by N, but after it fails to find any further digits from 7-8 or 9 that divide 7, i don't get the next set of steps to "reset" the global ARR and begin from index 2, i.e. try 24xxxx,and eventually get to 3816547290</p>
  
  <p>Thanks in Advance for your help!</p>
  
  <p><strong>EDIT</strong>: One condition I'd forgotten to mention is that each digit must be used exactly once (i.e. repetition of digits is disallowed)</p>
  
  <p><strong>2nd EDIT</strong>:</p>
  
  <p>I was able to <strong>finally</strong> apply proper backtracking to solve the problem...this code works as is.</p>
  
  <pre><code>ARR = [0]*10
  def numDivisibile(num,pos):
  
      if all(ARR):
          print num
          return True
  
      for i in xrange(0,10):
          if ARR[i] == 1:
              continue
          new_num = num*10+i
          #check for valid case
          if new_num%(pos+1) == 0:
              ARR[i] = 1
              if numDivisibile(new_num, pos+1):
                  return True
              #backtrack
              ARR[i] = 0
  
      return False
  
  print numDivisibile(0, 0)
  </code></pre>