如何根据单词列表创建Boggle板？(反向Boggle求解器！)

Question

我正试图解决反向扭动问题。简单地说，给出一个单词列表，形成一个4x4的字母网格，其中列表中的单词可以在相邻的字母序列中找到(字母是正交的和对角的)。

我不想拿一个已知的板来解决它。这是一个很容易解决的问题，已经在这里讨论/解决了人们的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板x7比较。解决时间变得冷淡。

一定有更好的方法！

一些代码：

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个字母剪掉任何单词。计算所需的唯一字母数。一定要考虑到在同一个词中重复的字母。例如，如果列表中包含“雄鹰”，我认为您不能在单词的两端使用相同的“e”。如果你需要的字母列表>16，你必须删除一些单词。找出先切哪一个是个有趣的子问题.我会从包含最少使用字母的单词开始。把所有的子列表按分数排序可能会有帮助。

然后，您可以做一些简单的情况，在这些情况下，单词的总长度小于16。在此之后，从单词的完整列表开始，看看是否有解决方案。如果没有，请找出要删除哪个单词，然后再试一次。

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

愚蠢的蛮力方式是用你需要的字母遍历所有可能的网格，并测试每个字母，看看你所有的单词是否合适。但是，这是相当苛刻的:中间的大小写是16！= 2x10exp13板。N个字母的精确公式是..。(16!)/(16-n)！X波(n，16-n)。这给出了3x10exp16范围内的最坏情况。不是很容易管理。即使你可以避免旋转和翻转，这也只为你节省了1/16的搜索空间。

一种更聪明的贪婪算法是根据某些标准对单词进行排序，比如难度或长度。递归解决方案是将列表中的顶部单词保留下来，并尝试将其放在网格上。然后用那个网格和剩下的单词列表进行递归。如果你在字数用完之前填好了网格，那么你就得后退一步，尝试另一种方法来放置这个单词。一种更贪婪的方法是尝试先重复使用大多数字母的位置。你可以做些修剪。如果在任何时候，网格中留下的空格数都小于所需的其他唯一字母集，那么您可以消除这些子树。还有其他一些情况，很明显，没有解决方案可以削减，特别是当剩余的网格空间是<长度的最后一个字。搜索空间取决于单词长度和重复使用的字母数。我肯定这比暴力强，但我不知道这是否足以使问题合理。

聪明的方法是使用某种形式的动态规划。我看不出这方面的完整算法。一种方法是有一个字母树或图表，将每个字母连接到单词列表中的“相邻”字母。然后，从连接最紧密的字母开始，尝试将树映射到网格上。总是把最能完成单词列表的字母放在上面。在网格中必须有某种方法来处理同一个字母的多重情况。我不知道怎么订购这样你就不用搜索每个密码了。

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

祝你好运。

Answer 2

对于加速回溯搜索，您可以尝试以下几个一般想法：

1)早期检查。它通常有助于放弃那些永远无法尽早工作的部分解决方案，即使代价是更多的工作。考虑所有的两个字符序列产生的切碎你想要融入的单词-例如，美洲狮贡献PU，UM，MA和AS。这些都必须出现在最后的答复中。如果一个部分解没有足够的重叠的两个字符空间，可以包含它还没有的所有重叠的两个字符序列，那么它就不能扩展到最终的答案。

2)对称性。我认为，如果你试图证明没有解决办法，这可能是最有用的。给定一种填充板的方法，您可以旋转并反映该解决方案，以找到其他填充板子的方法。如果你有68K起点，其中一个起点是另一个起点的旋转或反射，你不需要两者都尝试，因为如果你能(或可以)从一个起点解决问题，你可以通过旋转或反射板从另一个起点得到答案。因此，您可能可以将需要尝试的起点数除以某个整数。

这个问题并不是每个阶段都有大量替代品的唯一问题。这也影响到旅行推销员的问题。如果你能接受没有一个保证，你会找到绝对最好的答案，你可以尝试不跟进这些68k选择中最不可能的。你需要一些分数来决定保留哪一个--你可能希望保留那些已经使用了尽可能多的字母的字母。旅行商问题的一些程序很早就放弃了节点之间毫无希望的链接。一个更普遍的方法，放弃部分解，而不是做一个完整的深度，第一次搜索或分支和定界是有限差异搜索-见例如http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2426。

当然，有些TSP丢弃树的搜索方法完全支持某种爬山方法。您可以从一个填充的摆动方块开始，并反复尝试在其中查找您的单词，修改几个字符以强制它们进入，试图找到依次增加在正方形中可以找到的单词数量的步骤。最简单的爬山方式是重复简单的爬山，从多个随机开始。另一种方法是重新开始爬山--通过随机化解决方案的一部分--因为您不知道要随机化的部分的最佳大小，您可能决定随机选择部分大小来随机化，这样至少有一小部分时间是随机的，您将正确的区域大小随机化，生成一个新的开始。遗传算法和模拟退火在这里非常流行。一篇关于新想法的论文“迟收爬山”也描述了它的一些竞争对手-- http://www.cs.nott.ac.uk/~yxb/LAHC/LAHC-TR.pdf