title: How to create a Boggle Board from a list of Words? (reverse Boggle solver!)
body: <p>I am trying to solve the reverse <a href="http://en.wikipedia.org/wiki/Boggle" rel="nofollow">Boggle</a> problem.  Simply put, given a list of words, come up with a 4x4 grid of letters in which as many words in the list can be found in sequences of adjacent letters (letters are adjacent both orthogonally and diagonally). </p>
  
  <p><strong>I DO NOT want to take a known board and solve it.  That is an easy TRIE problem and has been discussed/solved to death here for people's CS projects.</strong></p>
  
  <p>Example word list:</p>
  
  <pre><code>margays, jaguars, cougars, tomcats, margay, jaguar, cougar, pumas, puma, toms
  </code></pre>
  
  <p>Solution:</p>
  
  <pre><code>ATJY
  CTSA
  OMGS
  PUAR
  </code></pre>
  
  <p>This problem is HARD (for me). Algorithm I have so far:</p>
  
  <ol>
  <li>For each word in the input, make a list of all possible ways it can legally be appear on the board by itself. </li>
  <li>Try all possible combinations of placing word #2 on those boards and keep the ones that have no conflicts.</li>
  <li>Repeat till end of list.</li>
  <li>... </li>
  <li>Profit!!!  (for those that read /.)</li>
  </ol>
  
  <p>Obviously, there are implementation details.  Start with the longest word first.  Ignore words that are substrings of other words.</p>
  
  <p>I can generate all 68k possible boards for a 7 character word in around 0.4 seconds.  Then when I add an additional 7 character board, I need to compare 68k x 68k boards x 7 comparisons. Solve time becomes glacial.</p>
  
  <p>There must be a better way to do this!!!!</p>
  
  <p>Some code:</p>
  
  <pre><code>BOARD_SIDE_LENGTH = 4
  
  class Board:
      def __init__(self):
          pass
  
      def setup(self, word, start_position):
          self.word = word
          self.indexSequence = [start_position,]
          self.letters_left_over = word[1:]
          self.overlay = []
          # set up template for overlay.  When we compare boards, we will add to this if the board fits
          for i in range(BOARD_SIDE_LENGTH*BOARD_SIDE_LENGTH):
              self.overlay.append('')
          self.overlay[start_position] = word[0]
          self.overlay_count = 0
  
      @classmethod
      def copy(boardClass, board):
          newBoard = boardClass()
          newBoard.word = board.word
          newBoard.indexSequence = board.indexSequence[:]
          newBoard.letters_left_over = board.letters_left_over
          newBoard.overlay = board.overlay[:]
          newBoard.overlay_count = board.overlay_count
          return newBoard
  
      # need to check if otherboard will fit into existing board (allowed to use blank spaces!)
      # otherBoard will always be just a single word
      @classmethod
      def testOverlay(self, this_board, otherBoard):
          for pos in otherBoard.indexSequence:
              this_board_letter = this_board.overlay[pos]
              other_board_letter = otherBoard.overlay[pos]
              if this_board_letter == '' or other_board_letter == '':
                  continue
              elif this_board_letter == other_board_letter:
                  continue
              else:
                  return False
          return True
  
      @classmethod
      def doOverlay(self, this_board, otherBoard):
          # otherBoard will always be just a single word
          for pos in otherBoard.indexSequence:
              this_board.overlay[pos] = otherBoard.overlay[pos]
          this_board.overlay_count = this_board.overlay_count + 1
  
      @classmethod
      def newFromBoard(boardClass, board, next_position):
          newBoard = boardClass()
          newBoard.indexSequence = board.indexSequence + [next_position]
          newBoard.word = board.word
          newBoard.overlay = board.overlay[:]
          newBoard.overlay[next_position] = board.letters_left_over[0]    
          newBoard.letters_left_over = board.letters_left_over[1:]
          newBoard.overlay_count = board.overlay_count
          return newBoard
  
      def getValidCoordinates(self, board, position):
          row = position / 4
          column = position % 4
          for r in range(row - 1, row + 2):
              for c in range(column - 1, column + 2):
                  if r &gt;= 0 and r &lt; BOARD_SIDE_LENGTH and c &gt;= 0 and c &lt; BOARD_SIDE_LENGTH:
                      if (r*BOARD_SIDE_LENGTH+c not in board.indexSequence):
                          yield r, c
  
  class boardgen:
      def __init__(self):
          self.boards = []
  
      def createAll(self, board):
          # get the next letter
          if len(board.letters_left_over) == 0:
              self.boards.append(board)
              return
          next_letter = board.letters_left_over[0]    
          last_position = board.indexSequence[-1]
          for row, column in board.getValidCoordinates(board, last_position):
              new_board = Board.newFromBoard(board, row*BOARD_SIDE_LENGTH+column)
              self.createAll(new_board)
  </code></pre>
  
  <p>And use it like this:</p>
  
  <pre><code>words = ['margays', 'jaguars', 'cougars', 'tomcats', 'margay', 'jaguar', 'cougar', 'pumas', 'puma']
  words.sort(key=len)
  
  first_word = words.pop()
  
  # generate all boards for the first word
  overlaid_boards = []
  for i in range(BOARD_SIDE_LENGTH*BOARD_SIDE_LENGTH):
      test_board = Board()
      test_board.setup(first_word, i)
      generator = boardgen()
      generator.createAll(test_board)
      overlaid_boards += generator.boards
  </code></pre>