与えられた単語のリストをクロスワード グリッドに配置するにはどうすればよいでしょうか?
対称的な「適切な」クロスワード パズルのようなものである必要はありません。基本的には、各単語の開始位置と方向を出力するだけです。
95117 次
13 に答える
24
私は最近、Pythonで自分自身を書きました。ここで見つけることができます: http://bryanhelmig.com/python-crossword-puzzle-generator/。密度の高い NYT スタイルのクロスワードではなく、子供向けのパズルの本に見られるようなクロスワードのスタイルを作成します。
私が見つけたいくつかのアルゴリズムとは異なり、いくつかのアルゴリズムが提案したように単語をランダムに配置する総当り法を実装していましたが、私は単語の配置で少し賢い総当り法を実装しようとしました。これが私のプロセスです：
- 任意のサイズのグリッドと単語のリストを作成します。
- 単語リストをシャッフルし、単語を長い順に並べ替えます。
- 最初で最も長い単語を左上端の位置 1,1 (垂直または水平) に配置します。
- 次の単語に移動し、単語内の各文字とグリッド内の各セルをループして、文字と文字の一致を探します。
- 一致が見つかったら、その位置をその単語の提案された座標リストに追加するだけです。
- 提案された座標リストをループし、交差する他の単語の数に基づいて単語の配置を「スコア付け」します。スコア 0 は、配置が悪い (既存の単語に隣接している) か、単語のクロスがないことを示します。
- 単語リストが使い果たされるまで、ステップ #4 に戻ります。オプションの 2 番目のパス。
- これでクロスワードができたはずですが、ランダムな配置がいくつかあるため、品質に問題が生じる可能性があります。したがって、このクロスワードをバッファリングして、ステップ 2 に戻ります。次のクロスワードがボード上に配置された単語をさらに持っている場合、バッファー内のクロスワードが置き換えられます。これは時間制限があります (x 秒で最高のクロスワードを見つけてください)。
最終的には、ほぼ同じなので、まともなクロスワード パズルまたは単語検索パズルが完成します。かなりうまくいく傾向がありますが、改善に関する提案があれば教えてください。より大きなグリッドは指数関数的に遅くなります。より大きな単語リストが直線的に表示されます。単語リストが大きいほど、単語の配置数が増える可能性も高くなります。
于 2010-04-11T18:41:16.883 に答える
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 ボード:
(# は 1 つのセルに 1 つのヒントを意味し、% は 1 つのセルに 2 つのヒントを意味し、矢印は表示されていません)
# - # # - % # - #
- - - - - - - - -
# - - - - - # - -
% - - # - # - - -
% - - - - - % - -
- - - - - - - - -
生成された 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 の複雑さのクラスにあります)。
これは、組み合わせ最適化と制約プログラミングに関連しています。この場合、制約はグリッドのジオメトリと、単語が一意であるという要件などです。
ランダム化/アニーリング アプローチも機能します (適切な設定の範囲内ではありますが)。
効率的なシンプルさは究極の知恵かもしれません!
必要条件は、多かれ少なかれ完全なクロスワード コンパイラと (ビジュアル WYSIWYG) ビルダーでした。
WYSIWYG ビルダーの部分は別として、コンパイラの概要は次のとおりです。
利用可能な単語リストをロードします (単語の長さでソートされます。つまり、2,3,..,20)
ユーザーが構築したグリッド上の単語スロット (つまり、グリッド単語) を見つけます (例: x,y で長さ L、水平または垂直の単語) (複雑さ O(N) )
グリッド ワード (埋める必要がある) の交点を計算します (複雑さ O(N^2) )
使用されているアルファベットのさまざまな文字を使用して、単語リスト内の単語の共通部分を計算します (これにより、テンプレートを使用して一致する単語を検索できます。たとえば、cwc で使用されている Sik Cambon 論文) (複雑さ O(WL*AL) )
ステップ .3 および .4 で、このタスクを実行できます。
を。グリッド単語とそれ自体の交差により、このグリッド単語に使用可能な単語の関連する単語リストで一致を見つけようとするための「テンプレート」を作成できます (特定の時点で既に埋められているこの単語と他の交差する単語の文字を使用することにより)。アルゴリズムのステップ)
b. 単語リスト内の単語とアルファベットの共通部分により、特定の「テンプレート」に一致する一致する (候補) 単語を見つけることができます (たとえば、「A」が 1 位、「B」が 3 位など)。
したがって、これらのデータ構造を実装すると、使用されるアルゴリズムは次のようになります。
注: 単語のグリッドとデータベースが一定である場合、前の手順は 1 回だけ実行できます。
アルゴリズムの最初のステップは、空の単語スロット (グリッド単語) を無作為に選択し、関連する単語リストから候補単語を入力することです (ランダム化により、アルゴリズムの連続実行で異なる解を生成できます) (複雑さ O(1) または O( N) )
まだ空の単語スロット (既に満たされた単語スロットとの共通部分がある) ごとに、制約比率 (これは変化する可能性があります。単純なのは、そのステップで使用可能なソリューションの数です) を計算し、この比率で空の単語スロットを並べ替えます (複雑さ O(NlogN ) または O(N) )
前のステップで計算された空の単語スロットをループし、それぞれについていくつかの候補解を試します (「弧の一貫性が保持されている」ことを確認します。つまり、この単語が使用されている場合、このステップの後にグリッドに解があります)。次のステップの最大可用性 (つまり、この単語がその時点でその場所で使用されている場合、次のステップには可能な最大の解決策があるなど) (複雑さ O(N*MaxCandidatesUsed) )
その単語を入力します (入力済みとしてマークし、ステップ 2 に進みます)
ステップ .3 の基準を満たす単語が見つからない場合は、前のステップの別の候補解に戻ります (基準はここで変わる可能性があります) (複雑さ O(N) )
バックトラックが見つかった場合は、代替手段を使用し、必要に応じて、リセットが必要な可能性のある既に埋められている単語をリセットします (再び埋められていないものとしてマークします) (複雑さ O(N) )
バックトラックが見つからない場合、解決策は見つかりません (少なくともこの構成、初期シードなどでは..)
それ以外の場合、すべてのワードロットがいっぱいになると、1 つの解決策があります
このアルゴリズムは、問題の解ツリーのランダムな一貫したウォークを行います。ある時点で行き止まりになった場合は、前のノードに戻り、別のルートをたどります。解決策が見つかるか、さまざまなノードの候補がなくなるまで。
一貫性部分は、見つかったソリューションが実際にソリューションであることを確認し、ランダム部分は、さまざまな実行でさまざまなソリューションを生成し、平均してパフォーマンスを向上させることを可能にします。
PS。これらすべて (およびその他) は、純粋な JavaScript (並列処理と WYSIWYG を使用) 機能で実装されました。
PS2。アルゴリズムは、同時に複数の (異なる) ソリューションを生成するために簡単に並列化できます。
お役に立てれば
于 2014-05-02T19:33:39.723 に答える
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
長さとスクラブルスコアの2つの数値を生成します。スクラブルスコアが低いと、参加しやすいと仮定します（スコアが低い=一般的な文字がたくさんある）。リストを長さの降順とスクラブルスコアの昇順で並べ替えます。
次に、リストを下に移動します。単語が既存の単語と交差しない場合（各単語の長さとスクラブルスコアでそれぞれチェックします）、キューに入れて次の単語をチェックします。
すすぎ、繰り返します。これにより、クロスワードが生成されます。
もちろん、これはO（n！）であり、クロスワードを完成させる保証はありませんが、誰かがそれを改善できる可能性があります。
于 2009-06-03T05:26:01.907 に答える
3
私はこの問題について考えてきました。私の感覚では、真に高密度のクロスワードを作成するには、限られた単語リストで十分になるとは期待できません。したがって、辞書を取得して「試行」データ構造に配置することをお勧めします。これにより、残りのスペースを埋める単語を簡単に見つけることができます。トライでは、たとえば「c？t」の形式のすべての単語を与えるトラバーサルを実装するのはかなり効率的です。
したがって、私の一般的な考え方は、低密度のクロスを作成するためにここで説明するような、ある種の比較的強引なアプローチを作成し、辞書の単語で空白を埋めることです。
他の誰かがこのアプローチを取っているなら、私に知らせてください。
于 2010-09-22T17:34:08.933 に答える