algorithm来生成一个填字游戏

给出一个单词列表，你将如何去安排他们到填字游戏网格？

它不必像是一个对称或类似的“适当的”纵横字谜：基本上只是输出每个单词的起始位置和方向。

会有Java的例子吗？

我想出了一个解决scheme，可能不是最有效的，但它工作得很好。基本上：

将所有单词按长度sorting，降序排列。
把第一个字放在板子上。
接下来的单词。
search板上已经存在的所有单词，看看这个单词是否有任何可能的交点（任何常见的字母）。
如果这个单词有一个可能的位置，则遍历棋盘上的所有单词，并检查新单词是否干扰。
如果这个单词没有打破棋盘，那么把它放在那里，然后转到步骤3，否则，继续search一个地方（步骤4）。
继续这个循环，直到所有单词被放置或无法放置。

这使得一个工作，但往往很差的填字游戏。我对上面的基本配方进行了一些改动，以得到更好的结果。

在产生一个填字游戏的结尾，给它一个基于有多less单词放在一个分数（越多越好），董事会有多大（越小越好），以及高度和宽度之间的比例到1更好）。生成一些填字游戏，然后比较他们的分数，并select最好的一个。
- 我决定在任意时间内创build尽可能多的填字游戏，而不是运行任意数量的迭代。如果你只有一个小的单词列表，那么你会在5秒内得到几十个可能的填字游戏。更大的填字游戏只能从5-6种可能性中select。
当放置一个新的单词时，不要在find可接受的位置时立即放置它，而要根据它增加网格的大小和多less个交点的数量给这个单词的位置（理想情况下，您希望每个单词都是穿过2-3个其他词）。跟踪所有的位置和他们的分数，然后select最好的一个。

我刚刚写了我自己的Python。你可以在这里find它： http : //bryanhelmig.com/python-crossword-puzzle-generator/ 。它不会产生密集的纽约时报风格的填字游戏，而是可能在孩子的益智书中find的填字游戏的风格。

与我发现的几个algorithm不同的是，这里实现了一个随机的蛮力方法来放置像这样的单词，我试图在单词放置上实施一个更聪明的蛮力方法。这是我的过程：

创build一个任意大小和单词列表的网格。
随机抽出单词列表，然后按照最长到最短的顺序排列单词。
将第一个和最长的单词放在最左上angular的1,1（垂直或水平）。
移到下一个单词上，循环单词中的每个字母，并在网格中的每个单元格寻找字母匹配的字母。
当find匹配的时候，只需将该位置添加到该单词的build议坐标列表中即可。
在build议的坐标列表上循环，并根据它所穿过的多less其他单词对单词放置进行“评分”。 0的分数表示不合格放置（与现有词语相邻）或者没有词汇交叉。
回到步骤＃4，直到词表被用尽。可选的第二遍。
我们现在应该有一个填字游戏，但由于一些随机的安排，质量可能会被打或失。所以，我们缓冲这个填字游戏并返回到步骤＃2。如果下一个填字词在单板上放置了更多单词，它将replace缓冲区中的填字。这是时间有限（在x秒内find最好的填字游戏）。

到最后，你有一个体面的纵横字谜或单词search难题，因为它们大致相同。它往往运行得相当好，但让我知道，如果你有任何改善的build议。更大的网格运行速度指数更慢; 更大的单词线性列出。更大的单词列表在更好的单词放置数字上也具有更高的可能性。

我实际上是在十年前编写了一个字谜生成程序（这是一个神秘的，但同样的规则将适用于正常的填字游戏）。

它有一个单词列表（和相关的线索）存储在一个文件中按照递减的用法进行sorting（以便文件的顶部使用的是较less使用的单词）。一个模板，基本上是一个代表黑色和自由方块的位掩码，是从客户端提供的池中随机select的。

然后，对于拼图中的每个非完整单词（基本上find第一个空白方块，看看右边的一个（跨词）还是下面的（下面的词）也是空白的），search该文件寻找适合的第一个单词，考虑到该单词中已有的字母。如果没有合适的词汇，你只是将整个词汇标记为不完整，然后继续前进。

最后会有一些不完整的单词，编译器将不得不填写（如果需要的话，添加单词和线索到文件中）。如果他们不能提出任何想法，他们可以手动编辑填字游戏来改变约束，或只是要求重新生成。

一旦单词/线索文件达到一定的大小（每天为这个客户端添加50到100条线索），很less有两个或三个以上的手动修复工作必须为每个填字游戏完成。

该algorithm在60秒内创build50个密集的6×9 箭头纵横字谜。它使用一个字数据库（带有word +提示）和一个电路板数据库（带有预configuration的电路板）。

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

一个更大的字数据库大大减less了世代的时间，一些板很难填补！更大的电路板需要更多时间才能正确填充！

例：

预configuration的6×9电路板：

（＃表示一个单元格中的一个提示，％表示一个单元格中的两个提示，箭头未显示）

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

生成的6×9板：

 # C # # P % # O # SATELLITE # NINES # TA % AB # A # GAS % DENSE % WECATHEDRAL

提示[行，列]：

 [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)

为什么不使用随机概率方法开始。从一个单词开始，然后反复挑选一个随机单词，并尝试将其纳入当前的谜题状态，而不会打破对尺寸的限制等。如果失败，则重新开始。

你会惊奇地发现，像这样的蒙特卡洛方法是多么的经常运作。

虽然这是一个比较老的问题，但是会根据我所做的类似的工作尝试一个答案。

解决约束问题的方法有很多（在NPC复杂等级中是普遍的）。

这与组合优化和约束规划有关。在这种情况下，约束条件是网格的几何形状以及单词的唯一性等。

随机化/退火方法也可以工作（尽pipe在适当的设置下）。

高效简单可能只是最终的智慧！

这些要求是针对一个或多或less的完整填字游戏编译器和（可视所见即所得）构build器。

撇开所见即所得的构build器部分，编译器大纲是这样的：

加载可用的单词列表（按字长sorting，即2,3，…，20）
在用户构造的网格（例如，长度为L，水平或垂直的x，y处的词）（复杂度O（N））上查找词语（即网格词）
计算网格单词（需要填充的）的交点（复杂度为O（N ^ 2））
计算词表中单词与所使用的各种字母的交集（这允许通过使用模板（例如cwc使用的Sik Cambon论文）来search匹配的单词（复杂度O（WL * AL））

步骤.3和.4允许执行此任务：

一个。网格单词与它们自己的交集使得能够创build一个“模板”，用于在该网格单词的可用单词的关联单词表中find匹配（通过使用与该单词相关的其他相交单词的字母，algorithm的一步）

湾单词表中的单词与字母表的交集使得能够find匹配给定“模板”的匹配（候选）单词（例如，第一位的“A”和第三位的“B”）。

所以在这些数据结构中，所使用的algorithm就是这样的：

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

algorithm的第一步是随机select一个空字槽（网格字），并用相关单词表中的候选字填充（随机化使得在algorithm的连续执行中产生不同的解）（复杂度O（1）或O（ N））
对于每个仍然是空的单词槽（与已经填充的单词槽有交集），计算一个约束比率（这可以是不同的，简单的是在该步骤可用的解决scheme的数量），并按照这个比例（复杂性O（NlogN ）或O（N））
循环遍历在上一步计算出的空字段，并为每一个尝试一些cancdidate解决scheme（确保“弧一致性保留”，即网格有一个解决scheme后，如果使用这个词的这一步），并根据下一步的最大可用性（即，如果在那个地方当时使用这个词，则下一步有最大可能的解决scheme，等等。）（复杂度O（N * MaxCandidatesUsed））
填写该字（标记为已填写并转到步骤2）
如果找不到满足步骤.3的标准的词，则尝试回溯到前一步的另一个候选解（标准可以在此变化）（复杂度O（N））
如果find了回溯，则使用替代方法，并可选地重置任何已经填充的可能需要重置的单词（将它们标记为未填充）（复杂度为O（N））
如果没有find回溯，可以find没有解决scheme（至less在这个configuration，初始种子等..）
否则，当所有的单词填满你有一个解决scheme

该algorithm对问题的解树进行随机一致行走。如果在某一时刻有一个死胡同，它会回溯到前一个节点，并沿着另一条路线前进。直到find的解决scheme或者各个节点的候选人数量都用尽。

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

PS。所有这些（和其他）都是用纯JavaScript（具有并行处理和所见即所得）function来实现的

PS2。该algorithm可以很容易地并行化，以便同时生成多个（不同的）解决scheme

希望这可以帮助

我会生成两个数字：长度和拼字比分。假设低拼字比分意味着join比较容易（低分=大量普通字母）。按长度降序排列列表，拼字比例按升序排列。

接下来，就在列表中。如果单词不与现有单词交叉（分别按照长度和拼字比分检查每个单词），然后将其放入队列中，并检查下一个单词。

冲洗并重复，这应该产生一个填字游戏。

当然，我很确定这是O（n！），并不能保证为你完成填字游戏，但也许有人可以改进它。

这里是一些基于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(); }

我正在玩填字游戏发动机引擎，我发现这是最重要的：

0 !/usr/bin/python

一个。 allwords.sort(key=len, reverse=True)

湾做一些像光标一样的项目/对象，这些项目/对象将围绕matrix走动，以方便定位，除非你想随后的随机select迭代。
第一，拿起第一对，并从0,0上下放置它们; 存储第一个作为我们目前填字游戏的“领导者”。
将光标按对angular线顺序移动或以更大的对angular线概率随机移动到下一个空白单元格
迭代单词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:][:]

…并重新迭代新的填字游戏。

通过填充容易进行评分系统，并进行一些估计。如果得分系统满足得分，则为当前填字游戏提供分数，并缩小后面的选项。
在第一次迭代之后，再次从制作的填字游戏列表中完成作业。

通过使用更多的参数，速度可以被一个巨大的因素改善。

我会得到每个字使用的每个字母的索引，以了解可能的十字架。然后，我会select最大的单词，并将其用作基础。 select下一个大的交叉。冲洗并重复。这可能是一个NP问题。

另一个想法是创build一个遗传algorithm，其中的强度度量是您可以在网格中放置多less个单词。

我发现的难点是什么时候知道某个列表不可能被跨越。

我一直在想这个问题。我的感觉是，要创造一个真正密集的填字游戏，你不能希望你的有限的单词列表就足够了。因此，您可能需要将字典放入“trie”数据结构中。这将使您可以轻松find填满左侧空格的单词。在一个方法中，实现一个遍历就是相当高效的，比如说，给你所有的forms“c？t”的话。

所以，我的总体思路是：创build一些比较暴力的方法，就像在这里描述的那样，创build一个低密度的十字架，用词典填充空格。

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

下面是一些基于Bryan的python代码的纵横字谜生成器。

只是在有人需要的情况下分享。