Który algorytm najlepiej pasuje do rozwiązania gry wyszukiwania słów, jak "Boggle" z Pythonem

Question

Koduję grę podobną do Boggle, w której gracz powinien znaleźć słowa wewnątrz dużego łańcucha z losowych liter.

Na przykład w tym przypadku istnieje pięć tablic z ciągami znaków. Pięć wierszy, wykonane z sześciu liter każdy:

AMSDNS 
MASDOM 
ASDAAS 
DSMMMS 
OAKSDO 

Tak, użytkownicy gry powinny wyrabiać słowa pomocą liter dostępne z następującymi ograniczeniami i zasadami pamiętać:

• Nie jest możliwe powtórz tę samą literę, aby słowo. Mówię o "fizycznej" literze w grze, która jest kostką. Nie można użyć tej samej kostki dwa lub więcej razy, aby przekazać słowo.
• Nie można "przeskoczyć" żadnej litery, aby złożyć słowo. Litery tworzące słowo muszą być ciągłe.
• Użytkownik może poruszać się w dowolnym kierunku, który chce, bez żadnych ograniczeń poza dwa wyżej wymienione. Więc możliwe jest przejście na górę, potem na dół, potem na prawo, potem znowu na górę i tak dalej. Tak więc ruchy w poszukiwaniu słów mogą być w jakiś sposób niekonsekwentne.

Chcę wiedzieć, jak przejść przez wszystkie ciągi znaków, aby utworzyć słowa. Poznać słowa Im użyję pliku txt ze słowami.

Nie wiem, jak zaprojektować algorytm, który jest w stanie przeprowadzić wyszukiwanie, szczególnie myśląc o błędnych ruchach, które są potrzebne do znalezienia słów i przestrzegania ograniczeń.

Zaimplementowałam już UX, logikę do rzucania kostką i wypełnienia gry planszowej oraz całą logikę sześcioznakowych kości.

Ale ta część nie jest łatwa i chciałbym przeczytać Wasze sugestie dotyczące tego interesującego wyzwania.

Używam Pythona do tej gry, ponieważ jest to język, którego używam do kodowania i języka, który najbardziej lubię. Ale wyjaśnienie lub sugestia samego algorytmu również powinny być miłe, niezależnie od języka.

Answer 1

Podstawowy algorytm jest prosty.

• Dla każdego kafelka wykonaj następujące czynności.
  • Zacznij od pustego słowa kandydującego, a następnie przejdź do bieżącego kafelka.
  • Odwiedź kafelek, wykonując następujące czynności.
    • Dodaj literę pozycji kafelka do słowa kandydującego.
    • Czy słowo kandydujące jest znanym słowem? Jeśli tak, dodaj go do listy znalezionych słów.
    • Czy słowo kandydujące jest przedrostkiem dowolnego znanego słowa?
      • Jeśli tak, dla każdego sąsiedniego kafelka, który nie został odwiedzony, aby utworzyć słowo kandydujące, odwiedź go (to jest, rekurencyjny).
      • Jeśli nie, cofnij (przestań rozważać nowe kafelki dla tego kandydującego słowa).

Żeby płynnie kiedy zadajesz pytanie „jest to słowo z prefiksem dowolnego słowa w moim słowniku”, uważają reprezentujący słownika jako trie. Próby oferują szybkie czasy wyszukiwania dla słów i prefiksów.

Answer 2

Może się okazać, że użyteczne jest Trie - umieść wszystkie słowa słownikowe w Trie, a następnie wykonaj kolejne Trie z siatki Boggle, tylko tak długo, jak dopasowujesz słownik Trie.

tj. Słownik trie:

S->T->A->C->K = stack 
     \->R->K = stark 
     \->T = start 

siatki (uproszczonych)

STARKX 
XXXTXX 
XXXXXX 

Siatka trie (pokazano tylko począwszy od S - również rozpoczynać się na sztukę, itp)

S->X (no matches in dict Trie, so it stops) 
\->T->X 
    \->A-R->K (match) 
     | |->T (match) 
     | \->X 
     \->C->K (match) 
     \->X  

Można było wizualizuj swoje próby z GraphViz jak this.