#!/usr/bin/env python """ sq3.py Solve three digit squares crossword. Another object oriented version of squares_crossword.py, with a more general constraint representation. This one would extend easily to longer crosswords layouts, and aesthetically seems like the coolest. It runs just a bit slower that sq2.py. I tried to speed it up by avoiding making new Crossword objects for each solution, but that didn't make any difference. Something about the more general constraint checks are probably the culprit; I'm not sure. thirty:Desktop$ time ./sq3.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 repeats. Here's the first: 8 169 225 1 484 625 729 1 441 676 6 real 0m11.153s user 0m10.773s sys 0m0.117s """ 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. Used here for iteration over a ThreePerfectSquares, below. """ 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: """ All three digit numbers that are squares, e.g. [100, 121, ..., 961]. """ def __init__(self): self.numbers = [] # 10*2 = 100 is the first one; 31**2 = 961 is the last. 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: """ A penciled in three-digit squares crossword. Up to 13 three digit numbers in this pattern : * * * * * * * * * * * * * * * * * * * * * * * * * """ # The data is stored in numbers[position][digit] in the following 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 # This tuple describes how each number relates to those to its left. layout = ( 'leftmost', 'bar', 'box_left', 'box_top', 'box_bottom', 'box_right', 'bar', 'box_left', 'box_top', 'box_bottom', 'box_right', 'bar', 'box_left', ) # For each layout, the digits (n,m,offset) in below in connectivity # describes a constraint, namely that the n'th digit must match # the m'th of the previous offset'th number. # For example # the number in position=2 is a 'box_left' because # its a vertical column of numbers at the left of a box # with (left,top,bottom,right) at positions (2,3,4,5). # If the numbers in positions 0 to 6 have already been placed, # then the number in position 7 will be consistent if it's middle digit # (n=1) matches the last digit (m=2) of the one in postion 6, # which is 1 back (offset=1) from position set. # As a triple of numbers that constraint (n,m,offset) is (1,2,1). # The box_right layout has two constraints, since it has two numbers # to the left that intersect it. connectivity = { 'leftmost' : ( ), 'bar' : ( (0, 1, 1), ), 'box_left' : ( (1, 2, 1), ), 'box_top' : ( (0, 0, 1), ), 'box_bottom' : ( (0, 2, 2), ), 'box_right' : ( (0, 2, 2), (2, 2, 1), ), } def is_valid(self, position, number): """ Return True if putting number at position is consistent with the numbers at lower positions in the crossword pattern. """ for (n, m, offset) in self.connectivity[self.layout[position]]: if number[n] != self.numbers[position-offset][m]: return False return True def __init__(self, numbers = [None]*13 ): self.numbers = numbers def copy_numbers(self): return self.numbers[:] def setlike(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): """ One character from the number at a specific position """ return str(self.numbers[position][digit]) def num(position): """ string version of the number at a given 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.setlike_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_numbers()) if self.crossword.setlike(): self.setlike_solutions.append(self.crossword.copy_numbers()) 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 Crossword(self.solutions[0]) print "Found", len(self.setlike_solutions), \ "solution(s) without repeats." print "Here's the first:" print Crossword(self.setlike_solutions[0]) Analysis().run()