生成填字游戏的算法

Question

生成填字游戏的算法

algorithmcrosswordlanguage-agnostic

128

如果给你一列单词，你会如何将它们排列成一个填字游戏的表格呢？

这个填字游戏的表格并不需要像传统的填字游戏那样对称或者其他特殊要求。你只需要输出每个单词的起始位置和方向即可。

- nickf

13个回答

24

我最近用Python写了一个交叉字谜生成器。你可以在这里找到它：http://bryanhelmig.com/python-crossword-puzzle-generator/。它不会创建密集的纽约时报风格的交叉字谜，而是像你在孩子的谜题书中发现的那种。

与我发现的一些实现随机暴力布局单词方法的算法不同，我试图实现一种稍微更加聪明的暴力方法来布置单词。以下是我的过程：

创建任意大小的网格和单词列表。
打乱单词列表，然后将单词按从长到短排序。
将第一个和最长的单词放在左上角位置1,1（垂直或水平）。
移动到下一个单词，循环遍历单词中的每个字母和网格中的每个单元格，寻找字母对字母的匹配。
找到匹配时，将该位置添加到该单词的建议坐标列表中。
循环遍历建议坐标列表，并根据它横跨多少其他单词来“评分”单词布置。得分为0表示不良的布局（相邻于现有单词）或没有单词交叉。
返回步骤#4，直到单词列表耗尽。可选第二次扫描。
现在我们应该有了一个交叉字谜，但由于某些随机布局可能会出现好坏参半的情况。因此，我们缓存这个交叉字谜并返回步骤#2。如果下一个交叉字谜在板子上放置更多的单词，它将替换缓存中的交叉字谜。这是有时间限制的（在x秒内找到最好的交叉字谜）。

到最后，你会得到一个不错的交叉字谜或者文字搜索谜题，因为它们几乎是一样的。它倾向于运行得相当不错，但如果你有任何改善建议，请告诉我。更大的网格运行速度呈指数级下降；更大的单词列表线性下降。更大的单词列表也有更高的机会获得更好的单词布局。

- Bryan

@Neil N：对于其他单词可能有更好的字母匹配可能性。也许按每个单词包含的不同字母数量进行排序是一种方法，这将大多数情况下导致相同的结果。 - Karl Adler

Python中的array.sort(key=f)是稳定的，这意味着（例如）仅通过长度对字母单词列表进行排序将保持所有8个字母单词按字母顺序排序。 - Lynn

4

@Bryan，您的网站链接对我无效，主要域名只会重定向到Twitter。您是否有更新的代码链接？ - Michael A

2

这是（显然）Bryan生成器的克隆：https://github.com/jeremy886/crossword_helmig - lvictorino

20

大约十年前，我编写了一个填字游戏生成程序（它是加密的，但同样的规则也适用于普通填字游戏）。

程序中有一个单词列表（以降序存储使用频率），其中包含与之相关的提示，这些单词和提示存储在文件中。从客户端提供的池中随机选择一个模板（基本上是代表黑色方块和空白方块的位掩码）。

然后，对于谜题中每个非完整单词（基本上是找到第一个空白方块，并查看右侧（横向）或下方（竖向）是否也为空白方块），会在文件中进行搜索，寻找第一个符合条件的单词，考虑已经存在该单词中的字母。如果没有符合条件的单词，则将整个单词标记为不完整并继续下一步。

最后，会有一些未完成的单词需要手动填入（如果需要，还要将单词和提示添加到文件中）。如果他们想不出任何主意，可以手动编辑填字游戏，修改限制条件或者请求完全重新生成。

一旦单词/提示文件达到一定大小（对于这个客户端，每天添加50-100个提示），每个填字游戏很少需要超过两到三个手动修正。

- paxdiablo

这对我的情况实际上没有帮助，因为我只有大约6-12个单词的列表。我的更像是用户的学习练习，而不是单词拼图。无论如何，算法很有趣！ - nickf

1

很好的描述。我以前也想过几次，但从未尝试过。现在来到了神奇的问题：它的效果如何？仅适用于稀疏的难题，还是也适用于密集的难题（例如论文中的）？对于密集的难题需要多少线索？ - dmckee --- ex-moderator kitten

1

@dmckee，虽然时间有点久远了，但从记忆来看，即使是密集的难题也相当不错。许多问题可以在没有干预的情况下完成，但仍然可能有五分之一左右需要添加一个或两个额外的单词。而且我们谈论的是文件中数千个单词。毫无疑问，回溯法可能有所帮助，但对于客户来说，拒绝有5个未完成单词的问题比担心如何提供额外的线索更容易。我看到的未完成单词的上限大约是五个。 - paxdiablo

17

这个算法可以在60秒内创建50个密集的6x9 箭头填字游戏。它使用一个单词数据库（包含单词和提示）和一个棋盘数据库（带有预配置的棋盘）。

1) Search for all starting cells (the ones with an arrow), store their size and directions
2) Loop through all starting cells
2.1) Search a word
2.1.1) Check if it was not already used
2.1.2) Check if it fits
2.2) Add the word to the board
3) Check if all cells were filled

一个更大的单词数据库可以显著减少生成时间，而某些类型的游戏板更难填充！更大的游戏板需要更多时间才能正确填充！

示例：

预配置的6x9板：

(# 表示一个单元格中有一个提示，% 表示一个单元格中有两个提示，箭头未显示)

# - # # - % # - # 
- - - - - - - - - 
# - - - - - # - - 
% - - # - # - - - 
% - - - - - % - - 
- - - - - - - - -

生成的6x9棋盘：

# C # # P % # O # 
S A T E L L I T E 
# N I N E S # T A 
% A B # A # G A S 
% D E N S E % W E 
C A T H E D R A L

提示 [行，列]：

[1,0] SATELLITE: Used for weather forecast
[5,0] CATHEDRAL: The principal church of a city
[0,1] CANADA: Country on USA's northern border
[0,4] PLEASE: A polite way to ask things
[0,7] OTTAWA: Canada's capital
[1,2] TIBET: Dalai Lama's region
[1,8] EASEL: A tripod used to put a painting
[2,1] NINES: Dressed up to (?)
[4,1] DENSE: Thick; impenetrable
[3,6] GAS: Type of fuel
[1,5] LS: Lori Singer, american actress
[2,7] TA: Teaching assistant (abbr.)
[3,1] AB: A blood type
[4,3] NH: New Hampshire (abbr.)
[4,5] ED: (?) Harris, american actor
[4,7] WE: The first person of plural (Grammar)

- thiagolr

11

虽然这是一个比较旧的问题，但我会基于我的类似工作尝试回答。解决约束问题有许多方法（通常属于NPC复杂度类）。这与组合优化和约束编程有关。在这种情况下，约束是网格的几何形状和单词唯一性等要求。随机化/退火方法也可以使用（但必须在适当的设置下）。高效的简易性可能只是最终的智慧！要求是更或多或少完整的填字游戏编译器和（可视化WYSIWYG）构建器。撇开WYSIWYG构建器部分，编译器大纲如下：

加载可用的单词列表（按单词长度排序，例如2,3,..,20）
在用户构建的网格上找到单词插槽（即网格中的单词）（例如x,y处具有长度L的单词，水平或垂直）（复杂度为O(N)）
计算需要填充的网格单词的交点（复杂度为O(N^2)）
计算单词列表中的单词与所使用的各个字母的交集（这允许通过使用模板（例如Sik Cambon thesis as used by cwc）搜索匹配的单词）（复杂度为O(WL*AL)）

步骤.3和.4允许完成此任务：

a. 网格单词之间的交叉点可以创建一个“模板”，以尝试在此网格单词的关联可用单词列表中查找匹配项（通过使用已经在算法某个步骤中填充的其他交叉单词的字母）。

b. 单词表中的单词与字母表的交集可以找到与给定“模板”相匹配的匹配（候选）单词（例如，第1个位置为'A'，第3个位置为'B'等）。

因此，实现了这些数据结构后，使用的算法类似于：

注意：如果网格和单词数据库是恒定的，则可以仅执行上述步骤一次。

算法的第一步是随机选择一个空白单元格（网格单词），并从其关联的单词列表中填入候选单词（随机化使得在算法的连续执行中产生不同的解决方案）（复杂度为O(1)或O(N)）。
对于每个仍为空的单词槽（与已填充单词槽有交叉），计算一个约束比率（这可以变化，简单的方法是在该步骤可用的解决方案数量），并按此比率对空单词槽进行排序（复杂度为O(NlogN)或O(N)）。
循环遍历上一步计算出的空白单词槽，并为每个单词尝试多个候选解（确保“弧一致性”保持不变，即如果使用该单词，则网格在此步骤后具有解决方案），并根据下一步的最大可用性进行排序（即如果该单词在那个时间和地点使用，则下一步具有最大可能的解决方案等）（复杂度为O(N*MaxCandidatesUsed)）。
填写该单词（标记为填写并转到步骤2）。
如果没有找到符合第3步标准的单词，则尝试回溯到先前某个步骤的其他候选解决方案（此处标准可能会有所变化）（复杂度为O(N)）。
如果找到回溯，则使用替代方案，并可选择重置可能需要重置的任何已填充单词（将它们标记为未填充）（复杂度为O(N)）。
如果没有找到回溯，则找不到解决方案（至少是在该配置、初始种子等情况下）。
否则，当所有单词槽都被填满时，就有一个解决方案。

该算法对问题的解决树进行随机一致性遍历。如果某个节点陷入死局，它会回溯到先前的节点并跟随另一条路径，直到找到解决方案或各节点的候选数用尽为止。

一致性部分确保找到的解决方案确实是解决方案，而随机部分则使其能够在不同的执行中生成不同的解决方案，并且平均表现更好。

PS. 所有这些（以及其他）都是使用纯JavaScript（具有并行处理和所见即所得功能）实现的。

PS2. 该算法可以轻松并行化，以同时产生多个（不同的）解决方案。

希望这可以帮到您。

- Nikos M.

1

这是用于创建密集布局（类似于纽约时报）还是稀疏布局？ - Jim

1

@Jim，这主要是针对密集布局的，但也可以调整为稀疏布局。不同之处在于，在密集布局（例如经典、斯堪的纳维亚等）中，人们有网格并搜索单词，而在自由形式布局（稀疏）中，人们有单词并搜索网格。 - Nikos M.

1

你是否有一些实现上述步骤的示例源代码可用？例如，我对大部分内容都很了解（并且已经独立实现了大部分内容），但是当涉及到“计算约束比率…”时，我必须承认你让我迷惑了。在网上搜索“STH Ratio”之类的东西对我也没有什么帮助。我的实现问题在于尝试找到填充词语非常低效，并且花费的时间太长。 - Jim

1

@Jim，我已经有这个了，但是这是为了我以前的一份工作而特别制作的。如果需要更多帮助，请联系我。可能会在我的开源项目中发布一个轻量级版本。顺便说一句，有些情况下我发布的算法确实会花费太长时间，但平均而言并不会。 - Nikos M.

1

@Jim，请看一下这个跨字游戏网站（仍在建设中）istavrolexo.gr（希腊语），其中有各种（密集的）跨字游戏（例如斯堪的纳维亚，经典，数独），这些游戏是由类似算法生成的（一个大型斯堪的纳维亚跨字游戏）。 - Nikos M.

9

为什么不先使用随机概率方法呢？从一个单词开始，然后反复选择一个随机单词，并尝试将其适配到当前的谜题状态中，而不会破坏大小等约束条件。如果失败了，就重新开始。

您会惊讶地发现，像这样的蒙特卡罗方法经常奏效。

- Yogi

2

是的，这是我选择的方法。你不必试图聪明过人。在循环中，随机选择一个单元格（列和行坐标），并将单词放在棋盘上，测试以查看它是否超出了边缘或干扰了其他单词（在将单词写入网格之前，请检查每个单元格是空的还是如果它有一个字母，那个字母是否与你试图写的字母匹配）。还有一些其他的逻辑来检查边界等等。我采用蛮力生成一堆越来越小的网格，然后根据相交的单词对最小的进行排名。 - ChatGPT

7

这是基于nickf和Bryan Python代码的JavaScript代码，如果有其他人需要js代码，我将其发布在此。

function board(cols, rows) { //instantiator object for making gameboards
this.cols = cols;
this.rows = rows;
var activeWordList = []; //keeps array of words actually placed in board
var acrossCount = 0;
var downCount = 0;

var grid = new Array(cols); //create 2 dimensional array for letter grid
for (var i = 0; i < rows; i++) {
    grid[i] = new Array(rows);
}

for (var x = 0; x < cols; x++) {
    for (var y = 0; y < rows; y++) {
        grid[x][y] = {};
        grid[x][y].targetChar = EMPTYCHAR; //target character, hidden
        grid[x][y].indexDisplay = ''; //used to display index number of word start
        grid[x][y].value = '-'; //actual current letter shown on board
    }
}

function suggestCoords(word) { //search for potential cross placement locations
    var c = '';
    coordCount = [];
    coordCount = 0;
    for (i = 0; i < word.length; i++) { //cycle through each character of the word
        for (x = 0; x < GRID_HEIGHT; x++) {
            for (y = 0; y < GRID_WIDTH; y++) {
                c = word[i];
                if (grid[x][y].targetChar == c) { //check for letter match in cell
                    if (x - i + 1> 0 && x - i + word.length-1 < GRID_HEIGHT) { //would fit vertically?
                        coordList[coordCount] = {};
                        coordList[coordCount].x = x - i;
                        coordList[coordCount].y = y;
                        coordList[coordCount].score = 0;
                        coordList[coordCount].vertical = true;
                        coordCount++;
                    }

                    if (y - i + 1 > 0 && y - i + word.length-1 < GRID_WIDTH) { //would fit horizontally?
                        coordList[coordCount] = {};
                        coordList[coordCount].x = x;
                        coordList[coordCount].y = y - i;
                        coordList[coordCount].score = 0;
                        coordList[coordCount].vertical = false;
                        coordCount++;
                    }
                }
            }
        }
    }
}

function checkFitScore(word, x, y, vertical) {
    var fitScore = 1; //default is 1, 2+ has crosses, 0 is invalid due to collision

    if (vertical) { //vertical checking
        for (i = 0; i < word.length; i++) {
            if (i == 0 && x > 0) { //check for empty space preceeding first character of word if not on edge
                if (grid[x - 1][y].targetChar != EMPTYCHAR) { //adjacent letter collision
                    fitScore = 0;
                    break;
                }
            } else if (i == word.length && x < GRID_HEIGHT) { //check for empty space after last character of word if not on edge
                 if (grid[x+i+1][y].targetChar != EMPTYCHAR) { //adjacent letter collision
                    fitScore = 0;
                    break;
                }
            }
            if (x + i < GRID_HEIGHT) {
                if (grid[x + i][y].targetChar == word[i]) { //letter match - aka cross point
                    fitScore += 1;
                } else if (grid[x + i][y].targetChar != EMPTYCHAR) { //letter doesn't match and it isn't empty so there is a collision
                    fitScore = 0;
                    break;
                } else { //verify that there aren't letters on either side of placement if it isn't a crosspoint
                    if (y < GRID_WIDTH - 1) { //check right side if it isn't on the edge
                        if (grid[x + i][y + 1].targetChar != EMPTYCHAR) { //adjacent letter collision
                            fitScore = 0;
                            break;
                        }
                    }
                    if (y > 0) { //check left side if it isn't on the edge
                        if (grid[x + i][y - 1].targetChar != EMPTYCHAR) { //adjacent letter collision
                            fitScore = 0;
                            break;
                        }
                    }
                }
            }

        }

    } else { //horizontal checking
        for (i = 0; i < word.length; i++) {
            if (i == 0 && y > 0) { //check for empty space preceeding first character of word if not on edge
                if (grid[x][y-1].targetChar != EMPTYCHAR) { //adjacent letter collision
                    fitScore = 0;
                    break;
                }
            } else if (i == word.length - 1 && y + i < GRID_WIDTH -1) { //check for empty space after last character of word if not on edge
                if (grid[x][y + i + 1].targetChar != EMPTYCHAR) { //adjacent letter collision
                    fitScore = 0;
                    break;
                }
            }
            if (y + i < GRID_WIDTH) {
                if (grid[x][y + i].targetChar == word[i]) { //letter match - aka cross point
                    fitScore += 1;
                } else if (grid[x][y + i].targetChar != EMPTYCHAR) { //letter doesn't match and it isn't empty so there is a collision
                    fitScore = 0;
                    break;
                } else { //verify that there aren't letters on either side of placement if it isn't a crosspoint
                    if (x < GRID_HEIGHT) { //check top side if it isn't on the edge
                        if (grid[x + 1][y + i].targetChar != EMPTYCHAR) { //adjacent letter collision
                            fitScore = 0;
                            break;
                        }
                    }
                    if (x > 0) { //check bottom side if it isn't on the edge
                        if (grid[x - 1][y + i].targetChar != EMPTYCHAR) { //adjacent letter collision
                            fitScore = 0;
                            break;
                        }
                    }
                }
            }

        }
    }

    return fitScore;
}

function placeWord(word, clue, x, y, vertical) { //places a new active word on the board

    var wordPlaced = false;

    if (vertical) {
        if (word.length + x < GRID_HEIGHT) {
            for (i = 0; i < word.length; i++) {
                grid[x + i][y].targetChar = word[i];
            }
            wordPlaced = true;
        }
    } else {
        if (word.length + y < GRID_WIDTH) {
            for (i = 0; i < word.length; i++) {
                grid[x][y + i].targetChar = word[i];
            }
            wordPlaced = true;
        }
    }

    if (wordPlaced) {
        var currentIndex = activeWordList.length;
        activeWordList[currentIndex] = {};
        activeWordList[currentIndex].word = word;
        activeWordList[currentIndex].clue = clue;
        activeWordList[currentIndex].x = x;
        activeWordList[currentIndex].y = y;
        activeWordList[currentIndex].vertical = vertical;

        if (activeWordList[currentIndex].vertical) {
            downCount++;
            activeWordList[currentIndex].number = downCount;
        } else {
            acrossCount++;
            activeWordList[currentIndex].number = acrossCount;
        }
    }

}

function isActiveWord(word) {
    if (activeWordList.length > 0) {
        for (var w = 0; w < activeWordList.length; w++) {
            if (word == activeWordList[w].word) {
                //console.log(word + ' in activeWordList');
                return true;
            }
        }
    }
    return false;
}

this.displayGrid = function displayGrid() {

    var rowStr = "";
    for (var x = 0; x < cols; x++) {

        for (var y = 0; y < rows; y++) {
            rowStr += "<td>" + grid[x][y].targetChar + "</td>";
        }
        $('#tempTable').append("<tr>" + rowStr + "</tr>");
        rowStr = "";

    }
    console.log('across ' + acrossCount);
    console.log('down ' + downCount);
}

//for each word in the source array we test where it can fit on the board and then test those locations for validity against other already placed words
this.generateBoard = function generateBoard(seed = 0) {

    var bestScoreIndex = 0;
    var top = 0;
    var fitScore = 0;
    var startTime;

    //manually place the longest word horizontally at 0,0, try others if the generated board is too weak
    placeWord(wordArray[seed].word, wordArray[seed].displayWord, wordArray[seed].clue, 0, 0, false);

    //attempt to fill the rest of the board 
    for (var iy = 0; iy < FIT_ATTEMPTS; iy++) { //usually 2 times is enough for max fill potential
        for (var ix = 1; ix < wordArray.length; ix++) {
            if (!isActiveWord(wordArray[ix].word)) { //only add if not already in the active word list
                topScore = 0;
                bestScoreIndex = 0;

                suggestCoords(wordArray[ix].word); //fills coordList and coordCount
                coordList = shuffleArray(coordList); //adds some randomization

                if (coordList[0]) {
                    for (c = 0; c < coordList.length; c++) { //get the best fit score from the list of possible valid coordinates
                        fitScore = checkFitScore(wordArray[ix].word, coordList[c].x, coordList[c].y, coordList[c].vertical);
                        if (fitScore > topScore) {
                            topScore = fitScore;
                            bestScoreIndex = c;
                        }
                    }
                }

                if (topScore > 1) { //only place a word if it has a fitscore of 2 or higher

                    placeWord(wordArray[ix].word, wordArray[ix].clue, coordList[bestScoreIndex].x, coordList[bestScoreIndex].y, coordList[bestScoreIndex].vertical);
                }
            }

        }
    }
    if(activeWordList.length < wordArray.length/2) { //regenerate board if if less than half the words were placed
        seed++;
        generateBoard(seed);
    }
}
}
function seedBoard() {
    gameboard = new board(GRID_WIDTH, GRID_HEIGHT);
    gameboard.generateBoard();
    gameboard.displayGrid();
}

- FascistDonut

单词对象模式缺失，请提供wordArray。 - whoopdedoo

就像 ['apple', 'orange', 'pear'] 这样的单词数组。 - FascistDonut

嗨，FYI我的编辑并没有改变太多的代码，只是对其进行了格式化。我知道在“内联”查看时它看起来很混乱，但是如果您想查看代码中的实际更改，请单击“并排标记”。哦...我应该在编辑说明中写“格式化代码”，但是算了吧。 - double-beep

这是如何工作的？你能提供一个包含这个 JavaScript 的 HTML 文件吗？ - GKS

5

我将生成两个数字：长度和Scrabble得分。假设低的Scrabble得分意味着更容易加入（低分=共同字母很多）。按长度降序和Scrabble得分升序排序列表。

接下来，按顺序检查列表。如果单词与现有单词没有交叉（通过它们的长度和Scrabble得分逐一检查每个单词），则将其放入队列中，并继续检查下一个单词。

重复此过程，就可以产生一个纵横填字游戏。

当然，我相信这是O(n!)，且不能保证为您完成纵横填字游戏，但也许有人可以改善它。

- Eric

3

我在使用填字游戏生成引擎时，发现了以下最重要的内容：

0.!/usr/bin/python

a. allwords.sort(key=len, reverse=True)

b. make some item/object like cursor which will walk around matrix for easy orientation unless you want to iterate by random choice later on.
the first, pick up first pair and place them across and down from 0,0 ; store the first one as our current crossword 'leader'.
move cursor by order diagonal or random with greater diagonal probability to next empty cell
iterate over the words like and use free space length to define max word length : temp=[] for w_size in range( len( w_space ), 2, -1 ) : # t for w in [ word for word in allwords if len(word) == w_size ] : # if w not in temp and putTheWord( w, w_space ) : # temp.append( w )

to compare word against free space I used i.e. :

w_space=['c','.','a','.','.','.'] # whereas dots are blank cells

# CONVERT MULTIPLE '.' INTO '.*' FOR REGEX

pattern = r''.join( [ x.letter for x in w_space ] )
pattern = pattern.strip('.') +'.*' if pattern[-1] == '.' else pattern

prog = re.compile( pattern, re.U | re.I )

if prog.match( w ) :
    #
    if prog.match( w ).group() == w :
        #
        return True

after each successfully used word, change direction. Loop while all cells are filled OR you run out of words OR by limit of iterations then :

# 更改所有单词列表 leading_w的索引 = allwords.index( leading_w ) allwords = allwords[:inexOf1stWord+1][:] + allwords[inexOf1stWord+1:][:]

...然后再次迭代新的填字游戏。

通过易于填充和一些估算计算成绩系统。如果当前填字游戏得分符合您的评分系统，则为其打分并将其添加到制作的填字游戏列表中，以缩小后续选择范围。
在第一个迭代会话之后，从制作的填字游戏列表中再次迭代以完成工作。

使用更多参数可以大幅提高速度。

- Alex

3

我一直在思考这个问题。我的感觉是，要创建一个真正密集的填字游戏，你不可能只依靠有限的词汇表。因此，你可能需要将字典放入“trie”数据结构中。这样就可以轻松地找到填补剩余空间的单词。在trie中，实现遍历，比如找到所有形式为“c?t”的单词，是相当有效的。

因此，我的一般想法是：采用某种相对粗暴的方法来创建一个低密度的填字游戏，并用字典单词填补空白部分。

如果有其他人采用了这种方法，请让我知道。

- Jake

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nickf · Accepted Answer

我想到了一种解决方案，可能不是最高效的，但足够好用。基本上：

按长度从长到短排序所有单词。
将第一个单词放在棋盘上。
取下一个单词。
查找已经放在棋盘上的所有单词，看看是否有可能与此单词交叉（任何共同字母）。
如果有这个单词的可能位置，则循环遍历已经放在棋盘上的所有单词，并检查新单词是否会干扰。
如果这个单词不会打破棋盘，则放置它并转到步骤3，否则继续寻找位置（步骤4）。
继续这个循环直到所有单词都被放置或无法放置。

这样可以制作出一个可用但通常相当差的纵横填字游戏。我对上述基本方法进行了一些修改，以得到更好的结果。

在生成纵横填字游戏结束时，根据放置的单词数量（越多越好）、棋盘大小（越小越好）以及高度与宽度之间的比例（越接近1越好）对其进行评分。生成多个纵横填字游戏，然后比较它们的得分并选择最好的一个。
- 我决定不是运行任意数量的迭代，而是在任意时间内创建尽可能多的纵横填字游戏。如果您只有一个小的单词列表，则可以在5秒钟内获得数十个可能的纵横填字游戏。一个更大的纵横填字游戏可能只会从5-6个可能性中选择一个。
在放置新单词时，不要立即将其放置在可接受的位置上，而是根据它增加网格大小的程度以及交叉点的数量（理想情况下，每个单词都应该被2-3个其他单词穿过）给该单词位置评分。跟踪所有位置及其分数，然后选择最好的。