给定一个单词列表，你会如何将它们排列成一个填字游戏网格？
它不必像对称的“正确”填字游戏或类似的东西：基本上只为每个单词输出一个起始位置和方向。
问问题
95117 次
13 回答
67
我想出了一个可能不是最有效的解决方案，但效果很好。基本上：
- 按长度对所有单词进行降序排序。
- 取第一个单词并将其放在板上。
- 接下一个词。
- 搜索所有已经在板上的单词，看看是否有任何可能的交叉点（任何常见字母）与这个单词。
- 如果这个词有可能的位置，循环遍历板上的所有词并检查新词是否干扰。
- 如果这个词没有破坏棋盘，则将其放在那里并转到步骤 3，否则，继续搜索位置（步骤 4）。
- 继续这个循环，直到所有单词都被放置或无法放置。
这是一个有效的，但通常很差的填字游戏。我对上面的基本配方进行了许多修改，以获得更好的结果。
- 在生成填字游戏的最后，根据放置的单词数量（越多越好）、板子的大小（越小越好）以及高宽比（越接近）给它打分为 1 越好）。生成一些填字游戏，然后比较他们的分数并选择最好的一个。
- 我决定在任意时间内创建尽可能多的填字游戏，而不是运行任意数量的迭代。如果您只有一个小的单词列表，那么您将在 5 秒内获得几十个可能的填字游戏。较大的填字游戏可能只能从 5-6 种可能性中选择。
- 放置一个新词时，不是在找到可接受的位置后立即放置，而是根据它增加网格大小的多少以及有多少交叉点给该词的位置打分（理想情况下，您希望每个词都是被2-3个其他词交叉）。跟踪所有位置及其分数，然后选择最佳位置。
于 2009-06-20T15:02:03.413 回答
24
我最近刚刚用 Python 编写了自己的代码。你可以在这里找到它：http: //bryanhelmig.com/python-crossword-puzzle-generator/。它不会创建密集的 NYT 风格填字游戏，而是创建您可能在儿童益智书中找到的填字游戏风格。
与我发现的一些算法不同，这些算法实现了一些随机蛮力放置单词的方法，就像一些人建议的那样，我尝试在单词放置时实现一种稍微智能的蛮力方法。这是我的过程：
- 创建一个任意大小的网格和一个单词列表。
- 打乱单词列表，然后将单词从最长到最短排序。
- 将第一个和最长的单词放在最左上角的位置，1,1（垂直或水平）。
- 移动到下一个单词，遍历单词中的每个字母和网格中的每个单元格，寻找字母到字母的匹配。
- 找到匹配项后，只需将该位置添加到该单词的建议坐标列表中即可。
- 循环遍历建议的坐标列表并根据它跨越的其他单词数量“评分”单词位置。0 分表示位置不好（与现有单词相邻）或没有单词交叉。
- 返回步骤#4，直到单词列表用完。可选的第二关。
- 我们现在应该有一个填字游戏，但由于一些随机放置，质量可能会受到影响。所以，我们缓冲这个填字游戏并返回到第 2 步。如果下一个填字游戏有更多的单词放在板上，它会替换缓冲区中的填字游戏。这是时间限制的（在 x 秒内找到最好的填字游戏）。
到最后，你就有了一个不错的填字游戏或单词搜索游戏，因为它们差不多。它往往运行得相当好，但如果您有任何改进建议，请告诉我。更大的网格运行速度呈指数级增长；线性更大的单词列表。更大的单词列表也有更高的机会获得更好的单词放置数字。
于 2010-04-11T18:41:16.883 回答
20
大约十年前，我实际上写了一个填字游戏生成程序（它很神秘，但同样的规则也适用于普通填字游戏）。
它有一个存储在文件中的单词列表（和相关线索），按迄今为止的使用情况降序排序（因此较少使用的单词位于文件顶部）。一个模板，基本上是一个代表黑色和自由方块的位掩码，是从客户端提供的池中随机选择的。
然后，对于拼图中的每个不完整的单词（基本上找到第一个空白方块，看看右边的（跨字）或下面的（下字）也是空白的），搜索完成文件寻找适合的第一个单词，考虑到该单词中已经存在的字母。如果没有合适的词，您只需将整个词标记为不完整并继续前进。
最后是一些未完成的单词，编译器必须填写（如果需要，可以在文件中添加单词和线索）。如果他们想不出任何想法，他们可以手动编辑填字游戏以更改约束，或者只是要求完全重新生成。
一旦单词/线索文件达到一定大小（并且它每天为该客户添加 50-100 条线索），很少有需要为每个填字游戏完成超过两到三个手动修复的情况.
于 2009-06-03T05:22:59.693 回答
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)
于 2013-07-22T12:07:17.320 回答
11
虽然这是一个较老的问题，但会根据我所做的类似工作尝试回答。
有很多方法可以解决约束问题（一般属于 NPC 复杂性类）。
这与组合优化和约束规划有关。在这种情况下，约束是网格的几何形状和单词是唯一的要求等。
随机化/退火方法也可以工作（尽管在适当的设置内）。
高效的简单可能只是终极智慧！
要求是一个或多或少完整的填字游戏编译器和（可视化所见即所得）构建器。
撇开所见即所得的构建器部分不谈，编译器大纲是这样的：
加载可用的词表（按词长排序，即2,3,..,20）
在用户构建的网格上找到字槽（即网格词）（例如，x,y 处的词，长度为 L，水平或垂直）（复杂度 O(N)）
计算网格词的交点（需要填充）（复杂度 O(N^2) ）
计算单词列表中的单词与所使用的各种字母的交集（这允许使用模板搜索匹配的单词，例如cwc 使用的 Sik Cambon 论文）（复杂度 O(WL*AL)）
步骤 .3 和 .4 允许执行此任务：
一种。网格词与其自身的交集能够创建一个“模板”，用于尝试在该网格词的可用词的关联词表中找到匹配项（通过使用其他与该词相交的词的字母，这些词已经在某个特定位置填充算法步骤）
湾。单词列表中的单词与字母表的交集可以找到与给定“模板”匹配的匹配（候选）单词（例如，第一名的“A”和第三名的“B”等）。
因此，随着这些数据结构的实现，所使用的算法是这样的：
注意：如果网格和单词数据库是不变的，前面的步骤可以只做一次。
算法的第一步是随机选择一个空词槽（网格词），并用其相关词表中的候选词填充它（随机化可以在算法的连续执行中产生不同的解决方案）（复杂度 O(1) 或 O( N))
对于每个仍然为空的词槽（与已填充的词槽有交集），计算一个约束比率（这可能会有所不同，简单的是该步骤中可用解决方案的数量）并按此比率对空词槽进行排序（复杂度 O(NlogN ) 或 O(N) )
循环遍历上一步计算的空词槽，并为每个空词槽尝试多个候选解（确保保留“弧一致性”，即如果使用此词，则网格在此步骤后有解）并根据下一步的最大可用性（即，如果当时在那个地方使用这个词等，下一步有最大可能的解决方案。）（复杂度 O(N*MaxCandidatesUsed) ）
填写该单词（将其标记为已填写并转到步骤 2）
如果没有找到满足步骤 .3 标准的单词，请尝试回溯到上一步的另一个候选解决方案（此处的标准可能有所不同）（复杂度 O(N)）
如果找到回溯，则使用替代方法并可选地重置任何可能需要重置的已填充单词（再次将它们标记为未填充）（复杂度 O(N) ）
如果没有找到回溯，则找不到解决方案（至少使用此配置、初始种子等）
否则，当所有单词都填满时，您有一个解决方案
该算法对问题的解决方案树进行随机一致游走。如果在某个时候出现死胡同，它会回溯到前一个节点并遵循另一条路线。直到找到解决方案或用尽各种节点的候选者数量。
一致性部分确保找到的解决方案确实是一个解决方案，随机部分能够在不同的执行中产生不同的解决方案，并且平均而言具有更好的性能。
PS。所有这些（以及其他）都是用纯 JavaScript（具有并行处理和所见即所得）功能实现的
PS2。该算法可以很容易地并行化，以便同时产生多个（不同的）解决方案
希望这可以帮助
于 2014-05-02T19:33:39.723 回答
9
为什么不直接使用随机概率方法开始。从一个单词开始，然后反复选择一个随机单词，并尝试在不破坏大小等限制的情况下使其适合拼图的当前状态。如果失败，重新开始。
您会惊讶于这样的蒙特卡洛方法的工作频率。
于 2009-06-20T15:07:58.500 回答
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();
}
于 2014-03-07T17:04:32.213 回答
5
我会生成两个数字：长度和拼字游戏得分。假设拼字游戏分数低意味着更容易加入（低分数 = 很多常用字母）。按长度降序和拼字游戏分数升序对列表进行排序。
接下来，只需从列表中删除。如果单词不与现有单词交叉（分别检查每个单词的长度和拼字游戏分数），则将其放入队列中，并检查下一个单词。
冲洗并重复，这应该会生成一个填字游戏。
当然，我很确定这是 O(n!) 并且不能保证为您完成填字游戏，但也许有人可以改进它。
于 2009-06-03T05:26:01.907 回答
3
我一直在思考这个问题。我的感觉是，要创建一个真正密集的填字游戏，你不能希望你有限的单词列表就足够了。因此，您可能想要获取字典并将其放入“trie”数据结构中。这将使您可以轻松找到填充剩余空格的单词。在 trie 中，实现一个遍历是相当有效的，比如说，给你所有形式为“c?t”的单词。
所以，我的一般想法是：创建某种相对蛮力的方法，如本文所述，创建一个低密度的十字架，并用字典单词填充空白。
如果其他人采用这种方法，请告诉我。
于 2010-09-22T17:34:08.933 回答
3
我在玩填字游戏生成器引擎，我发现这是最重要的：
0。!/usr/bin/python
一种。
allwords.sort(key=len, reverse=True)湾。制作一些类似光标的项目/对象，它将在矩阵周围移动以便于定位，除非您以后想通过随机选择进行迭代。
第一个，拿起第一对并将它们从 0,0 上下放置；将第一个存储为我们当前的填字游戏“领导者”。
将光标按对角线顺序或以更大对角线概率随机移动到下一个空单元格
遍历单词 like 并使用可用空间长度来定义最大单词长度：
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 )将单词与我使用的可用空间进行比较，即：
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每个成功使用的单词后，改变方向。循环同时填充所有单元格，或者您用完单词或通过迭代限制然后：
# CHANGE ALL WORDS LIST
inexOf1stWord = allwords.index( leading_w )
allwords = allwords[:inexOf1stWord+1][:] + allwords[inexOf1stWord+1:][:]
...并再次迭代新的填字游戏。
通过填写的容易程度和一些估计计算来制作评分系统。如果您的评分系统满足分数，则通过将其附加到已制作的填字游戏列表中，为当前填字游戏打分并缩小以后的选择范围。
在第一次迭代会话之后，再次从制作的填字游戏列表中迭代以完成工作。
通过使用更多参数，速度可以大大提高。
于 2014-12-05T08:47:35.623 回答
3
这个项目作为一个项目出现在哈佛的AI CS50 课程中。这个想法是将填字游戏生成问题表述为一个约束满足问题，并使用不同的启发式回溯来解决它以减少搜索空间。
首先，我们需要几个输入文件：
- 填字游戏的结构（如下图所示，例如，“#”代表不填的字符，“_”代表要填的字符）
`
###_####_#
____####_#
_##_#_____
_##_#_##_#
______####
#_###_####
#_##______
#_###_##_#
_____###_#
#_######_#
##_______#
`
一个输入词汇表（单词列表/字典），将从中选择候选词（如下所示）。
a abandon ability able abortion about above abroad absence absolute absolutely ...
现在定义CSP并解决如下：
- 变量被定义为具有来自作为输入提供的单词列表（词汇表）的值（即，它们的域）。
- 每个变量由一个 3 元组表示： (grid_coordinate, direction, length) 其中坐标表示相应单词的开头，方向可以是水平或垂直，长度定义为变量将是单词的长度分配给。
- 约束由提供的结构输入定义：例如，如果水平和垂直变量具有共同的字符，它将表示为重叠（弧）约束。
- 现在，可以使用节点一致性和 AC3 弧一致性算法来减少域。
- 然后回溯以获得具有 MRV（最小剩余值）、度等的 CSP 的解决方案（如果存在）。启发式可用于选择下一个未分配的变量，并且 LCV（最小约束值）等启发式可用于域-排序，使搜索算法更快。
下面显示了使用 CSP 求解算法的实现获得的输出：
`
███S████D█
MUCH████E█
E██A█AGENT
S██R█N██Y█
SUPPLY████
█N███O████
█I██INSIDE
█Q███E██A█
SUGAR███N█
█E██████C█
██OFFENSE█
`
以下动画显示了回溯步骤：
这是另一个带有孟加拉语（孟加拉语）语言单词列表的单词：
于 2020-04-20T07:16:07.253 回答
2
我会得到每个单词使用的每个字母的索引，以了解可能的交叉。然后我会选择最大的单词并将其用作基础。选择下一个大的并穿过它。冲洗并重复。这可能是一个NP问题。
另一个想法是创建一个遗传算法，其中强度指标是您可以在网格中放入多少单词。
我发现的困难部分是何时知道某个列表不可能被越过。
于 2009-06-03T05:15:49.877 回答
2
我已经编写了一个 JavaScript/jQuery 解决方案来解决这个问题：
示例演示：http ://www.earthfluent.com/crossword-puzzle-demo.html
源代码：https ://github.com/HoldOffHunger/jquery-crossword-puzzle-generator
我使用的算法的意图：
- 尽可能减少网格中不可用方块的数量。
- 有尽可能多的混合词。
- 在极快的时间内计算。
我将描述我使用的算法：
根据共享一个共同字母的单词将单词组合在一起。
从这些组中，构建一组新的数据结构（“词块”），这是一个主词（贯穿所有其他词），然后是其他词（贯穿主词）。
从填字游戏左上角的第一个单词块开始填字游戏。
对于其余的单词块，从填字游戏的最右下角开始，向上和向左移动，直到没有更多可用的位置可以填充。如果向上的空列多于向左的空列，则向上移动，反之亦然。
于 2018-04-17T18:54:18.313 回答