5
我正試圖解決Boggle反向問題。簡單地說，給出一個單詞列表，提出一個4x4的字母表格，其中列表中的許多單詞可以在相鄰字母序列中找到（字母正交和對角地相鄰）。如何從單詞列表創建一個Boggle Board？ （反向Boggle解算器！）
我不想拿一個已知的電路板並解決它。這是一個簡單的TRIE問題，在人們的CS項目中已經討論/解決了這個問題。
示例單詞列表：
margays, jaguars, cougars, tomcats, margay, jaguar, cougar, pumas, puma, toms
解決方案：
ATJY
CTSA
OMGS
PUAR
這個問題確實很難（對我來說）。算法我到目前爲止：
- 對於輸入中的每個單詞，列出所有可能的方式，它可以合法地出現在板上。
- 嘗試在這些板上放置單詞＃2的所有可能組合，並保留那些沒有衝突的組合。
- 重複至列表結尾。
- ...
- 利潤！ （對於那些讀/）
很明顯，有實現細節。先從最長的單詞開始。忽略其他詞的子字串。
我可以在大約0.4秒內爲7個字符的單詞生成所有68k塊可能的電路板。然後，當我添加額外的7字符板時，我需要比較68k x 68k板x 7比較。解決時間變成冰河。
必須有更好的方法來做到這一點！
一些代碼：
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 >= 0 and r < BOARD_SIDE_LENGTH and c >= 0 and 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):
# 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)
而且使用這樣的：
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
「Boggle」的含義很簡單，也就是說，您是否考慮了實際的Boggle多維數據集（來自一些變體）？例如，Qu在實際遊戲中的立方體的單個面上，並且存在特定的字母分佈。 – ooga
@ooga：http：//en.wikipedia.org/wiki/Boggle，你可以忽略Qu和其他Digraphs的目的。信件分發僅基於提供的信件。 – Richard
我想象你可以通過預先計算某些事情來節省大量的工作。只有68k板意味着您可以在字典中將通用詞的哈希值包含在獨特的棋盤狀態中。然後你的問題就變成了識別包含每個單詞的已知電路板，以及哪個電路板最經常出現。 –