python - 如何从单词列表中创建一个 Boggle Board？ (反向 Boggle 解算器!)

Question

我正试图解决相反的问题 Boggle问题。简单地说，给定一个单词列表，想出一个 4x4 的字母网格，其中可以在相邻字母序列中找到列表中尽可能多的单词(字母在正交和对角线上相邻)。

我不想拿一个已知的板来解决它。这是一个简单的 TRIE 问题，已经在这里为人们的 CS 项目讨论/解决了。

示例单词列表:

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

解决方法:

ATJY
CTSA
OMGS
PUAR

这个问题很难(对我来说)。到目前为止我的算法:

1. 对于输入中的每个单词，列出它可以合法地单独出现在板上的所有可能方式。
2. 尝试将单词 #2 放在这些板上的所有可能组合，并保留没有冲突的组合。
3. 重复直到列表结束。
4. ...
5. 利润!!! (对于那些阅读/. 的人)

显然，有实现细节。首先从最长的单词开始。忽略属于其他词的子字符串的词。

我可以在大约 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

Answer 1

这是一个有趣的问题。我不能完全想出一个完整的、优化的解决方案，但这里有一些您可以尝试的想法。

困难的部分是如果您不能将所有单词放入其中，则需要找到最佳子集。这会增加很多复杂性。首先消除明显行不通的单词组合。删除任何超过 16 个字母的单词。计算所需的唯一字母的数量。请务必考虑在同一个单词中重复出现的字母。例如，如果列表包含“eagle”，我认为您不能在单词的两端使用相同的“e”。如果您需要的字母列表大于 16，则必须删除一些单词。弄清楚先切掉哪些是一个有趣的子问题……我将从包含最少使用字母的单词开始。将所有子列表按分数排序可能会有所帮助。

然后您可以处理总字长小于 16 的简单情况。之后，您从完整的单词列表开始，看看是否有解决方案。如果不是，找出要删除的单词并重试。

然后给定一个单词列表，核心算法是找到一个包含的网格(如果存在的话) 所有这些词。

愚蠢的蛮力方法是用您需要的字母遍历所有可能的网格，然后测试每个网格以查看您的所有单词是否合适。不过这很苛刻:中间大小写是 16! = 2x10exp13 板。 n 个唯一字母的精确公式是... (16!)/(16-n)! x pow(n, 16-n)。这给出了 3x10exp16 范围内的最坏情况。不太好管理。 即使您可以避免旋转和翻转，也只能节省 1/16 的搜索空间。

一种更聪明的贪婪算法是根据一些标准对单词进行排序，例如难度或长度。递归解决方案是获取列表中剩余的最上面的单词，并尝试将其放在网格中。然后递归该网格和剩余的单词列表。如果你在用完单词之前填满了网格，那么你必须回溯并尝试另一种放置单词的方式。一种更贪婪的方法是首先尝试重新使用最多字母的放置。 你可以做一些修剪。如果在任何时候网格中剩余的空格数少于所需的剩余唯一字母集，那么您可以消除这些子树。在其他一些情况下，很明显没有可以切割的解决方案，特别是当剩余的网格空间小于最后一个单词的长度时。 搜索空间取决于单词长度和重复使用的字母数量。我确信它比蛮力要好，但我不知道它是否足以让问题变得合理。

聪明的方法是使用某种形式的动态规划。我不太明白这个的完整算法。一个想法是有一个字母树或图表，将每个字母连接到单词列表中的“相邻”字母。然后你从连接最多的字母开始，尝试将树映射到网格上。始终放置完成大部分单词列表的字母。必须有某种方法来处理网格中多个相同字母的情况。而且我不确定如何订购它，因此您不必搜索每个组合。

最好的办法是拥有一个还包括所有子词列表的动态算法。因此，如果列表中有“fog”和“fox”，而 fox 不适合但 fog 适合，它将能够处理这个问题，而不必在列表的两个版本上运行整个过程。这增加了复杂性，因为现在您必须按分数对每个解决方案进行排名。但在所有单词都不适合的情况下，它会节省很多时间。

祝你好运。