Algoritma untuk menghasilkan teka-teki silang

Diberikan daftar kata, bagaimana Anda akan mengaturnya menjadi kisi teka-teki silang?

Ini tidak harus seperti teka-teki silang yang "tepat" yang simetris atau semacamnya: pada dasarnya hanya menampilkan posisi dan arah awal untuk setiap kata.

Saya menemukan solusi yang mungkin bukan yang paling efisien, tetapi berhasil dengan cukup baik. Pada dasarnya:

1. Urutkan semua kata berdasarkan panjangnya, turun.
2. Ambil kata pertama dan letakkan di papan tulis.
3. Ambil kata berikutnya.
4. Cari semua kata yang sudah ada di papan tulis dan lihat apakah ada kemungkinan persimpangan (huruf umum) dengan kata ini.
5. Jika ada kemungkinan lokasi untuk kata ini, ulangi semua kata yang ada di papan tulis dan periksa untuk melihat apakah kata baru tersebut mengganggu.
6. Jika kata ini tidak merusak papan, letakkan di sana dan lanjutkan ke langkah 3, jika tidak, lanjutkan mencari tempat (langkah 4).
7. Lanjutkan putaran ini sampai semua kata ditempatkan atau tidak dapat ditempatkan.

Ini membuat teka-teki silang yang berhasil, namun seringkali sangat buruk. Ada sejumlah perubahan yang saya lakukan pada resep dasar di atas untuk mendapatkan hasil yang lebih baik.

• Pada akhir pembuatan teka-teki silang, beri skor berdasarkan berapa banyak kata yang ditempatkan (semakin banyak semakin baik), seberapa besar papannya (semakin kecil semakin baik), dan rasio antara tinggi dan lebar (semakin dekat menjadi 1 lebih baik). Hasilkan sejumlah teka-teki silang dan kemudian bandingkan skor mereka dan pilih yang terbaik.
  • Alih-alih menjalankan sejumlah iterasi yang sewenang-wenang, saya telah memutuskan untuk membuat sebanyak mungkin teka-teki silang dalam waktu yang sewenang-wenang. Jika Anda hanya memiliki daftar kata kecil, maka Anda akan mendapatkan lusinan kemungkinan teka-teki silang dalam 5 detik. Teka-teki silang yang lebih besar hanya dapat dipilih dari 5-6 kemungkinan.
• Saat menempatkan kata baru, alih-alih menempatkannya segera setelah menemukan lokasi yang dapat diterima, berikan skor lokasi kata tersebut berdasarkan seberapa besar peningkatan ukuran kisi dan jumlah persimpangan yang ada (idealnya Anda ingin setiap kata menjadi disilangkan dengan 2-3 kata lain). Pantau semua posisi dan skor mereka, lalu pilih yang terbaik.

Saya baru saja menulis sendiri dengan Python. Anda dapat menemukannya di sini: http://bryanhelmig.com/python-crossword-puzzle-generator/ . Itu tidak menciptakan teka-teki silang gaya NYT yang padat, tetapi gaya teka-teki silang yang mungkin Anda temukan di buku teka-teki anak.

Tidak seperti beberapa algoritme yang saya temukan di sana yang menerapkan metode brute-force acak untuk menempatkan kata-kata seperti yang disarankan beberapa, saya mencoba menerapkan pendekatan brute-force yang sedikit lebih cerdas pada penempatan kata. Inilah proses saya:

1. Buat kisi dengan ukuran berapa pun dan daftar kata.
2. Kocok daftar kata, lalu urutkan kata dari terpanjang ke terpendek.
3. Letakkan kata pertama dan terpanjang di posisi paling kiri atas, 1,1 (vertikal atau horizontal).
4. Pindah ke kata berikutnya, ulangi setiap huruf di kata dan setiap sel di kisi mencari kecocokan huruf ke huruf.
5. Saat kecocokan ditemukan, cukup tambahkan posisi itu ke daftar koordinat yang disarankan untuk kata itu.
6. Ulangi daftar koordinat yang disarankan dan "skor" penempatan kata tersebut berdasarkan berapa banyak kata lain yang disilangkan. Skor 0 menunjukkan penempatan yang buruk (berdekatan dengan kata-kata yang ada) atau bahwa tidak ada persilangan kata.
7. Kembali ke langkah # 4 hingga daftar kata habis. Lulus kedua opsional.
8. Kami sekarang harus memiliki teka-teki silang, tetapi kualitasnya bisa mengenai atau meleset karena beberapa penempatan acak. Jadi, kami menyangga teka-teki silang ini dan kembali ke langkah # 2. Jika teka-teki silang berikutnya memiliki lebih banyak kata yang ditempatkan di papan, itu menggantikan teka-teki silang di penyangga. Ini adalah waktu terbatas (temukan teka-teki silang terbaik dalam x detik).

Pada akhirnya, Anda memiliki teka-teki silang atau teka-teki pencarian kata yang bagus, karena keduanya hampir sama. Ini cenderung berjalan cukup baik, tetapi beri tahu saya jika Anda memiliki saran untuk perbaikan. Grid yang lebih besar berjalan lebih lambat secara eksponensial; daftar kata yang lebih besar secara linier. Daftar kata yang lebih besar juga memiliki peluang lebih tinggi pada nomor penempatan kata yang lebih baik.

Saya sebenarnya menulis program pembuatan teka-teki silang sekitar sepuluh tahun yang lalu (itu samar, tetapi aturan yang sama akan berlaku untuk teka-teki silang biasa).

Ini memiliki daftar kata (dan petunjuk terkait) yang disimpan dalam file yang diurutkan berdasarkan penggunaan menurun hingga saat ini (sehingga kata-kata yang jarang digunakan ada di bagian atas file). Sebuah template, pada dasarnya sebuah bit-mask yang merepresentasikan kotak hitam dan gratis, dipilih secara acak dari sebuah pool yang disediakan oleh klien.

Kemudian, untuk setiap kata yang tidak lengkap dalam teka-teki (pada dasarnya temukan kotak kosong pertama dan lihat apakah yang ada di kanan (kata di seberang) atau yang di bawahnya (kata di bawah) juga kosong), pencarian dilakukan dari file mencari kata pertama yang pas, dengan mempertimbangkan huruf yang sudah ada di kata itu. Jika tidak ada kata yang bisa muat, Anda cukup menandai seluruh kata sebagai tidak lengkap dan melanjutkan.

Pada akhirnya akan ada beberapa kata yang belum selesai yang harus diisi oleh kompilator (dan tambahkan kata dan petunjuk ke file jika diinginkan). Jika mereka tidak dapat menemukan ide apa pun , mereka dapat mengedit teka-teki silang secara manual untuk mengubah batasan atau hanya meminta pembuatan ulang total.

Setelah file kata / petunjuk mencapai ukuran tertentu (dan menambahkan 50-100 petunjuk sehari untuk klien ini), jarang ada kasus lebih dari dua atau tiga perbaikan manual yang harus dilakukan untuk setiap teka-teki silang .

Algoritma ini membuat 50 teka-teki silang panah 6x9 dalam 60 detik. Ini menggunakan database kata (dengan kata + tips) dan database papan (dengan papan yang telah dikonfigurasi sebelumnya).

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

Database kata yang lebih besar sangat mengurangi waktu pembuatan dan beberapa jenis papan lebih sulit diisi! Papan yang lebih besar membutuhkan lebih banyak waktu untuk diisi dengan benar!

Contoh:

Papan 6x9 yang Dikonfigurasi Sebelumnya:

(# berarti satu tip dalam satu sel,% berarti dua tip dalam satu sel, panah tidak ditampilkan)

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

Papan 6x9 yang dihasilkan:

# 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 

Kiat [baris, kolom]:

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

Meskipun ini adalah pertanyaan yang lebih lama, akan mencoba menjawab berdasarkan pekerjaan serupa yang telah saya lakukan.

Ada banyak pendekatan untuk memecahkan masalah kendala (yang umumnya ada di kelas kompleksitas NPC).

Ini terkait dengan optimasi kombinatorial dan pemrograman kendala. Dalam hal ini batasannya adalah geometri grid dan persyaratan bahwa kata-kata itu unik, dll.

Pendekatan pengacakan / anil juga dapat berfungsi (meskipun dalam pengaturan yang tepat).

Kesederhanaan yang efisien mungkin saja merupakan kebijaksanaan tertinggi!

Persyaratannya adalah untuk penyusun teka-teki silang yang kurang lebih lengkap dan pembuat (WYSIWYG visual).

Mengesampingkan bagian pembuat WYSIWYG, garis besar kompilernya adalah ini:

1. Muat daftar kata yang tersedia (diurutkan berdasarkan panjang kata, yaitu 2,3, .., 20)

2. Temukan wordlots (yaitu kata grid) pada grid yang dibuat pengguna (misalnya kata pada x, y dengan panjang L, horizontal atau vertikal) (kompleksitas O (N))

3. Hitung titik potong dari kata-kata grid (yang perlu diisi) (kompleksitas O (N ^ 2))

4. Hitung perpotongan kata-kata dalam daftar kata dengan berbagai huruf alfabet yang digunakan (ini memungkinkan untuk mencari kata yang cocok dengan menggunakan templat misalnya tesis Sik Cambon seperti yang digunakan oleh cwc ) (kompleksitas O (WL * AL))

Langkah .3 dan .4 memungkinkan untuk melakukan tugas ini:

Sebuah. Perpotongan kata kisi dengan dirinya sendiri memungkinkan untuk membuat "templat" untuk mencoba menemukan kecocokan dalam daftar kata terkait dari kata yang tersedia untuk kata kisi ini (dengan menggunakan huruf dari kata berpotongan lain dengan kata ini yang sudah diisi pada langkah algoritma)

b. Perpotongan kata-kata dalam daftar kata dengan alfabet memungkinkan untuk menemukan kata yang cocok (kandidat) yang cocok dengan "template" yang diberikan (misalnya, 'A' di tempat pertama dan 'B' di tempat ke-3, dll.)

Jadi dengan struktur data ini diimplementasikan, algoritma yang digunakan adalah seperti ini:

CATATAN: jika grid dan database kata konstan, langkah sebelumnya hanya dapat dilakukan satu kali.

1. Langkah pertama dari algoritme adalah memilih celah kata kosong (kata kisi) secara acak dan mengisinya dengan kata kandidat dari daftar kata yang terkait (pengacakan memungkinkan untuk menghasilkan soluton yang berbeda dalam eksekusi algoritme yang berurutan) (kompleksitas O (1) atau O ( N))

2. Untuk setiap slot kata yang masih kosong (yang memiliki persimpangan dengan slot kata yang sudah terisi), hitung rasio batasan (ini dapat bervariasi, sth simple adalah jumlah solusi yang tersedia pada langkah tersebut) dan urutkan wordlots kosong dengan rasio ini (kompleksitas O (NlogN) ) atau O (N))

3. Ulangi kata-kata kosong yang dihitung pada langkah sebelumnya dan untuk masing-masing coba sejumlah solusi cancdidate (pastikan bahwa "konsistensi busur dipertahankan", yaitu kisi memiliki solusi setelah langkah ini jika kata ini digunakan) dan urutkan menurut ketersediaan maksimum untuk langkah berikutnya (yaitu, langkah selanjutnya memiliki solusi maksimum yang mungkin jika kata ini digunakan pada saat itu di tempat itu, dll ..) (kompleksitas O (N * MaxCandidatesUsed))

4. Isi kata itu (tandai sebagai terisi dan lanjutkan ke langkah 2)

5. Jika tidak ditemukan kata yang memenuhi kriteria pada langkah .3 coba mundur ke solusi kandidat lain dari beberapa langkah sebelumnya (kriteria dapat bervariasi di sini) (kompleksitas O (N))

6. Jika jejak mundur ditemukan, gunakan alternatif dan secara opsional setel ulang kata-kata yang sudah terisi yang mungkin perlu diatur ulang (tandai sebagai tidak terisi lagi) (kompleksitas O (N))

7. Jika tidak ada backtrack yang ditemukan, tidak ada solusi yang dapat ditemukan (setidaknya dengan konfigurasi ini, seed awal, dll ..)

8. Lain ketika semua slot kata terisi, Anda memiliki satu solusi

Algoritme ini melakukan jalan konsisten acak dari pohon solusi masalah. Jika di beberapa titik ada jalan buntu, ia melakukan backtrack ke node sebelumnya dan mengikuti rute lain. Hingga solusi yang ditemukan atau jumlah kandidat untuk berbagai node habis.

Bagian konsistensi memastikan bahwa solusi yang ditemukan memang merupakan solusi dan bagian acak memungkinkan untuk menghasilkan solusi yang berbeda dalam eksekusi yang berbeda dan juga rata-rata memiliki performa yang lebih baik.

PS. semua ini (dan lainnya) diimplementasikan dalam JavaScript murni (dengan pemrosesan paralel dan kemampuan WYSIWYG)

PS2. Algoritme dapat dengan mudah diparalelkan untuk menghasilkan lebih dari satu solusi (berbeda) pada saat yang bersamaan

Semoga ini membantu

Mengapa tidak hanya menggunakan pendekatan probabilistik acak untuk memulai. Mulailah dengan sebuah kata, lalu berulang kali memilih kata acak dan mencoba menyesuaikannya dengan status teka-teki saat ini tanpa melanggar batasan ukuran, dll. Jika Anda gagal, mulai dari awal lagi.

Anda akan terkejut betapa sering pendekatan Monte Carlo seperti ini berhasil.

Berikut adalah beberapa kode JavaScript berdasarkan jawaban nickf dan kode Python Bryan. Hanya mempostingnya jika orang lain membutuhkannya di 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();
}

Saya akan menghasilkan dua angka: Panjang dan skor Scrabble. Asumsikan bahwa skor Scrabble yang rendah berarti lebih mudah untuk bergabung (skor rendah = banyak huruf umum). Urutkan daftar berdasarkan panjang menurun dan skor Scrabble naik.

Selanjutnya, turunkan daftarnya. Jika kata tersebut tidak bersilangan dengan kata yang sudah ada (periksa setiap kata dengan panjangnya dan skor Scrabble, masing-masing), masukkan ke antrean, dan periksa kata berikutnya.

Bilas dan ulangi, dan ini akan menghasilkan teka-teki silang.

Tentu saja, saya cukup yakin ini adalah O (n!) Dan tidak ada jaminan untuk menyelesaikan teka-teki silang untuk Anda, tetapi mungkin seseorang dapat memperbaikinya.

Saya sudah memikirkan masalah ini. Pengertian saya adalah bahwa untuk membuat teka-teki silang yang benar-benar padat, Anda tidak dapat berharap bahwa daftar kata Anda yang terbatas akan cukup. Oleh karena itu, Anda mungkin ingin mengambil kamus dan menempatkannya ke dalam struktur data "trie". Ini akan memungkinkan Anda dengan mudah menemukan kata-kata yang mengisi ruang yang tersisa. Dalam percobaan, cukup efisien untuk mengimplementasikan traversal yang, katakanlah, memberi Anda semua kata dalam bentuk "c? T".

Jadi, pemikiran umum saya adalah: buat semacam pendekatan kekerasan yang relatif seperti yang dijelaskan di sini untuk membuat persilangan dengan kepadatan rendah, dan mengisi kekosongan dengan kata-kata kamus.

Jika ada orang lain yang telah mengambil pendekatan ini, beri tahu saya.

Saya bermain-main dengan mesin generator teka-teki silang, dan saya menemukan ini yang paling penting:

0.!/usr/bin/python

1. Sebuah. allwords.sort(key=len, reverse=True)

   b. buat beberapa item / objek seperti kursor yang akan berjalan mengelilingi matriks untuk memudahkan orientasi kecuali jika anda ingin mengulang dengan pilihan acak nanti.

2. yang pertama, ambil pasangan pertama dan letakkan di seberang dan ke bawah dari 0,0; simpan yang pertama sebagai 'pemimpin' teka-teki silang kita saat ini.

3. pindahkan kursor dengan urutan diagonal atau acak dengan probabilitas diagonal lebih besar ke sel kosong berikutnya

4. mengulangi kata-kata seperti dan gunakan panjang ruang kosong untuk menentukan panjang kata maksimal: 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 )

5. untuk membandingkan kata dengan ruang kosong yang saya gunakan yaitu:

   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. setelah setiap kata berhasil digunakan, ubah arah. Ulangi saat semua sel terisi ATAU Anda kehabisan kata ATAU dengan batas iterasi maka:

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

... dan mengulangi teka-teki silang baru lagi.

7. Membuat sistem penilaian dengan kemudahan pengisian, dan beberapa perhitungan perhitungan. Beri skor untuk teka-teki silang saat ini dan persempit pilihan nanti dengan menambahkannya ke dalam daftar teka-teki silang yang dibuat jika skornya sesuai dengan sistem penilaian Anda.

8. Setelah sesi iterasi pertama iterasi lagi dari daftar teka-teki silang yang dibuat untuk menyelesaikan pekerjaan.

Dengan menggunakan lebih banyak parameter, kecepatan dapat ditingkatkan dengan faktor yang sangat besar.

Saya akan mendapatkan indeks dari setiap huruf yang digunakan oleh setiap kata untuk mengetahui kemungkinan persilangan. Kemudian saya akan memilih kata terbesar dan menggunakannya sebagai basis. Pilih yang besar berikutnya dan silangkan. Bilas dan ulangi. Ini mungkin masalah NP.

Ide lainnya adalah membuat algoritma genetika di mana metrik kekuatannya adalah berapa banyak kata yang dapat Anda masukkan ke dalam kisi.

Bagian tersulit yang saya temukan adalah ketika mengetahui daftar tertentu yang tidak mungkin disilangkan.

Yang ini muncul sebagai proyek dalam kursus AI CS50 dari Harvard. Idenya adalah untuk merumuskan masalah pembuatan teka-teki silang sebagai masalah kepuasan kendala dan menyelesaikannya dengan backtracking dengan heuristik yang berbeda untuk mengurangi ruang pencarian.

Untuk memulainya kita membutuhkan beberapa file input:

1. Struktur teka-teki silang (yang terlihat seperti berikut, misalnya, di mana '#' mewakili karakter yang tidak boleh diisi dan '_' mewakili karakter yang akan diisi)

`

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

`

2. Kosakata masukan (daftar kata / kamus) dari mana kata-kata kandidat akan dipilih (seperti yang ditunjukkan berikut ini).

   a abandon ability able abortion about above abroad absence absolute absolutely ...

Sekarang CSP didefinisikan dan diselesaikan sebagai berikut:

1. Variabel didefinisikan memiliki nilai (yaitu, domainnya) dari daftar kata (kosakata) yang disediakan sebagai masukan.
2. Setiap variabel diwakili oleh 3 tuple: (grid_coordinate, direction, length) di mana koordinat mewakili awal kata yang sesuai, arah dapat berupa horizontal atau vertikal dan panjangnya didefinisikan sebagai panjang kata dari variabel tersebut. ditugaskan untuk.
3. Batasan ditentukan oleh input struktur yang disediakan: misalnya, jika variabel horizontal dan vertikal memiliki karakter yang sama, itu akan direpresentasikan sebagai batasan tumpang tindih (busur).
4. Sekarang, konsistensi node dan algoritma konsistensi busur AC3 dapat digunakan untuk mengurangi domain.
5. Kemudian mundur untuk mendapatkan solusi (jika ada) ke CSP dengan MRV (nilai tersisa minimum), derajat dll heuristik dapat digunakan untuk memilih variabel yang tidak ditetapkan berikutnya dan heuristik seperti LCV (nilai paling tidak membatasi) dapat digunakan untuk domain- memesan, untuk membuat algoritma pencarian lebih cepat.

Berikut ini adalah keluaran yang diperoleh dengan menggunakan implementasi algoritma penyelesaian 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█

`

Animasi berikut menunjukkan langkah mundur:

Ini satu lagi dengan daftar kata bahasa Bangla (Bengali):

Saya telah membuat kode solusi JavaScript / jQuery untuk masalah ini:

Demo Contoh: http://www.earthfluent.com/crossword-puzzle-demo.html

Kode Sumber: https://github.com/HoldOffHunger/jquery-crossword-puzzle-generator

Maksud dari algoritma yang saya gunakan:

1. Minimalkan jumlah kotak yang tidak dapat digunakan di grid sebanyak mungkin.
2. Miliki sebanyak mungkin kata yang saling bercampur.
3. Hitung dalam waktu yang sangat cepat.

Saya akan menjelaskan algoritma yang saya gunakan:

1. Kelompokkan kata-kata itu menurut kata-kata yang memiliki huruf yang sama.

2. Dari grup ini, buat kumpulan struktur data baru ("blok kata"), yang merupakan kata utama (yang berjalan melalui semua kata lain) dan kemudian kata lainnya (yang dijalankan melalui kata utama).

3. Mulailah teka-teki silang dengan yang pertama dari blok kata ini di posisi paling kiri atas teka-teki silang.

4. Untuk blok kata lainnya, mulai dari posisi paling kanan-bawah teka-teki silang, bergerak ke atas dan ke kiri, hingga tidak ada lagi slot yang tersedia untuk diisi. Jika ada lebih banyak kolom kosong ke atas daripada di kiri, pindahkan ke atas, dan sebaliknya.