生成纵横字谜的算法

给定一个单词列表，您将如何将它们排列成纵横字谜网格？

它不必像一个“正确的”纵横字谜，是对称的或类似的东西: 基本上只是输出一个开始的位置和方向为每个字。

102768 次浏览
小开

我会得到一个索引的每个字母使用的每个单词知道可能的交叉。然后，我会选择最大的单词，并使用它作为基础。选择下一个大的，然后交叉。冲洗，重复。可能是 NP 问题。

另一个想法是创建一个遗传算法，其中的强度度量是你可以在网格中放入多少个单词。

我发现最困难的部分是什么时候知道某个名单是不可能被跨越的。

小开

实际上，我在十年前写了一个填字游戏生成程序(它很神秘，但是对于普通的填字游戏也是同样的规则)。

它有一个单词列表(和相关的线索)存储在一个文件中，根据到目前为止的降序用法进行排序(因此，较少使用的单词位于文件的顶部)。一个模板，基本上是一个代表黑色和自由正方形的位掩码，从客户端提供的池中随机选择。

然后，对于拼图中的每一个不完整的单词(基本上找到第一个空格，看看右边的那个(横向单词)或者下面的那个(下向单词)是否也是空格) ，对文件进行搜索，寻找第一个合适的单词，同时考虑到该单词中已经存在的字母。如果没有合适的单词，你只需将整个单词标记为不完整，然后继续前进。

最后将是一些未完成的单词，编译器将不得不填写(并添加单词和线索的文件，如果需要的话)。如果他们不能想出 任何的点子，他们可以手动编辑填字游戏来改变约束，或者只是要求完全重新生成。

一旦文字/线索文件达到一定的大小(并且它每天为这个客户添加50-100个线索) ，很少有一个案例需要为每个填字游戏进行超过两到三次的手动修复。

小开

我会生成两个数字: 长度和拼字游戏得分。假设拼字游戏得分低意味着更容易加入(低得分 = 许多常见字母)。按照长度降序和拼字游戏分数升序对列表进行排序。

接下来，按照列表往下看。如果该单词没有与现有单词交叉(分别通过单词的长度和 Scrabble 分数检查每个单词) ，则将其放入队列中，并检查下一个单词。

漂洗和重复，这应该生成一个纵横字谜。

当然，我很确定这是 O (n!)并不能保证你能完成填字游戏，但也许有人可以改进一下。

小开
最佳答案

我想出了一个可能不是最有效的解决方案，但是它运行得很好。基本上:

  1. 按长度对所有单词进行排序，降序。
  2. 把第一个单词写在黑板上。
  3. 下一个词。
  4. 搜索所有已经在黑板上的单词，看看是否有任何可能的交叉点(任何常见的字母)与这个单词。
  5. 如果这个单词有可能的位置，循环遍历黑板上的所有单词，检查是否有新单词干扰。
  6. 如果这个单词没有打破黑板，那么把它放在那里，然后进入步骤3，否则，继续寻找一个地方(步骤4)。
  7. 继续这个循环，直到所有单词都被放置或无法放置。

这使得一个工作，但往往是相当差的纵横字谜。为了得到更好的结果，我对上面的基本配方做了一些修改。

  • 在生成填字游戏的最后，根据填了多少个单词(越多越好)、板子有多大(越小越好)以及高度和宽度的比例(越接近1越好)给它打分。生成一些填字游戏，然后比较它们的分数，选择最好的一个。
    • 我决定在任意时间内创建尽可能多的填字游戏，而不是运行任意数量的迭代。如果你只有一个很小的单词列表，那么你将在5秒钟内得到几十个可能的填字游戏。一个更大的填字游戏可能只能从5-6种可能性中选择。
  • 当放置一个新单词时，不要在找到一个可以接受的位置后立即放置，而是根据单词位置增加了多少网格大小和有多少交叉点来给它打分(理想情况下，你希望每个单词被2-3个其他单词交叉)。跟踪所有的位置和他们的分数，然后选择最好的一个。
小开

为什么不从随机概率的方法开始呢。从一个单词开始，然后反复选择一个随机的单词，并试图在不打破大小限制的情况下将它放入当前的拼图状态等等。如果你失败了，就从头再来。

您会惊讶于蒙特卡罗方法这样的工作频率。

小开

我最近刚用 Python 写了自己的代码。你可以在这里找到它: http://bryanhelmig.com/python-crossword-puzzle-generator/。它没有创建密集的纽约时报风格的填字游戏，但风格的填字游戏，你可能会发现在一个儿童的益智书。

与我发现的一些算法不同，这些算法实现了一种随机的蛮力方法来放置单词，就像一些人建议的那样，我试图在单词放置方面实现一种稍微聪明一点的蛮力方法。我的流程是这样的:

  1. 创建一个任意大小的网格和一个单词列表。
  2. 对单词列表进行洗牌，然后将单词从最长到最短进行排序。
  3. 将第一个和最长的单词放在最左上角的位置，1,1(垂直或水平)。
  4. 移动到下一个单词，循环遍历单词中的每个字母和网格中的每个单元格，寻找字母对字母的匹配。
  5. 找到匹配项后，只需将该位置添加到该单词的建议坐标列表中。
  6. 循环遍历建议的坐标列表，并根据所跨越的其他单词的数量对单词的位置进行“打分”。得分为0表示放置不当(与现有单词相邻)或没有单词交叉。
  7. 回到步骤 # 4，直到单词列表用完。可选第二遍。
  8. 我们现在应该有一个填字游戏，但质量可以打或错过由于一些随机的位置。因此，我们缓冲这个填字游戏，回到步骤2。如果下一个填字游戏在黑板上放置了更多的单词，它将替换缓冲区中的填字游戏。这是有时间限制的(在 x 秒内找到最好的填字游戏)。

到最后，你有一个体面的纵横字谜或单词搜索难题，因为他们是大约相同的。它往往运行得相当好，但让我知道，如果你有任何改进的建议。更大的网格运行速度呈指数级减慢; 更大的单词列表是线性的。更大的单词列表也有更高的机会获得更好的单词位置编号。

小开

我一直在想这个问题。我的感觉是，要创建一个真正密集的填字游戏，你不能指望你有限的单词列表将是足够的。因此，您可能需要使用一个 dictionary 并将其放入一个“ trie”数据结构中。这将使您能够轻松地找到填充剩余空格的单词。在一个 try 中，实现一个遍历是相当有效的，例如，给出所有形式为“ c? t”的单词。

所以，我的总体想法是: 创建一些相对蛮力的方法，就像这里描述的一样，来创建一个低密度的十字，然后用字典单词来填充空格。

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

小开

此算法在60秒内创建50个密度为6x9的 箭头填字游戏。它使用一个 word 数据库(包含 word + 技巧)和一个主板数据库(包含预先配置的主板)。

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)
小开

下面是一些基于 nickf 的答案和 Bryan 的 Python 代码的 JavaScript 代码。只是发布一下，以防有人需要。

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();
}
小开

虽然这是一个较老的问题，将尝试基于类似的工作，我已经做了一个答案。

解决约束问题的方法有很多(一般在 NPC 复杂性类中)。

这与组合优化和约束编程有关。在这种情况下，约束是网格的几何形状和单词是唯一的要求等。.

随机/退火方法也可以工作(尽管在适当的设置内)。

高效的简单可能就是终极智慧！

需求是一个或多或少完整的纵横字谜编译器和(可视化所见即所得)构建器。

撇开所见即所得的构建器部分不谈，编译器大纲是这样的:

  1. 加载可用的单词列表(按单词长度排序，如2、3、 . . 、20)

  2. 在用户构建的网格中找到单词槽(即网格单词)(例如长度为 L 的单词 x，y，水平或垂直)(复杂度 O (N))

  3. 计算网格单词(需要填充的)的交点(复杂度 O (N ^ 2))

  4. 计算单词列表中的单词与使用的字母表中的各种字母的交集(这允许使用模板例如搜索匹配的单词)。(复杂度 O (WL * AL))

步骤3和步骤4允许完成这项任务:

一。网格单词与它们自身的交集能够创建一个“模板”，用于尝试在这个网格单词的相关可用单词列表中找到匹配(通过使用其他与这个单词相交的单词的字母，这些单词已经在算法的某个步骤中被填充)

B.单词列表中的单词与字母表的交叉点能够找到匹配的(候选)单词，匹配给定的“模板”(例如“ A”在第一位，“ B”在第三位等)

所以这些数据结构的实现算法是这样的:

注意: 如果网格和单词数据库是常数，前面的步骤可以只做一次。

  1. 该算法的第一步是随机选择一个空单词槽(网格单词) ，并从相关的单词列表中选择一个候选单词填充它(随机化能够在算法的连续执行中产生不同的解决方案)(复杂度 O (1)或 O (N))

  2. 对于每个仍然空的单词槽(与已经填充的单词槽有交集的单词槽) ，计算一个约束比率(这可以变化，简单的是该步骤中可用解决方案的数量) ，并按照这个比率(复杂度 O (NlogN)或 O (N))对空的单词槽进行排序

  3. 循环通过前一步计算的空单词槽，并对每一个单词尝试一些补充解决方案(确保“弧一致性被保留”，即网格有一个解决方案在这一步之后，如果使用这个单词) ，并根据下一步的最大可用性对它们进行排序(即下一步有一个最大可能的解决方案，如果这个单词在那个时间在那个地方使用，等等)(复杂度 O (N * MaxCandidatesused))

  4. 填充这个单词(将其标记为已填充，然后转到步骤2)

  5. 如果没有找到满足步骤标准的单词。3尝试回溯到前一步骤的另一个候选解决方案(标准在这里可以有所不同)(复杂度 O (N))

  6. 如果找到回溯，使用替代方法并可选地重新设置任何可能需要重新设置的已填充单词(将它们再次标记为未填充单词)(复杂度 O (N))

  7. 如果没有找到回溯，那么就不能找到解决方案(至少使用这个配置、初始种子等)

  8. 否则，当所有的单词都被填满时，你只有一个解决办法

该算法对问题的解树进行随机一致的遍历。如果在某个点有一个死胡同，它会回溯到前一个节点，然后沿着另一条路线前进。直到找到一个解决方案或者各个节点的候选节点的数量耗尽为止。

一致性部分确保找到的解决方案确实是一个解决方案，而随机性部分能够在不同的执行中产生不同的解决方案，并且平均而言具有更好的性能。

所有这些(以及其他)都是在纯 JavaScript (具有并行处理和所见即所得)功能中实现的

该算法可以很容易地并行化，以便同时产生多个(不同的)解决方案

希望这个能帮上忙

小开

我在玩填字游戏发生器引擎，我发现最重要的是:

0

  1. A

    使一些项目/对象，如光标，将周围的矩阵方向容易定位 除非您希望以后通过随机选择进行迭代

  2. 第一步，拿起第一对，从0,0开始横向放置; 将第一个存储为我们当前的填字游戏“领导者”

  3. 按顺序对角或随机移动光标的对角概率更大的下一个空单元格

  4. 迭代像这样的单词并使用自由空间长度来定义最大单词长度: 温度 = [] 对于范围内的 w _ size (len (w _ space) ，2，-1) : # T 如果 len (word) = = w _ size ] : # 如果 w 不在 temp 中并且 putTheWord (w，w _ space) : # Append (w)

  5. 比较词语和我使用的自由空间，例如:

    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

  6. 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 :

# CHANGE ALL WORDS LIST inexOf1stWord = allwords.index( leading_w ) allwords = allwords[:inexOf1stWord+1][:] + allwords[inexOf1stWord+1:][:]

...and iterate again new crossword.

  1. Make the scoring system by easiness of filling, and some estimation calcs. Give score for the current crossword and narrow later choice by append it into list of made crosswords if the score is satisfied by your scoring system.

  2. After first iteration session iterate again from the list of made crosswords to finish the job.

By using more parameters speed can be improved by a huge factor.

小开

jQuery Crossword Puzzle Generator and Game

我已经为这个问题编写了一个 JavaScript/jQuery 解决方案:

样本演示: http://www.earthfluent.com/crossword-puzzle-demo.html

源代码: https://github.com/HoldOffHunger/jquery-crossword-puzzle-generator

我使用的算法的目的是:

  1. 尽可能减少网格中无法使用的正方形的数量。
  2. 有尽可能多的混合词。
  3. 以极快的速度进行计算。

Demonstration of a generated crossword puzzle.

我将描述我使用的算法:

  1. 根据共同的字母将单词组合在一起。

  2. 从这些组中构建新数据结构(“单词块”)的集合，这是一个主要单词(贯穿所有其他单词) ，然后是其他单词(贯穿主要单词)。

  3. 在填字游戏的最左上角位置用这些单词块中的第一个单词开始填字游戏。

  4. 对于单词块的其余部分，从纵横字谜的最右下角开始，向上和向左移动，直到没有可填充的空格为止。如果向上的空列多于向左的空列，则向上移动，反之亦然。

小开

这一个作为一个项目出现在 人工智能 CS50课程从哈佛。我们的想法是把填字游戏的生成问题作为一个约束补偿问题，然后用不同的启发式回溯来解决它，从而减少搜索空间。

首先，我们需要几个输入文件:

  1. 纵横字谜的结构(看起来像下面这个，例如，‘ #’表示不要填充的字符，‘ _’表示要填充的字符)

`

###_####_#
____####_#
_##_#_____
_##_#_##_#
______####
#_###_####
#_##______
#_###_##_#
_____###_#
#_######_#
##_______#

`

  1. 一个输入词汇表(单词列表/词典) ，从中选择候选单词(如下所示)。

    一 放弃 能力 有能力 堕胎 关于 以上 在国外 缺席 绝对的 当然 ...

现在，CSP 的定义和解决办法如下:

  1. 变量被定义为具有作为输入提供的单词(词汇表)列表中的值(即它们的域)。
  2. 每个变量都由一个3元组来表示: (grid _ location，direct，length)其中坐标表示对应单词的开头，方向可以是水平的也可以是垂直的，长度被定义为变量将被赋予的单词的长度。
  3. 约束由提供的结构输入定义: 例如，如果水平变量和垂直变量具有公共字符，则它将表示为重叠(圆弧)约束。
  4. 现在，节点一致性算法和 AC3弧一致性算法可以用来降低域的大小。
  5. 然后回溯得到一个解决方案(如果存在的话)与 MRV (最小剩余值) ，度等启发式可以用来选择下一个未分配的变量和像 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█

`

下面的动画显示了回溯步骤:

enter image description here

下面是另一个孟加拉语单词列表:

enter image description here


提交答案