nic*_*ckf 115 language-agnostic algorithm crossword
给出一个单词列表,你会如何安排他们进入填字游戏网格？
它不一定像对称的"正确的"填字游戏或类似的东西:基本上只输出每个单词的起始位置和方向.
是否有可用的Java示例？
nic*_*ckf 53
我提出了一个可能不是最有效的解决方案,但它运作良好.基本上:
这使得填字游戏变得有效,但往往很差.我对上面的基本配方进行了一些改动,以获得更好的结果.
Bry*_*yan 19
我最近刚用Python写了自己的.你可以在这里找到它:http://bryanhelmig.com/python-crossword-puzzle-generator/.它不会创建密集的NYT风格填字游戏,而是您可能在儿童拼图书中找到的填字游戏风格.
不同于我发现的一些算法实现了一种随意暴力方法来放置像一些人所建议的单词,我尝试在单词放置时实现一种稍微聪明的暴力方法.这是我的过程:
到最后,你有一个像样的填字游戏或单词搜索拼图,因为它们大致相同.它往往运行得相当好,但如果您对改进有任何建议,请告诉我.更大的网格以指数速度增长; 更大的单词线性列出.较大的单词列表在更好的单词放置数字上也有更高的机会.
pax*_*blo 18
实际上,我在大约十年前写了一个填字游戏生成程序(它很神秘,但同样的规则适用于普通的填字游戏).
它有一个单词列表(和相关的线索)存储在一个文件中,按日期的降序使用排序(因此较少使用的单词位于文件的顶部).从客户端提供的池中随机选择模板,基本上是表示黑色和自由方块的位掩码.
然后,对于拼图中的每个非完整单词(基本上找到第一个空白正方形,看看右边的那个(跨单词)还是下面的单词(向下单词)也是空白的),搜索完成了该文件寻找适合的第一个单词,考虑到该单词中已有的字母.如果没有适合的单词,您只需将整个单词标记为不完整并继续前进.
最后会有一些未完成的单词,编译器必须填写这些单词(如果需要,可以在文件中添加单词和线索).如果他们无法提出任何想法,他们可以手动编辑填字游戏以更改约束或只是要求完全重新生成.
一旦单词/线索文件达到一定的大小(并且它每天为该客户端添加50-100条线索),很少有一个案例需要为每个填字游戏完成两到三次手动修复.
thi*_*olr 14
该算法在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
提示[line,column]:
[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)
Nik*_* M. 10
虽然这是一个较老的问题,但会根据我所做的类似工作尝试回答.
有许多解决约束问题的方法(通用在NPC复杂性类中).
这与组合优化和约束编程有关.在这种情况下,约束是网格的几何形状和单词是唯一的要求等.
随机化/退火方法也可以起作用(尽管在适当的环境中).
高效的简约可能只是最终的智慧!
这些要求适用于或多或少完整的填字游戏编译器和(可视WYSIWYG)构建器.
暂且不谈WYSIWYG构建器部分,编译器大纲如下:
加载可用的单词表(按字长排序,即2,3,..,20)
在用户构造的网格上找到wordslots(即网格词)(例如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))
循环通过在前一步计算出的空单词,并为每一个尝试一些cancdidate解决方案(确保"保持弧的一致性",即如果使用该单词,则在此步骤之后网格有解决方案)并根据下一步的最大可用性(即如果在那个地方当时使用该词,则下一步有最大可能的解决方案等).(复杂度O(N*MaxCandidatesUsed))
填写该单词(将其标记为已填写并转到第2步)
如果没有找到满足步骤.3标准的单词,请尝试回溯到前一步骤的另一个候选解决方案(标准可能会有所不同)(复杂度O(N))
如果找到了回溯,请使用替代方案并可选地重置任何可能需要重置的已填充单词(将其标记为未填充)(复杂度O(N))
如果没有找到回溯,则找不到解决方案(至少使用此配置,初始种子等...)
此外,当所有的字槽都填满时,你有一个解决方案
该算法对问题的解决方案树进行随机一致行走.如果在某个时刻有一个死胡同,它会对前一个节点做一个回溯并跟随另一个路径.直到找到的解决方案或各个节点的候选者数量都已用尽.
一致性部分确保找到的解决方案确实是一种解决方案,并且随机部分能够在不同的执行中生成不同的解决方案,并且平均而言具有更好的性能.
PS.所有这些(以及其他)都是用纯JavaScript(具有并行处理和WYSIWYG)功能实现的
PS2.该算法可以很容易地并行化,以便同时产生多个(不同的)解决方案
希望这可以帮助
为什么不使用随机概率方法开始.从一个单词开始,然后重复选择一个随机单词,并尝试将其放入拼图的当前状态,而不会破坏对大小等的约束.如果失败,只需重新开始.
你会惊讶地发现像这样的蒙特卡洛方法有效.
这里有一些基于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();
}
我会生成两个数字:长度和拼字游戏得分.假设一个低Scrabble分数意味着它更容易加入(低分=很多普通字母).按长度递减排序列表,Scrabble得分递增.
接下来,就在列表中.如果单词不与现有单词交叉(分别按长度和Scrabble分数检查每个单词),则将其放入队列,然后检查下一个单词.
冲洗并重复,这应该生成填字游戏.
当然,我很确定这是O(n!)并且不能保证为你完成填字游戏,但也许有人可以改进它.