like a geek

Fabryka Kliknięć Praca w domu

Tworzenie i rozwiązywanie krzyżówek

fragment krzyzowki

Zastanawialiście się kiedyś, jak rozwiązać krzyżówkę? Taką zwykłą z milion panoramicznych.

Nie wiem, co ludzie w tym widzą, ale faktem jest, że niektórzy poświęcają swój czas na takie zajęcia - ich wola. Dużo lepszym wyjściem na do rozwiązanie krzyżówki wydaje się być wykorzystanie komputera. W artykule przedstawię prosty sposób na rozwiązanie gotowej i wygenerowanie własnej krzyżówki.

Pseudointeligencja

Pierwszym pomysłem, niestety moim zdaniem nierealnym wydaje się wczytanie haseł, znalezienie odpowiedzi na nie w Internecie i wpisanie do krzyżówki. Program taki cechowałby się bardzo małą złożonością, a szybkość i skuteczność jego działania zależałyby głównie od dostępu do baz danych z objaśnieniami haseł (wikipedia, słowniki). Takie podejście zostało zastosowane w jednym z projektów (lub prac dyplomowych) na PWr - niestety z niezbyt zadowalającym skutkiem.

Dlaczego ten sposób jest moim zdaniem słaby? Spójrzcie na obrazek na górze artykułu. Takiego prostego hasła jakim jest nazwa zwierzęcia na obrazku nie da się rozwiązać w ten sposób. Ponadto objaśnienia haseł nie muszą być dosłowne, mogą to być gry słów trudniejsze niż świętuje 22 maja. Sami autorzy twierdzą, że przy dużych krzyżówkach udaje im się rozwiązać tylko ok. 50% haseł.

Algorytm

Jak powszechnie wiadomo, komputery są głupie, ale za to całkiem dobrze radzą sobie z liczeniem. Jak na razie lepszym wyjściem wydaje się więc brute-force (no, prawie). Sposobem w 100% skutecznym, o ile tylko dysponujemy listą poprawnych słów z danego języka (słownikiem, objaśnienia nie są konieczne) jest wykorzystanie następującego algorytmu:

  1. Wybieramy pierwsze hasło i wpisujemy w nie dowolne pasujące słowo (pasujące w sensie o danej długości i ze zgadzającymi się literami, jeśli jakieś są już w krzyżówce).
  2. Tworzymy nową, tymczasową krzyżówkę, w której znajduje się dodane w punkcie pierwszym słowo.
  3. W miejsce następnego hasła wpisujemy jakiekolwiek pasujące słowo.
  4. Powtarzamy punkty 2 i 3, aż:
    • dojdziemy do ostatniego hasła - wtedy krzyżówka jest rozwiązana
    • nie będziemy w stanie dopasować poprawnego hasła - wtedy cofamy się do poprzedniego stanu i zamiast słowa powodującego błąd wstawiamy inne pasujące

W pseudokodzie algorytm można przedstawić następująco (krzyzowka - aktualny stan krzyzowki, nr - numer analizowanego hasła, slownik - zbiór słów):

uzupelnij(krzyzowka, nr, …)
{
  if (nr==ilosc hasel)
  {
    pokaz rozwiazana krzyzowke
  }
  else
  {
    foreach( slowo s in slownik )
      if ( slowo s pasuje do hasla nr )
      {
        wstaw s do krzyzowki
        uzupelnij(krzyzowka, nr+1)
        przywroc poprzedni stan hasla nr
      }
  }
}

Jak widać jest to algorytm rekurencyjny, więc jego złożoność jest trudna do przewidzenia. Wiadomo, że zależy ona od ilości haseł i rozmiaru słownika i po przeprowadzeniu kilku testów szacuję, że jest to zależność wielomianowa (mniej więcej 4 rzędu), ale naprawdę ciężko to dokładnie ocenić.Algorytm cechuje się bardzo dużą żłożonością, zależną od ilości haseł i rozmiaru słownika, ale mimo to na zwykłym pececie wyświetlenie rozwiązań trwa kilka minut. Poza rozmiarem słownika i liczbą haseł złożoność zależy także od kolejności wybieranych haseł, ilości słów o tej samej długości itd. Pomijając potrzebny czas algorytm wygeneruje wszystkie możliwe rozwiązania, a jeśli krzyżówka krzyżuje się w wielu miejscach (panoramiczne) rozwiązanie będzie prawdopodobnie tylko jedno. Przy małych krzyżówkach rozwiązań jest niestety bardzo dużo i algorytm nie zdaje egzaminu.

Aby przyśpieszyć działanie programu warto zminimalizować ilość sprawdzanych słów. Typowy słownik krzyżówkowicza ma kilka tysięcy haseł, których sprawdzenie jest bardzo czasochłonne. Zamiast tego można podzielić cały słownik na listy zależne od długości słowa, a następnie przyporządkowywanie słów na podstawie wyrażenia regularnego. Dla haseł 4-6 literowych (takich jest najwięcej) daje to olbrzymie  przyśpieszenie.

Jeśli rozwiązanie jest tylko jedno jesteśmy już w domu. Gorzej, jeśli program wyświetlił ich więcej. Tutaj możemy albo ręcznie sprawdzać ich sens, albo dopiero teraz zmusić program do szukania informacji w słownikach - z tego co zauważyłem długie hasła typu halabardzista są znajdowane poprawnie, ale krótkie hasła typu O?A generują problemy jeśli jest za mało skrzyżowań. W każdym razie na pewno łatwiej szukać informacji o kilku słowach niż 100 z całej krzyżówki - łatwiej jest wybrać jedno rozwiązanie z kilku niż sprawdzać każde hasło po kolei:).

Jak zrobić 500 panoramicznych?

Wygenerowanie krzyżówki nie wymaga już ani trochę inteligencji, ale za to konieczna jest duża ilość obliczeń (jak poprzednio). Tworzymy więc pole krzyżówki - najlepiej w miarę losowo, ale tak, żeby zostawić pola na opisy haseł i… rozwiązujemy ją. W tym przypadku nie musimy szukać wszystkich rozwiązań - wystarczy jedno. Jeśli mamy już układ słów w krzyżówce w odpowiednie miejsca wpisujemy opisy przyporządkowane do haseł, np. w tablicy asocjacyjnej. Skąd je wziąć? Można pisać samemu, można skopiować pierwsze trzy słowa każdego hasła z wikipedii. Można też skorzystać z jakiegoś gotowego słownika.

Jak widać algorytm nie jest skomplikowany, a wygenerowanie krzyżówki to tylko kwestia mocy obliczeniowej i wystarczająco bogatego słownika. Aby urozmaicić rozwiązywaczom zabawę można dodać po kilka opisów do każdego hasła, gdzieniegdzie wstawić rysunki itp. Co do kodu programu, to niestety nie mogę go na razie przedstawić z powodu praw autorskich (plagiatowanie samego siebie - pozdrawiam pana P.;), ale przepisanie podanego algorytmu na wybrany język nie powinno sprawić nikomu problemów, a utworzenie klasy opisującej krzyżówkę też nie jest trudne. Największy problem to dostosowanie do sposobu przechowywania danych o krzyżówce. Nic tylko drukować i podpisać umowę z siecią kiosków;).

Autor artykułu: Marcin Kosedowski.

Komentarze są własnością użytkowników. Zastrzegam sobie prawo do ich usuwania, jeśli uznam je za nieodpowiednie. Więcej w polityce prywatności.

Uwaga! Blog został przeniesiony na domenę like-a-geek.pl. Zapraszam na porcję nowych wpisów!

Zamknij [x]

Możesz za darmo umieścić ten artykuł na dowolnej stronie, również komercyjnej, w postaci dokładnie takiej jak w ramce poniżej i zachowując aktywne hiperłącza (linki). Licencja artykułu: CC-BY-ND. Licencja nie dotyczy zdjęć w nagłówkach artykułów! Dozwolone jest dodanie stylu do wstępu, stopki, danych autora, zmiana poziomu środtytułów (np. z h2 na h3) i odłączenie wstępu oraz tytułu od reszty.