Backtracking solution for http://blog.pizzahut.com/flavor-news/national-pi-day-math-contest-problems-are-here-2/

pizza.py

"""I'm thinking of a ten-digit integer whose digits are all distinct. It happens that the number formed by the first n of them is divisible by n for each n from 1 to 10. What is my number?
 http://blog.pizzahut.com/flavor-news/national-pi-day-math-contest-problems-are-here-2/ """

digits = [None] * 10

def pretty(A):
	return "".join(str(x) if x != None else "-" for x in A)

assert pretty([5, None, 3]) == "5-3"

def test(k):
	"""Test first k digits"""
	assert None not in digits[:k], digits[:k]

	if not len(set(digits[:k])) == k:
		return False

	for i in range(1, k+1):
		if int("".join(map(str, digits[:i]))) % i != 0:
			return False

	return True

def solve():
	pos = 0

	while True:
		# advance at pos
		assert digits[pos] != 9, digits

		if digits[pos] == None:
			digits[pos] = 0
		else:
			digits[pos] += 1

		if test(pos+1):
			print(pretty(digits))

			pos += 1
			if pos == 10:
				solution = int("".join(map(str,digits)))
				return solution

		else:
			print(pretty(digits) + " BUST")

			# rewind
			while digits[pos] == 9:
				digits[pos] = None
				pos -= 1
				if pos < 0:
					return "impossible"

print(solve())