我将尝试解决反向Boggle问题。简单来说，给定一个单词列表，在一个4x4的字母网格中，尽可能多地找到单词列表中可以在相邻字母序列中找到的单词（字母在正交和对角线上都是相邻的）。
我不想使用已知的板子进行解决。那是一个简单的TRIE问题，并且已经在这里为人们的CS项目进行了讨论/解决。
示例单词列表：
解决方案：
这个问题对我来说很难。我目前的算法如下：
我可以在大约0.4秒内生成一个7个字符单词的所有68k个可能的棋盘。然后当我添加另一个7个字符的棋盘时，我需要比较68k x 68k个棋盘，进行7次比较。解决时间变得非常缓慢。
肯定有更好的方法来解决这个问题！！！
一些代码：
margays, jaguars, cougars, tomcats, margay, jaguar, cougar, pumas, puma, toms
解决方案：
ATJY
CTSA
OMGS
PUAR
这个问题对我来说很难。我目前的算法如下：
- 对于输入中的每个单词，都列出它可以合法地出现在棋盘上的所有可能方式。
- 尝试在这些棋盘上放置第二个单词的所有可能组合，并保留没有冲突的那些。
- 重复直到列表结束。
- ...
- 赚钱!!!（对于那些阅读/的人）
我可以在大约0.4秒内生成一个7个字符单词的所有68k个可能的棋盘。然后当我添加另一个7个字符的棋盘时，我需要比较68k x 68k个棋盘，进行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