#!/usr/bin/env python """ sq2.py An object oriented version of squares_crossword, with the constraints as lambda functions in a list. * This approach is a bit awkward, since those array functions can't easily be called as object methods. * And it's slower as well, even though I've avoided the if x==1: elif x==2 elif x==3 ... structure. thirty:Desktop$ time ./sq2.py Solving three digit crossword ... done. Looked at 27447 nodes in search tree. Found 14436 solution(s). Here's the first: 1 225 121 1 225 729 900 1 676 676 0 Found 1 solution(s) without repeated numbers. Here's the first: 8 169 225 1 484 625 729 1 441 676 6 real 0m10.826s user 0m10.440s sys 0m0.128s thirty:Desktop$ """ from sets import Set # Python 2.3 (or 2.4) : Set([1,1,2,3]) # after 'from sets import Set' # Python 2.4+ : set([1,1,2,3]) # built-in function class ThreeDigitNumber: """ A three digit number 100 < n < 999 >>> n = ThreeDigitNumber(567) >>> n[0] 5 >>> n[1] 6 >>> n[2] 7 >>> int(n) 567 >>> len(n) 3 >>> str(n) '567' """ def __init__(self, n): n = int(n) self.digits = ( n/100, (n % 100)/10, n % 10 ) def __int__(self): return 100*self.digits[0] + 10*self.digits[1] + self.digits[2] def __str__(self): return str(int(self)) def __len__(self): return 3 def __getitem__(self,i): return self.digits[i] class Iter: """ Loop over an indexed container. """ def __init__(self, container): self.index = -1 self.container = container def next(self): self.index += 1 if self.index < len(self.container): return self.container[self.index] else: raise StopIteration class ThreeDigitPerfectSquares: """ Three digit numbers that are squares, e.g. 100=10**2, 121=11**2, ..., 961=31**2 """ def __init__(self): self.numbers = [] for n in range(10,32): self.numbers.append(ThreeDigitNumber(n**2)) def __getitem__(self,i): return self.numbers[i] def __len__(self): return len(self.numbers) def __iter__(self): return Iter(self) class Crossword: """ 13 three digit positions """ # # Crossword pattern of perfect squares : # * * * * * * * * # * * * * * * * * * # * * * * * * * * # # which are stored in numbers[position][digit] this way, # where 0<=position<=12; 0<=digit<=2. # 0 2 3 3 3 5 7 8 8 8 10 12 # 0 1 1 1 2 5 6 6 6 7 10 11 11 11 12 # 0 2 4 4 4 5 7 9 9 9 10 12 # # The constraint functions constraints[position](crossword,number) # contain the details to implement the is_valid(position,number) method, # which returns true if number is consistent those to its left in the crossword. # # For example, if numbers=[121, None, None,...] # (e.g. the number 121=11**2 already been placed in position 0), # then the middle digit in position 1 must be a 2; # therefore, in this case is_valid(900,1) is False while is_valid(200, 1) is True. # constraints = [None]*13 constraints[0] = lambda c, x: True constraints[1] = lambda c, x: x[0]==c.numbers[0][1] constraints[2] = lambda c, x: x[1]==c.numbers[1][2] constraints[3] = lambda c, x: x[0]==c.numbers[2][0] constraints[4] = lambda c, x: x[0]==c.numbers[2][2] constraints[5] = lambda c, x: x[0]==c.numbers[3][2] and x[2]==c.numbers[4][2] constraints[6] = lambda c, x: x[0]==c.numbers[5][1] constraints[7] = lambda c, x: x[1]==c.numbers[6][2] constraints[8] = lambda c, x: x[0]==c.numbers[7][0] constraints[9] = lambda c, x: x[0]==c.numbers[7][2] constraints[10]= lambda c, x: x[0]==c.numbers[8][2] and x[2]==c.numbers[9][2] constraints[11]= lambda c, x: x[0]==c.numbers[10][1] constraints[12]= lambda c, x: x[1]==c.numbers[11][2] def __init__(self, numbers = [None]*13 ): self.numbers = numbers def is_valid(self, position, number): """ True if placing the number at the given position is consistent with numbers in lower positions.""" return self.constraints[position](self,number) def copy(self): return Crossword(self.numbers[:]) def all_numbers_different(self): """ True if no two of the numbers are the same. """ return len(Set(self.numbers)) == len(self.numbers) def __setitem__(self,i,number): self.numbers[i] = number def __str__(self): def c(position,digit): return str(self.numbers[position][digit]) def num(position): return str(self.numbers[position]) return " "*3+c(0,0)+" "+num(3)+" "+num(8)+" "+c(12,0)+"\n"+\ " "*3+num(1)+" "+num(6)+" "+num(11)+"\n"+\ " "*3+c(0,2)+" "+num(4)+" "+num(9)+" "+c(12,2) class Analysis: """ Solve crossword and display answers. """ def __init__(self): self.squares = ThreeDigitPerfectSquares() self.crossword = Crossword() self.solutions = [] self.no_repeats_solutions=[] self.node_count = 0 def solve(self, position=0): """ Recursivively solve from the given position, assuming the data for p= 13): self.solutions.append(self.crossword.copy()) else: self.node_count += 1 for number in self.squares: if self.crossword.is_valid(position, number): self.crossword[position] = number self.solve(position+1) def run(self): print "Solving three digit crossword ..." self.solve(position=0) print "done." print "Looked at", self.node_count, "nodes in search tree." print "Found", len(self.solutions), "solution(s)." print "Here's the first:" print self.solutions[0] for solution in self.solutions: if solution.all_numbers_different(): self.no_repeats_solutions.append(solution) print "Found", len(self.no_repeats_solutions), "solution(s) without repeated numbers." print "Here's the first:" print self.no_repeats_solutions[0] # Test Perfect Squares if False: print "three digit squares: ", for square in ThreeDigitPerfectSquares(): print square, print Analysis().run()