给定一个单词列表,您将如何将它们排列到纵横填字游戏网格中?
它不需要像一个对称的“适当的”字谜游戏或任何类似的东西:基本上只需要输出每个单词的起始位置和方向。
发布于 2009-06-20 15:07:59
为什么不从随机概率的方法开始呢?从一个单词开始,然后重复选择一个随机单词,并尝试在不打破大小等限制的情况下使其适合当前的拼图状态。如果你失败了,就重新开始。
你会惊讶于像这样的蒙特卡洛方法是多么的有效。
发布于 2014-03-08 01:04:32
下面是一些基于尼克夫的答案和布莱恩的JavaScript代码的Python代码。只是在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();
}
发布于 2009-06-03 05:26:02
我会生成两个数字:长度和拼写分数。假设拼写分数低意味着更容易加入(低分数=大量常见字母)。按长度降序和拼写分数升序对列表进行排序。
接下来,从列表中往下看。如果单词没有与现有单词交叉(分别根据每个单词的长度和拼写分数检查每个单词),则将其放入队列中,并检查下一个单词。
冲洗并重复,这应该会生成一个纵横字谜。
当然,我非常确定这是O(n!)它不能保证为你完成纵横字谜,但也许有人可以改进它。
https://stackoverflow.com/questions/943113
复制相似问题