Algorytm generowania krzyżówki

Mając listę słów, jak byś ułożył je w siatkę krzyżówek?

Nie musiałaby przypominać „właściwej” krzyżówki, która jest symetryczna lub podobna: w zasadzie wystarczy podać pozycję początkową i kierunek dla każdego słowa.

Wymyśliłem rozwiązanie, które prawdopodobnie nie jest najbardziej wydajne, ale działa wystarczająco dobrze. Gruntownie:

1. Posortuj wszystkie słowa malejąco według długości.
2. Weź pierwsze słowo i umieść je na tablicy.
3. Weź następne słowo.
4. Przeszukaj wszystkie słowa, które są już na tablicy i zobacz, czy są jakieś możliwe przecięcia (wspólne litery) z tym słowem.
5. Jeśli istnieje możliwe miejsce na to słowo, przejrzyj wszystkie słowa na tablicy i sprawdź, czy nowe słowo przeszkadza.
6. Jeśli to słowo nie złamie planszy, umieść je tam i przejdź do kroku 3, w przeciwnym razie kontynuuj wyszukiwanie miejsca (krok 4).
7. Kontynuuj tę pętlę, aż wszystkie słowa zostaną umieszczone lub nie można ich umieścić.

To działa, ale często dość kiepska krzyżówka. Wprowadziłem kilka zmian w podstawowej recepturze powyżej, aby uzyskać lepszy wynik.

• Na koniec generowania krzyżówki, nadaj jej punktację na podstawie tego, ile słów zostało umieszczonych (im więcej, tym lepiej), jak duża jest tablica (im mniejsza, tym lepiej) oraz stosunek wysokości do szerokości (im bliżej do 1, tym lepiej). Wygeneruj kilka krzyżówek, a następnie porównaj ich wyniki i wybierz najlepszą.
  • Zamiast wykonywać dowolną liczbę iteracji, zdecydowałem się utworzyć jak najwięcej krzyżówek w dowolnym czasie. Jeśli masz tylko małą listę słów, w 5 sekund otrzymasz dziesiątki możliwych krzyżówek. Większą krzyżówkę można wybrać tylko z 5-6 możliwości.
• Umieszczając nowe słowo, zamiast umieszczać je natychmiast po znalezieniu akceptowalnej lokalizacji, nadaj temu miejscu punktację w oparciu o to, jak bardzo zwiększa rozmiar siatki i liczbę przecięć (najlepiej byłoby, gdyby każde słowo było przekreślone 2-3 innymi słowami). Śledź wszystkie pozycje i ich wyniki, a następnie wybierz najlepszą.

Niedawno napisałem własny w Pythonie. Możesz go znaleźć 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 z puzzlami dla dzieci.

W przeciwieństwie do kilku algorytmów, które tam odkryłem, które zaimplementowały losową metodę brutalnej siły do ​​umieszczania słów, jak sugerowało kilka z nich, próbowałem zaimplementować nieco inteligentniejsze podejście brutalnej siły przy umieszczaniu słów. Oto mój proces:

1. Utwórz siatkę dowolnego rozmiaru i listę słów.
2. Potasuj listę słów, a następnie posortuj słowa od najdłuższych do najkrótszych.
3. Umieść pierwsze i najdłuższe słowo w lewym górnym rogu 1,1 (w pionie lub w poziomie).
4. Przejdź do następnego słowa, zapętlaj każdą literę w słowie i każdą komórkę w siatce, szukając dopasowań między literami.
5. Po znalezieniu dopasowania po prostu dodaj tę pozycję do sugerowanej listy współrzędnych dla tego słowa.
6. Przejrzyj sugerowaną listę współrzędnych i „oceń” rozmieszczenie słów na podstawie liczby innych słów, które przecina. Wyniki równe 0 wskazują albo na złe miejsce (w sąsiedztwie istniejących słów), albo na brak krzyżyków.
7. Wróć do kroku 4, aż lista słów zostanie wyczerpana. Opcjonalne drugie przejście.
8. Powinniśmy mieć teraz krzyżówkę, ale jakość może zostać trafiona lub pominięta z powodu niektórych przypadkowych miejsc docelowych. Dlatego buforujemy tę krzyżówkę i wracamy do kroku 2. Jeśli następna krzyżówka zawiera więcej słów na tablicy, zastępuje krzyżówkę w buforze. Jest to ograniczone czasowo (znajdź najlepszą krzyżówkę w x sekund).

Na koniec masz przyzwoitą krzyżówkę lub układankę wyszukiwania słów, ponieważ są mniej więcej takie same. Zwykle działa dość dobrze, ale daj mi znać, jeśli masz jakieś sugestie dotyczące ulepszeń. Większe siatki działają wykładniczo wolniej; większe listy słów są liniowe. Większe listy słów mają również znacznie większą szansę na lepsze numery umieszczania słów.

Właściwie napisałem program do generowania krzyżówek około 10 lat temu (był on tajemniczy, ale te same zasady miałyby zastosowanie do normalnych krzyżówek).

Miał listę słów (i powiązanych wskazówek) przechowywanych w pliku posortowanych według malejącej daty użycia (tak, że rzadziej używane słowa znajdowały się na górze pliku). Szablon, w zasadzie maska ​​bitowa reprezentująca czarne i wolne kwadraty, został wybrany losowo z puli dostarczonej przez klienta.

Następnie dla każdego niekompletnego słowa w układance (w zasadzie znajdź pierwszy pusty kwadrat i zobacz, czy ten po prawej (w poprzek), czy ten poniżej (w dół) jest również pusty), przeprowadzono wyszukiwanie plik wyszukuje pierwsze pasujące słowo, biorąc pod uwagę litery znajdujące się już w tym słowie. Jeśli nie było słowa, które by pasowało, po prostu oznaczałeś całe słowo jako niekompletne i przechodziłeś dalej.

Na końcu byłoby kilka niedokończonych słów, które kompilator musiałby wypełnić (i dodać słowo i wskazówkę do pliku, jeśli trzeba). Jeśli nie mieli żadnych pomysłów, mogli ręcznie edytować krzyżówkę, aby zmienić ograniczenia lub po prostu poprosić o całkowitą zmianę generacji.

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

Ten algorytm tworzy 50 gęstych krzyżówek ze strzałkami 6x9 w 60 sekund. Wykorzystuje bazę danych słów (ze słowami i wskazówkami) oraz bazę danych tablic (ze wstępnie skonfigurowanymi tablicami).

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 danych słów znacznie skraca czas generowania, a niektóre tablice są trudniejsze do wypełnienia! Większe deski wymagają więcej czasu na prawidłowe wypełnienie!

Przykład:

Wstępnie skonfigurowana płyta 6x9:

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

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

Wygenerowana tablica 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 

Wskazówki [wiersz, 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óbuję odpowiedzieć na podstawie podobnej pracy, którą wykonałem.

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

Jest to związane z optymalizacją kombinatoryczną i programowaniem z ograniczeniami. W tym przypadku ograniczeniami są geometria siatki i wymóg unikalności słów itp.

Metody randomizacji / wyżarzania również mogą działać (chociaż w odpowiednich warunkach).

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

Wymagania dotyczyły mniej lub bardziej kompletnego kompilatora krzyżówek i konstruktora (wizualnego WYSIWYG).

Pomijając część kreatora WYSIWYG, zarys kompilatora wyglądał następująco:

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

2. Znajdź pola słów (tj. Słowa siatki) na siatce utworzonej przez użytkownika (np. Słowo w x, y o długości L, w poziomie lub w pionie) (złożoność O (N))

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

4. Obliczyć przecięcia słów w listach słów z różnymi literami używanego alfabetu (pozwala to na wyszukanie pasujących słów przy użyciu szablonu, np. Praca Sik Cambona używana przez cwc ) (złożoność O (WL * AL))

Kroki .3 i .4 pozwalają na wykonanie tego zadania:

za. Skrzyżowania ze sobą słów siatki pozwalają na stworzenie "szablonu" do wyszukiwania dopasowań w powiązanej liście słów dostępnych słów dla tego słowa z siatki (używając liter innych przecinających się słów z tym słowem, które są już wypełnione w określonym krok algorytmu)

b. Skrzyżowania słów na liście słó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 itp.)

Więc przy tych zaimplementowanych strukturach danych zastosowany algorytm wyglądał następująco:

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 pustej szczeliny na słowa (słowo siatki) i wypełnienie jej słowem kandydującym z powiązanej listy słów (randomizacja umożliwia tworzenie różnych rozwiązań w kolejnych wykonaniach algorytmu) (złożoność O (1) lub O ( N))

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

3. Przejrzyj puste pola słów obliczone w poprzednim kroku i dla każdego z nich wypróbuj kilka rozwiązań anulowania (upewniając się, że "spójność łuku jest zachowana", tj. Siatka ma rozwiązanie po tym kroku, jeśli zostało użyte to słowo) i posortuj je według maksymalna dostępność do następnego kroku (tj. następny krok ma maksymalne możliwe rozwiązania, jeśli to słowo jest używane w tym czasie w tym miejscu itp.) (złożoność O (N * MaxCandidatesUsed))

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

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

6. Jeśli zostanie znaleziony powrót, 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 zostanie znaleziona ścieżka cofania, nie można znaleźć rozwiązania (przynajmniej w tej konfiguracji, początkowym seedu itp.)

8. W przeciwnym razie, gdy wszystkie pola są wypełnione, masz jedno rozwiązanie

Algorytm ten wykonuje losowy, spójny spacer po drzewie rozwiązań problemu. Jeśli w którymś momencie pojawia się ślepy zaułek, cofa się do poprzedniego węzła i podąża inną trasą. Dopóki nie zostanie znalezione rozwiązanie lub liczba kandydatów dla różnych węzłów zostanie wyczerpana.

Część spójności zapewnia, że ​​znalezione rozwiązanie jest rzeczywiście rozwiązaniem, a część losowa pozwala na wytwarzanie różnych rozwiązań w różnych wykonaniach, a także średnio ma lepszą wydajność.

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

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

Mam nadzieję że to pomoże

Dlaczego nie zastosować na początek losowego podejścia probabilistycznego. Zacznij od słowa, a następnie kilkakrotnie 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, po prostu zacznij wszystko od nowa.

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

Oto kod JavaScript oparty na odpowiedzi nickfa i kodzie Bryana w Pythonie. Po prostu opublikuj to na wypadek, gdyby ktoś potrzebował go 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 w scrabble. Załóżmy, że niski wynik w Scrabble oznacza, że ​​łatwiej się przyłączyć (niskie wyniki = wiele popularnych liter). Sortuj listę według długości malejąco i rosnąco punktacji Scrabble.

Następnie po prostu zejdź na dół listy. Jeśli słowo nie krzyżuje się z istniejącym słowem (sprawdź z każdym słowem odpowiednio ich długość i wynik w Scrabble), a następnie umieść je w kolejce i sprawdź następne słowo.

Wypłucz i powtórz, a to powinno wygenerować krzyżówkę.

Oczywiście jestem prawie pewien, że to jest O (n!) I nie ma gwarancji, że ukończysz krzyżówkę za Ciebie, ale może ktoś może to poprawić.

Myślałem o tym problemie. Mam wrażenie, że aby stworzyć naprawdę gęstą krzyżówkę, nie możesz mieć nadziei, że Twoja ograniczona lista słów będzie wystarczająca. Dlatego możesz chcieć wziąć słownik i umieścić go w strukturze danych „trie”. Pozwoli ci to łatwo znaleźć słowa, które wypełniają pozostawione spacje. W przypadku próby dość wydajne jest zaimplementowanie przejścia, które, powiedzmy, daje wszystkie słowa w postaci „c? T”.

Tak więc moje ogólne myślenie jest następujące: stwórz coś w rodzaju stosunkowo brutalnej siły, jak niektórzy tutaj opisywali, aby stworzyć krzyż o niskiej gęstości i wypełnij puste miejsca słowami ze słownika.

Jeśli ktoś inny zastosował takie podejście, daj mi znać.

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

0.!/usr/bin/python

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

   b. stwórz jakiś przedmiot / obiekt jak kursor, który będzie poruszał się po macierzy dla łatwej orientacji, chyba że chcesz później iterować przez losowy wybór.

2. pierwszy, weź pierwszą parę i umieść je w poprzek i w dół od 0,0; zapisz pierwszą jako naszą obecną krzyżówkę „lider”.

3. przesuń kursor po przekątnej kolejności lub losowo z większym prawdopodobieństwem po przekątnej do następnej pustej komórki

4. iteruj po słowach takich jak i użyj 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ą, której 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. Zapętlaj, gdy wszystkie komórki są wypełnione LUB skończą ci się słowa LUB przez limit iteracji, a następnie:

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

... i powtórz ponownie nową krzyżówkę.

7. Zrób system punktacji przez łatwość wypełniania i kilka kalkulacji szacunkowych. Podaj wynik dla bieżącej krzyżówki i zawęź późniejszy wybór, dołączając ją do listy wykonanych krzyżówek, jeśli wynik jest zadowalający przez Twój system punktacji.

8. Po pierwszej sesji iteracji ponownie wykonaj iterację z listy wykonanych krzyżówek, aby zakończyć zadanie.

Dzięki zastosowaniu większej liczby parametrów prędkość można znacznie poprawić.

Otrzymał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 podstawy. Wybierz następny duży i przejdź przez niego. Wypłukać i powtórzyć. To prawdopodobnie problem NP.

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

Najtrudniejsze jest dla mnie to, kiedy dowiedzieć się, jakiej listy nie da się przekroczyć.

Ten pojawia się jako projekt na kursie AI CS50 z Harvardu. Pomysł polega na sformułowaniu problemu generowania krzyżówek jako problemu spełniania ograniczeń i rozwiązaniu go za pomocą wycofywania się 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)

`

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

`

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

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

Teraz CSP jest zdefiniowany i należy go rozwiązać w następujący sposób:

1. Zmienne definiuje się tak, aby miały wartości (tj. Ich domeny) z listy słów (słownictwa) podanej jako dane wejściowe.
2. Każda zmienna jest reprezentowana przez 3 krotki: (współrzędna_siatki, kierunek, długość) 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, które będzie zmienna przypisany do.
3. Więzy są definiowane za pomocą dostarczonych danych wejściowych struktury: na przykład, jeśli zmienna pozioma i pionowa ma wspólny znak, będzie to reprezentowane jako ograniczenie nakładania się (łuku).
4. Teraz algorytmy spójności węzłów i spójności łuku AC3 można wykorzystać do zredukowania domen.
5. Następnie cofanie się w celu uzyskania rozwiązania (jeśli istnieje) do CSP z MRV (minimalna pozostała wartość), stopień itp. Heurystykę można wykorzystać do wybrania następnej nieprzypisanej zmiennej, a heurystyki, takie jak LCV (najmniej ograniczająca wartość), mogą być użyte dla dziedziny porządkowanie, aby algorytm wyszukiwania był szybszy.

Poniżej przedstawiono wyniki uzyskane za pomocą implementacji algorytmu rozwiązywania 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█

`

Poniższa animacja przedstawia kroki cofania:

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

Mam napisane rozwiązanie JavaScript / jQuery dla 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

Cel zastosowanego przeze mnie algorytmu:

1. Zminimalizuj liczbę nieużywanych kwadratów w siatce tak bardzo, jak to możliwe.
2. Miej jak najwięcej mieszanych słów.
3. Obliczaj w niezwykle szybkim czasie.

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

1. Pogrupuj słowa według tych, które mają wspólną literę.

2. Z tych grup stwórz zbiory nowej struktury danych („bloki słów”), które jest słowem podstawowym (które przechodzi przez wszystkie inne słowa), a następnie innymi słowami (które przechodzą przez słowo podstawowe).

3. Rozpocznij krzyżówkę, umieszczając pierwszy z tych bloków słów w lewym górnym rogu krzyżówki.

4. Dla pozostałych bloków słów, zaczynając od prawej dolnej pozycji krzyżówki, przesuwaj się w górę i w lewo, aż nie będzie już wolnych miejsc do wypełnienia. Jeśli jest więcej pustych kolumn w górę niż w lewo, przejdź do góry i odwrotnie.