Algorytm generowania krzyżówki

Niedawno napisałem swój własny w Pythonie. Znajdziesz go tutaj: http://bryanhelmig.com/python-crossword-puzzle-generator/. nie tworzy gęstych krzyżówek w stylu NYT, ale styl krzyżówek, które można znaleźć w książeczce dla dzieci.

W przeciwieństwie do kilku algorytmów, które odkryłem tam, że zaimplementował losową metodę brute-force umieszczania słów, jak kilka zasugerowało, próbowałem zaimplementować nieco mądrzejsze podejście brute-force przy umieszczaniu słów. Oto mój proces:

1. Utwórz siatkę o dowolnej wielkości i listę słów.
2. przetasuj listę słów, a następnie posortuj słowa według najdłuższych do najkrótszych.
3. Umieść pierwsze i najdłuższe słowo w lewym górnym rogu, 1,1 (pionowo lub poziomo).
4. przejdź do następnego słowa, zapętlaj każdą literę w słowie i każdą komórkę w siatce, szukając dopasowania liter do liter.
5. gdy dopasowanie zostanie znalezione, po prostu dodaj tę pozycję do sugerowanej listy współrzędnych dla tego słowo.
6. wykonaj pętlę nad sugerowaną listą współrzędnych i "oceń" rozmieszczenie słów na podstawie liczby innych słów, które krzyżują się. Wyniki 0 wskazują albo złe umiejscowienie (sąsiadujące z istniejącymi wyrazami), albo że nie było krzyżyków wyrazowych.
7. wróć do kroku # 4, aż lista słów zostanie wyczerpana. Opcjonalnie drugi przejazd.
8. powinniśmy teraz mieć krzyżówkę, ale jakość może zostać trafiona lub pominięta z powodu niektórych losowych miejsc. Więc buforujemy tę krzyżówkę i wracamy do kroku # 2. Jeśli następny krzyżówka ma więcej słów umieszczonych na planszy, zastępuje krzyżówkę w buforze. Jest to ograniczone czasowo (znajdź najlepszą krzyżówkę w X sekund).

Na koniec masz porządną krzyżówkę lub wyszukiwarkę słów, ponieważ są one mniej więcej takie same. Działa raczej dobrze, ale daj mi znać, jeśli masz jakieś sugestie dotyczące poprawy. Większe siatki działają wykładniczo wolniej; większe listy słów liniowo. Większe listy słów mają również znacznie większą szansę na lepsze umieszczenie słów liczby.

Napisałem program do tworzenia krzyżówek jakieś 10 lat temu(to było zagadkowe, ale te same zasady obowiązują dla normalnych krzyżówek).

Miał listę słów (i powiązanych wskazówek) przechowywanych w pliku posortowanym według malejącego użycia do daty (tak, że mniej używane słowa były na górze pliku). Szablon, w zasadzie maska bitowa reprezentująca Czarne i wolne kwadraty, został wybrany losowo z puli, która została dostarczona przez Klienta.

Wtedy, dla każdego niepełnego słowa w zagadka (zasadniczo znajdź pierwszy pusty kwadrat i sprawdź, czy ten po prawej (w poprzek) lub ten pod spodem (w dół) jest również pusty), przeprowadzono wyszukiwanie pliku szukającego pierwszego słowa, które pasowało, biorąc pod uwagę litery już w tym słowie. Jeśli nie było słowa, które mogłoby się zmieścić, po prostu zaznaczyłeś całe słowo jako niekompletne i ruszyłeś dalej.

Na końcu będzie kilka nieukończonych słów, które kompilator musiałby wypełnić (i dodać słowo i wskazówkę do plik w razie potrzeby). Jeśli nie mogliby wymyślić żadnych pomysłów, mogliby edytować krzyżówkę ręcznie, aby zmienić ograniczenia lub po prostu poprosić o całkowitą ponowną generację.

Gdy plik Word / clue osiągnął określony rozmiar (i dodawał 50-100 wskazówek dziennie dla tego klienta), rzadko zdarzało się więcej niż dwa lub trzy ręczne poprawki, które trzeba było zrobić dla każdej krzyżówki.

Algorytm ten tworzy 50 gęstych krzyżówek 6x9 strzałek W 60 sekund. Używa bazy danych word (z poradami word+) i bazy danych plansz (z wstępnie skonfigurowanymi planszami).

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

Większa baza słów znacznie skraca czas generowania, a niektóre tablice są trudniejsze do wypełnienia! Większe deski wymagają więcej czasu na poprawne wypełnienie!

Przykład:

Wstępnie skonfigurowana Płyta 6x9:

(# oznacza jedną końcówkę w jednej komórce, % oznacza dwie końcówki w jednej komórce, strzałki nie pokazano)

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

Wygenerowano planszę 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 

Końcówki [linia, kolumna]:

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

Chociaż jest to starsze pytanie, spróbuje odpowiedzieć na podstawie podobnej pracy, którą wykonałem.

Istnieje wiele podejść do rozwiązywania problemów z ograniczeniami (które generalnie należą do klasy złożoności NPC).

Jest to związane z optymalizacją kombinatoryczną i programowaniem ograniczeń. W tym przypadku ograniczenia są geometria siatki i wymóg, że słowa są unikalne itp..

Metody randomizacji/wyżarzania mogą również działać (chociaż w ramach właściwego ustawienie).

Efektywna prostota może być po prostu ostateczną mądrością !

Wymagania były dla mniej lub bardziej kompletnego kompilatora krzyżówek i (visual WYSIWYG) konstruktora.

Pomijając część WYSIWYG builder, zarys kompilatora był następujący:

1. Załaduj dostępne listy słów (posortowane według długości słów, czyli 2,3,..,20)

2. Znajdź słowa (czyli słowa siatki) na siatce konstruowanej przez użytkownika (np. słowo w x, y o długości L, poziome lub pionowe) (złożoność O (N) )

3. Oblicz przecinające się punkty słów siatki (które muszą być wypełnione) (złożoność O (N^2) )

4. Oblicz przecięcia słów w listach słów z różnymi literami używanego alfabetu (pozwala to na wyszukiwanie pasujących słów za pomocą szablonu np. Sik Cambon thesis as used by cwc ) (złożoność O (WL*AL) )

Kroki .3 i .4 Pozwól na wykonanie tego zadania:

A. The przecinające się ze sobą słowa siatki umożliwiają utworzenie "szablonu" do prób znalezienia dopasowania w powiązanej liście słów dostępnych dla tego słowa siatki (za pomocą liter innych przecinających się słów z tym słowem, które są już wypełnione na pewnym etapie algorytmu)

B. przecięcia wyrazów w liście wyrazów z alfabetem pozwalają znaleźć pasujące (kandydujące) słowa, które pasują do danego "szablonu" (np. " A "na 1. miejscu i" B " na 3. miejscu itd..)

Więc z tymi strukturami danych zaimplementowany algorytm był sth tak:

Uwaga: jeśli siatka i baza słów są stałe, poprzednie kroki można wykonać tylko raz.

1. Pierwszym krokiem algorytmu jest losowe wybranie pustego słowa (słowa siatki) i wypełnienie go słowem kandydującym z powiązanej z nim listy słów (randomizacja umożliwia tworzenie różnych rozwiązań w kolejnych egzekucjach algorytmu) (złożoność O (1) lub O (N) )

2. Dla każdego pustego slotu słów (które mają przecięcia z już wypełnionymi slotami słów), Oblicz współczynnik ograniczenia (może się różnić, sth simple to liczba dostępnych rozwiązań na tym etapie) i posortuj puste sloty słów według tego współczynnika (złożoność O (NlogN) lub O (N) )

3. Pętla przez puste słowa obliczone w poprzednim kroku i dla każdego z nich spróbuj kilku rozwiązań cancdidate (upewniając się, że "spójność łuku jest zachowana" , czyli siatka ma rozwiązanie po tym kroku, jeśli to słowo jest używane) i posortować je według maksymalnej dostępności dla następnego kroku (tzn. następny krok ma maksymalne możliwe rozwiązania, jeśli to słowo jest używane w tym czasie w tym miejscu, itd..) (złożoność O(N * MaxCandidatesUsed) )

4. Wypełnij To słowo (oznacz je jako wypełnione i przejdź do kroku 2)

5. Jeśli nie znaleziono żadnego słowa spełniającego kryteria kroku .3 spróbuj wrócić do innego kandydata rozwiązanie jakiegoś poprzedniego kroku (kryteria mogą się tutaj różnić) (złożoność O (N) )

6. Jeśli backtrack znajdzie, użyj alternatywy i opcjonalnie Zresetuj wszystkie już wypełnione słowa, które mogą wymagać zresetowania (oznacz je ponownie jako niewypełnione) (złożoność O (N) )

7. Jeśli nie znaleziono backtrack, nie można znaleźć rozwiązania (przynajmniej z tą konfiguracją, początkiem itp..)

8. Else gdy wszystkie wordloty są wypełnione masz jedno rozwiązanie

Algorytm ten wykonuje losowy, spójny spacer po drzewie rozwiązań problemu. Jeśli w pewnym momencie jest ślepy zaułek, wykonuje backtrack do poprzedniego węzła i podąża inną trasą. Dopóki nie znajdzie się rozwiązanie lub liczba kandydatów na poszczególne węzły nie zostanie wyczerpana.

Część konsystencji zapewnia, że znalezione rozwiązanie jest rzeczywiście rozwiązaniem, a część losowa umożliwia wytwarzanie różnych rozwiązań w różnych egzekucjach, a także średnio mają lepszą wydajność.

PS. wszystko to (i inne) zostało zrealizowane w czystej JavaScript (z możliwością przetwarzania równoległego i WYSIWYG)

PS2. Algorytm może być łatwo zrównoleglony w celu wytworzenia więcej niż jednego (innego) rozwiązania w tym samym czasie

Hope this helps

Dlaczego po prostu nie użyć losowego podejścia probabilistycznego na początek. Zacznij od słowa, a następnie wielokrotnie wybierz losowe słowo i spróbuj dopasować je do aktualnego stanu układanki bez łamania ograniczeń dotyczących rozmiaru itp.. Jeśli ci się nie uda, zacznij od nowa.

Będziesz zaskoczony, jak często takie podejście Monte Carlo działa.

Oto kod JavaScript oparty na odpowiedzi nickf i Kod Pythona Bryana. Wrzucę to na wypadek, gdyby ktoś inny potrzebował w 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();
}

Wygenerowałbym dwie liczby: długość i wynik Scrabble. Załóżmy, że niski wynik Scrabble oznacza, że łatwiej jest dołączyć (niskie wyniki = wiele wspólnych liter). Sortuj listę według długości malejąco i Scrabble score rosnąco.

Następnie przejdź do listy. Jeśli słowo nie krzyżuje się z istniejącym słowem (zaznacz je według ich długości i wyniku Scrabble), umieść je w kolejce i Sprawdź następne słowo.

Spłukać i powtórzyć, a to powinno wygenerować krzyżówka.

Oczywiście, jestem prawie pewien, że to jest O(n!) i nie jest gwarantowane, aby zakończyć krzyżówkę dla ciebie, ale może ktoś może go poprawić.

Myślałem o tym problemie. Moim zdaniem, aby stworzyć naprawdę gęstą krzyżówkę, nie możesz mieć nadziei, że Twoja ograniczona lista słów będzie wystarczająca. Dlatego warto wziąć słownik i umieścić go w strukturze danych "trie". Pozwoli Ci to łatwo znaleźć słowa, które wypełniają Pozostałe spacje. W Trie dość efektywnie jest zaimplementować traversal, który np. daje wszystkie słowa postaci " c?t".

Moje ogólne myślenie brzmi: stworzyć jakiś o stosunkowo brutalnej sile podejścia, jak niektórzy opisali tutaj, aby utworzyć krzyż o niskiej gęstości i wypełnić puste słowa słownikowe.

Jeśli ktoś jeszcze zastosował takie podejście, proszę dać mi znać.

Bawiłem się przy silniku generatora krzyżówek i uznałem to za najważniejsze:

0.!/usr/bin/python

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

   B. stwórz jakiś element / obiekt jak kursor, który będzie chodzić po macierzy dla łatwej orientacji chyba, że chcesz później powtórzyć przez losowy wybór.

2. Pierwszy, podnieś pierwszą parę i umieść je w poprzek iw dół od 0,0 ; Zapisz pierwszą jako naszą obecną krzyżówkę "lider".

3. Przesuń kursor według kolejności diagonalny lub losowy z większym prawdopodobieństwem diagonalnym do następnej pustej komórki

4. Powtarzaj słowa podobne i używaj wolnej przestrzeni, aby zdefiniować maksymalną długość słowa : 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. Aby porównać słowo z wolną przestrzenią użyłem tj.:

   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. Po każdym pomyślnie użytym słowie zmień kierunek. Pętla gdy wszystkie komórki są wypełnione lub zabraknie słów lub limitu iteracji to:

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

...i znowu nowe krzyżówka.

1. Dodać system punktacji przez łatwość napełniania, a niektóre kalki szacowania. Podaj wynik dla bieżącej krzyżówki i zawęź późniejszy wybór dołączając ją do lista wykonanych krzyżówek, jeśli wynik jest spełniony przez system punktacji.

2. Po pierwszej sesji iteracji powtórz ponownie z listy wykonanych krzyżówek, aby zakończyć zadanie.

Dzięki zastosowaniu większej liczby parametrów prędkość może być poprawiona przez ogromny czynnik.

Ten pojawia się jako projekt w kursie AI CS50 z Harvardu. Chodzi o sformułowanie problemu generowania krzyżówek jako problemu satysfakcji z ograniczeń i rozwiązanie go za pomocą backtrackingu z różnymi heurystykami w celu zmniejszenia przestrzeni wyszukiwania.

Na początek potrzebujemy kilku plików wejściowych:

1. struktura krzyżówki (która wygląda jak następująca, np., gdzie " # "oznacza znaki, których nie należy wypełniać, a" _ " oznacza znaki do wypełnienia)

`

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

`

1. Słownictwo wejściowe (lista słów / słownik), z którego zostaną wybrane słowa kandydujące(jak ten pokazany poniżej).

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

Teraz CSP jest zdefiniowany i ma być rozwiązany w następujący sposób:

1. zmienne są zdefiniowane jako wartości (tj. ich domeny) z listy słów (słownictwa) DOSTARCZANYCH JAKO dane wejściowe.
2. każda zmienna jest reprezentowana przez 3 krotka: (grid_coordinate, direction, length) gdzie współrzędna reprezentuje początek odpowiedniego słowa, kierunek może być poziomy lub pionowy, a długość jest zdefiniowana jako długość słowa, do którego zostanie przypisana zmienna.
3. ograniczenia są definiowane przez Dane wejściowe struktury: na przykład, jeśli zmienna pozioma i pionowa ma wspólny znak, będzie reprezentowana jako ograniczenie nakładania się (arc).
4. Teraz spójność węzła i AC3 algorytmy spójności arc mogą być używane do redukcji domen.
5. następnie powrót do uzyskania rozwiązania (jeśli istnieje) do CSP z MRV( minimalna pozostała wartość), stopień itp. heurystyka może być używana do wybrania następnej zmiennej bez przypisania, a heurystyka taka jak LCV (least constraining value) może być używana do porządkowania domeny, aby algorytm wyszukiwania był szybszy.

Poniżej przedstawiono wyniki uzyskane za pomocą implementacji rozwiązania CSP algorytm:

`
███S████D█
MUCH████E█
E██A█AGENT
S██R█N██Y█
SUPPLY████
█N███O████
█I██INSIDE
█Q███E██A█
SUGAR███N█
█E██████C█
██OFFENSE█

`

Poniższa animacja pokazuje kroki cofania:

Oto kolejny z listą słów w języku Bangla (Bengali):

Dostałbym indeks każdej litery używanej przez każde słowo, aby poznać możliwe krzyże. Wtedy wybrałbym największe słowo i użyłbym go jako bazy. Wybierz następny duży i skrzyżuj go. Spłukać i powtórzyć. To pewnie problem np.

Innym pomysłem jest stworzenie algorytmu genetycznego, w którym miarą siły jest ilość słów, które można umieścić w siatce.

Najtrudniejsze jest to, kiedy poznać pewną listę nie można przekroczyć.

Mam zakodowane JavaScript / jQuery rozwiązanie tego problemu:

Przykładowe Demo: http://www.earthfluent.com/crossword-puzzle-demo.html

Kod źródłowy: https://github.com/HoldOffHunger/jquery-crossword-puzzle-generator

Intencja algorytmu, którego użyłem:

1. zminimalizuj liczbę bezużytecznych kwadratów w siatce tak bardzo, jak to możliwe.
2. mieć tyle mieszanych słów, ile możliwe.
3. Oblicz w bardzo szybkim czasie.

Opiszę algorytm, którego użyłem:

1. Pogrupuj słowa razem zgodnie z tymi, które mają wspólną literę.

2. Z tych grup buduj zestawy nowej struktury danych ("bloki słów"), które są słowem podstawowym (które przebiega przez wszystkie inne słowa), a następnie innymi słowami (które przebiega przez słowo podstawowe).

3. Zacznij krzyżówkę puzzle z pierwszym z tych bloków słowa w bardzo górnej lewej pozycji krzyżówki.

4. Dla reszty bloków słowa, począwszy od prawej-dolnej większości pozycji krzyżówki, poruszać się w górę i w lewo, aż nie ma więcej dostępnych miejsc do wypełnienia. Jeśli jest więcej pustych kolumn w górę niż w lewo, Przesuń w górę i odwrotnie.