1  #!/usr/bin/python
   2   
   3  #..........................................................
   4  #
   5  #  Copyright  by Gary Ditlow   2008
   6  #
   7  #..........................................................
   8   
   9  def allSols(words,dim):
  10  # find all solutions by writing the words in 
  11  # all 8 directions and into each location in the array
  12   
  13    hash = {}
  14    nr,nc = dim
  15    
  16    dirs  = [[1,1],[-1,-1],[1,-1],[-1,1],[-1,0],[0,1],[1,0],[0,-1]]
  17    locs  = [[i,j] for i in range(nr) for j in range(nc)]
  18  
  19    for word in words:
  20      sol = []
  21      for loc in locs:
  22        for dir in dirs:
  23          a = newArray(dim)
  24          good = 1
  25          r,c  = loc[:]
  26          for char in word:
  27            if r<0 or r>=nr or c<0 or c>=nc: 
  28              good=0
  29              break
  30            else:
  31              a[r][c] = char
  32              r+=dir[0]
  33              c+=dir[1]
  34          if good: sol.append(a)
  35   
  36      hash[word]=sol
  37  
  38    return hash
  39  
  40  #..........................................................
  41   
  42  def isValid(array,a):
  43  # is "a" compatible with the valid "array"
  44   
  45    nr,nc = dimArray(a)
  46  
  47    for i in range(nr):
  48      for j in range(nc):
  49        if array[i][j] != "." and              \
  50           a[i][j]     != "." and              \
  51           array[i][j] != a[i][j]: return 0
  52    
  53    return 1
  54    
  55  #..........................................................
  56   
  57  def search(array,words,hash):
  58  # recursively search for a solution
  59  # array = valid solution so far
  60  # hash  = hashed set of solutions
  61  
  62    nr,nc = dimArray(array)
  63    sols  = hash[words[0]]
  64  
  65    for sol in sols:
  66      if isValid(array,sol):
  67        a = [0]*len(array)
  68        for i in range(len(array)): 
  69          a[i]=array[i][:]
  70  
  71        for i in range(nr):
  72          for j in range(nc):
  73            if sol[i][j] != ".":
  74              a[i][j] = sol[i][j]
  75  
  76        if len(words[1:])==0: 
  77          return a
  78        else:
  79          a1 = search(a,words[1:],hash)
  80          if len(a1)!=0: return a1
  81     
  82    return []
  83   
  84  #..........................................................
  85   
  86  def solve(words,dim):
  87  # solve the word puzzle
  88  
  89    f = lambda x,y:cmp(len(x),len(y))
  90    w = words[:]
  91    w.sort(f)
  92    w.reverse()
  93  
  94    array = newArray(dim)
  95    hash  = allSols(words,dim)
  96    s     = search(array,w,hash)
  97    
  98    return s
  99  
 100  #..........................................................
 101  
 102  def newArray(dim):
 103  # create a new character array with fill character "."
 104   
 105    nr,nc = dim
 106    a = [0]*nr
 107  
 108    for i in range(nr): a[i] = ["."]*nc
 109    return a
 110    
 111  #..........................................................
 112   
 113  def prtArray(a):
 114  # print the array
 115   
 116    f = lambda x: "".join(x)
 117    s = map(f,a)
 118    for d in s: print d
 119  
 120  #..........................................................
 121   
 122  def dimArray(a):
 123  # dimension of an array
 124   
 125    return [len(a),len(a[0])]
 126   
 127  #..........................................................
 128   
 129  dim   = [4,4]
 130  words = ["cat","dog","spot","pad","top","cog","oak","in","on","we"]
 131  
 132  s = solve(words,dim)
 133  prtArray(s)