#!/usr/bin/env python
"""

 From technology review puzzle corner, Nov/Dec 2006 issue, N/D 3.
 
 Place 13 three digit squares in this pattern:
 
      *   * * *   * * *   *
      * * *   * * *   * * *
      *   * * *   * * *   *

 thirty:Desktop$ time ./squares_crossword.py 
 There are 22 three-digit perfect squares:
 [100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400,
  441, 474, 529, 576, 625, 676, 729, 784, 841, 900, 961 ]
 Brute force search space =  22 **13 =  282810057883082752 .
 Looking for solutions...
 done.
 Looked at 27447  nodes in search tree.
 Number of solutions = 14436 .
 Here's the first:
   1 225 121 1
   225 729 900
   1 676 676 0
 Number of unique solutions =  1 .
   8 169 225 1
   484 625 729
   1 441 676 6

 real	0m3.766s
 user	0m3.536s
 sys	0m0.099s
 thirty:Desktop$       

"""

# First I want a list of the three digit squares.
#   9**2 = 81 which has two digits.
#   32**2 = 1024 which has four digits.
#   So the three digit squares are i**2 where 9<i<32.
squares_list = []
for i in range(10,32):
    squares_list.append(i**2)
print "There are", len(squares_list), "three-digit perfect squares:"
print squares_list

# I'm going to need the first, second, and third digit
# of these numbers.  Rather than calculate them each time,
# I'm going to store them now in a list of tuples,
# so that for example 
#  a) squares_digits[0]    is square 0 in the list, (1,0,0), i.e. 100, and
#  b) squares_digits[0][2] is square 0, digit 2, i.e. 0 
squares_digits = []
for square in squares_list:
    squares_digits.append(( square/100,         # i.e. 1 if square=169
                            (square % 100)/10,  # i.e. 6 if square=169
                            square % 10,        # i.e. 9 if square=169
                         ))
# print squares_digits

# I'll store the answer in a list of thirteen of these three-digit tuples,
# left to right, in a crossword pattern like this.  
# I'll each of these 0 to 12 places to put a number a 'position'
#   
#    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
#
# Thus for example crossword[0]=(1,2,1) would put 121 in the left-most column.
crossword = [ (0,0,0) ]*13       # all blank = [(0,0,0), (0,0,0), ... ]

# I'm going to try to fill in the crossword left to right,
# setting crossword[0], then crossword[1], and so on.  
# To be a valid, each successive entry must be consistent 
# with what's already in position.  
# ( Note: using a series of if's like this isn't the best approach,
#   since if x=9 we have to test for 0,1,2,3,... before figuring out
#   what to do.  But it works, and its straightforward.
#   Better would be to put these checking functions into an array,
#   perhaps using lambda functions like this :
#       contraint[2] = lambda x : x[0]==crossword[1][2] )
def is_valid(position, (first, second, third )):
    if position==0:
        return True
    elif position==1:
        return first == crossword[0][1]
    elif position==2:
        return second == crossword[1][2]
    elif position==3:
        return first == crossword[2][0]
    elif position==4:
        return first == crossword[2][2]
    elif position==5:
        return first == crossword[3][2] and third == crossword[4][2]
    elif position==6:
        return first == crossword[5][1]
    elif position==7:
        return second == crossword[6][2]
    elif position==8:
        return first == crossword[7][0]
    elif position==9:
        return first == crossword[7][2]
    elif position==10:
        return first == crossword[8][2] and third == crossword[9][2]
    elif position==11:
        return first == crossword[10][1]
    elif position==12:
        return second == crossword[11][2]
    else:
        print " OOPS - checking validity of position<0 or >12 "
        return False

# Save some typing.
def c(position,digit):
    return str(crossword[position][digit])
def num(position):
    return c(position,0)+c(position,1)+c(position,2)

# printable version of a crossword.
def crossword2string():
    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)

# Here's where answers to the crossword will be stored, as displayable strings.
answers = []
answer_strings = []
unique = []

def save_answer():
    list = []
    for tuple in crossword:
        list.append( 100*tuple[0]+10*tuple[1]+tuple[2] )
    answers.append(list)
    answer_strings.append(crossword2string())

# Finally, I define a recursive routine to solve the puzzle,
# that first, tries to find a valid number for postion p,
# and for each that works, looks for a valid number at position p+1.
n_nodes = [0]
def solve(p):
    if p >= 13:
        save_answer()
    else:
        n_nodes[0] += 1
        for square in squares_digits:
            if is_valid(p, square):
                crossword[p] = square
                solve(p+1)

n_squares = len(squares_list)
print "Brute force search space = ",n_squares,"**13 = ", n_squares**13, "."
print "Looking for solutions..."
solve(0)
print "done."
print "Looked at", n_nodes[0]," nodes in search tree."

def is_unique(answer):
    for i in range(len(answer)):
        for j in range(i+1, len(answer)):
            if answer[i] == answer[j]:
                return False
    return True

def count_unique():
    n = 0;
    i = 0
    for i in range(len(answers)):
        answer=answers[i]
        if is_unique(answer):
            n += 1
            unique.append(i)
    return n

print "Number of solutions =",len(answers),"."
print "Here's the first:"
print answer_strings[0]
print "Number of unique solutions = ", count_unique(), "."
for i in unique:
    print answer_strings[i]

"""

thirty:Desktop$ ./squares_crossword.py 
There are 22 three-digit perfect squares:
 [100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529,
  576, 625, 676, 729, 784, 841, 900, 961]
Brute force search space =  22 **13 =  282810057883082752 .
Looking for solutions...
done.
Looked at 27447  nodes in search tree.
Number of solutions = 14436 .
Here's the first:
   1 225 121 1
   225 729 900
   1 676 676 0

Number of unique solutions =  1 .
   8 169 225 1
   484 625 729
   1 441 676 6
"""