python - How to create a Boggle Board from a list of Words? (reverse Boggle solver!) -

i trying solve reverse boggle problem. put, given list of words, come 4x4 grid of letters in many words in list can found in sequences of adjacent letters (letters adjacent both orthogonally , diagonally).

i not want take known board , solve it. easy trie problem , has been discussed/solved death here people's cs projects.

example word list:

margays, jaguars, cougars, tomcats, margay, jaguar, cougar, pumas, puma, toms 

solution:

atjy ctsa omgs puar 

this problem hard (for me). algorithm have far:

1. for each word in input, make list of possible ways can legally appear on board itself.
2. try possible combinations of placing word #2 on boards , keep ones have no conflicts.
3. repeat till end of list.
4. ...
5. profit!!! (for read /.)

obviously, there implementation details. start longest word first. ignore words substrings of other words.

i can generate 68k possible boards 7 character word in around 0.4 seconds. when add additional 7 character board, need compare 68k x 68k boards x 7 comparisons. solve time becomes glacial.

there must better way this!!!!

some 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 template overlay.  when compare boards, add if board fits         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 check if otherboard fit existing board (allowed use blank spaces!)     # otherboard single word     @classmethod     def testoverlay(self, this_board, otherboard):         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 single word         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         r in range(row - 1, row + 2):             c in range(column - 1, column + 2):                 if r >= 0 , r < board_side_length , c >= 0 , c < 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):         # 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]         row, column in board.getvalidcoordinates(board, last_position):             new_board = board.newfromboard(board, row*board_side_length+column)             self.createall(new_board) 

and use this:

words = ['margays', 'jaguars', 'cougars', 'tomcats', 'margay', 'jaguar', 'cougar', 'pumas', 'puma'] words.sort(key=len)  first_word = words.pop()  # generate boards first word overlaid_boards = [] 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 

this interesting problem. can't quite come full, optimized solution, there here ideas might try.

the hard part requirement find optimal subset if can't fit words in. that's going add lot complexity. start eliminating word combinations aren't going work. cut words >16 letters. count number of unique letters needed. sure take account letters repeated in same word. example, if list includes "eagle" don't think allowed use same 'e' both ends of word. if list of needed letters >16, have drop words. figuring out ones cut first interesting sub-problem... i'd start words containing least used letters. might have sub-lists sorted score.

then can trivial cases total of word lengths <16. after that, start full list of words , see if there's solution that. if not, figure out word(s) drop , try again.

given word list then, core algorithm find grid (if 1 exists) contains of words.

the dumb brute-force way iterate on grids possible letters need, , test each 1 see if words fit. it's pretty harsh though: middle case 16! = 2x10exp13 boards. exact formula n unique letters is... (16!)/(16-n)! x pow(n, 16-n). gives worst case in range of 3x10exp16. not manageable. if can avoid rotations , flips, saves 1/16 of search space.

a smarter greedy algorithm sort words criteria, difficulty or length. recursive solution take top word remaining on list, , attempt place on grid. recurse grid , remaining word list. if fill grid before run out of words, have track , try way of placing word. greedier approach try placements re-use letters first. can pruning. if @ point number of spaces left in grid less remaining set of unique letters needed, can eliminate sub-trees. there few other cases it's obvious there's no solution can cut, when remaining grid spaces < length of last word. search space depends on word lengths , how many letters re-used. i'm sure it's better brute-force, don't know if it's enough make problem reasonable.

the smart way use form of dynamic programming. can't quite see complete algorithm this. 1 idea have tree or graph of letters, connecting each letter "adjacent" letters in word list. start most-connected letter , try map tree onto grid. place letter completes of word list. there'd have way of handling case of multiple of same letter in grid. , i'm not sure how order don't have search every combination.

the best thing have dynamic algorithm included sub word lists. if list had "fog" , "fox", , fox doesn't fit fog does, able handle without having run whole thing on both versions of list. that's adding complexity because have rank each solution score go. in cases words won't fit save lot of time.

good luck on this.