Twoja codzienna wiedza ze świata podatków

Tworzenie i rozwiązywanie krzyżówek

2009-01-02 | 

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.

Uwaga! Przedstawione informacje tylko w ogólny sposób wyjaśniają opisywaną ideę. Aby cała konstrukcja została wykonana poprawnie, niezbędna jest specjalistyczna wiedza z zakresu prawa podatkowego. Przed podjęciem jakichkolwiek działań mających wpływ na twoją firmę, koniecznie poznaj szczegóły!

Zachęcam również do opisywania swoich doświadczeń w komentarzach.

  • #1

    Ciekawe, ciekawe. A masz jakiegoś OCRa do krzyżówek?

    (btw, "W każdym razie..W każdym razie")

  • #2

    OCR-a mam (przejrzyj poprzednie wpisy;), ale w tym przypadku nie był konieczny, bo mam dostęp do plików opisujących krzyżówki typu haslo1: x, y, pion/poziom, dlugosc. haslo2... i do takiego opisu musiałem się dostosować.

  • #3

    Oczywiście ;] Niecodzienny temat.Bardzo ciekawe...kiedyś zastanawiałem się jak ludzie dopasowują te słowa żeby wyszła taka krzyżówka :D

    firunna
  • #4

    Można by spróbować przyspieszyć taki algorytm poprzez uczenie się skryptu z krzyżówek tzn.algorytm zgadł że dla pytania "świętują 22 maja" jest chrześcijanie to dla takiego pytania sprawdza czy pasuję wcześniej niż słowo zupełnie inne oraz sprawdza wcześniej synonimy tego słowa.
    Zamiast sprawdzić 500 słów sprawdzi np.25 i będzie większa szansa że odpowie poprawnie.

    Zen Vantalye
  • #5

    "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ć."

    Na jakiej podstawie wysuwasz takie wnioski? Na moje oko złożoność będzie raczej wykładnicza, co widać to po Twoim pseudokodzie. Zaczynasz od wywołania uzupelnij(krzyzowka, 1), w tym miejscu masz pewną ilość (K) wywołań rekurencyjnych uzupelnij(krzyzowka, 2), z każdego takiego wywołania powstają kolejne wywołania itd.

  • #6

    Post jest tak kiepski że aż szkoda komentować... Ale nie marnuj się, idź na polonistykę albo inną filologię zamiast trudzić matematyką.

    Edward2
  • #7

    Możliwe, że ilość haseł wpływa wykładniczo na ogólną złożoność, ale wielkość słownika chyba tu przeważa - rekurencyjnie wywołuje się kolejne hasła, których jest np. 50, a w nich już liniowo sprawdza się cały słownik (kilka tysięcy słów).

    W czasie testów programu zauważyłem, że dwukrotne powiększenie słownika powodowało 3-4 krotny wzrost ilości podstawień (kroków), ale zależy to np. od tego iloliterowe słowa się dodaje.

    Oczywiście mogę się mylić i jeśli ktoś jest w stanie w miarę dokładnie ocenić złożoność albo przedstawić sposób na badanie tego typu algorytmów chętnie posłucham.

    Tak na szybko przyszedł mi do głowy jeszcze jeden pomysł. Weźmy krzyżówkę powiedzmy k-hasłową, ale taką, że hasło drugie ma tylko jeden punkt wspólny z hasłem pierwszym, trzecie jeden punkt z drugim itd. Wszystkie hasła są tej samej długości i mogą się powtarzać. Powiedzmy, że słownik ma n słów.
    W najgorszym przypadku wstawiamy do hasła pierwszego słowo, przechodzimy do drugiego itd. W ostatnim haśle trafiamy dopiero na ostatnie słowo, w przedostatnim też, w drugim od końca też itd. Okazało się, że wszędzie pasuje ostatnie hasło ze słownika (np. zzzz). Czy dobrze myślę, że wykona się n^k podstawień? Trochę dużo, ale jednak komputer parę minut liczy;).

  • #8

    Ehm, trzymając się z daleka od osobistych przytyków, ten post z tego co rozumiem naprawdę nie ma wielkiego sensu. Załóżmy, że mamy małą krzyżówkę - 10 haseł po 10 liter, nic niespotykanego. W małym słowniku (500kb) języka angielskiego 10-literowych słów znajduję się około 5000. Już pierwszy poziom drzewka rekurencji ma więc 5000 węzłów, każdy z tych węzłów ma kolejne 5000 węzłów, więc w pesymistycznej wersji mamy do sprawdzenia 5000**10 kombinacji słów, czyli: 9765625000000000000000000000000000000. Jestem pewien, że można jakoś ładnie zilustrować ile by trwało czasu sprawdzenie takiej ilości kombinacji, czy słońce by się czasem wcześniej nie wypali, nie wspominając o ilości potrzebnej pamięci. Przy czym krzyżówki rzadko mają tylko 10 haseł, a dla niektórych długości słów jest więcej niż 5000 możliwości...

  • #9

    Btw, szybkie google pokazuje że ten problem cechują się taką miłą właściwością:

    http://en.wikipedia.org/wiki/AI-complete

    A tu można poczytać o tym jak się próbuje atakować to zagadnienie, z dosyć dobrym skutkiem:

    http://www.williamtp.com/crosswords/

  • #10

    Usunąłem wpis z techbloga, mimo że informacje o złożoności to tylko jedno zdanie wyraźnie wskazujące na to, że są to tylko moje przypuszczenia. Wpis miał raczej przedstawić jeden ze sposobów tworzenia krzyżówek.

    Wydaje mi się, że podana przez Ciebie liczba jest trochę za duża - pierwsza lepsza krzyżówka (27 haseł) przy słowniku złożonym z 4609 wyrazów różnej długości wykonała 1449 1295 311 1213 306 82 423 kroków czyli o 15 rzędów wielkości niż wskazują twoje obliczenia dla 10 haseł i o 76 rzędów mniej niż wynikałoby z twojego wzoru.

    Na pewno zgadzam się, że to i tak długo - obliczenia trwały kilka minut, ale nie na tyle, żeby rezygnować z algorytmu.

  • #11

    Ehm, to ile Twój program wykonał kroków w danym przypadku nie ma żadnego związku z tym jaka jest jest przybliżona złożoność w pesymistycznym przypadku - pozatym zauważ, że Twój słownik ma 5000 wszystkich haseł, mój ma 5000 haseł dla tej jednej konkretnej długości.

    Dokładne liczby i tak nie są zbyt ważne, wystarczy fakt, że złożoność jest wykładnicza względem ilości słów w słowniku dla hasła danej długości.

    No i ten, to że literki pasują w kratki, długości się zgadzają itp., nie znaczy że rozwiązanie krzyżówki ma sens...

  • #12

    Jasne, że to ile kroków wyszło nie określa złożoności pesymistycznej, w 100% się zgadzam. Ale dzięki twoim obliczeniom można zobaczyć, jakie są różnice między przewidywaniami a praktyką.
    Co do rozwiązania, to jeśli wyjdzie tylko jedno, to jest ono poprawne (przy założeniu, że słownik jest kompletny, ale w krzyżówkach jest na końcu pełna lista haseł). Jeśli jest kilka rozwiązań, to trzeba już użyć innego sposobu (napisałem o tym).

  • #13

    Kompletny słownik języka polskiego ma 100 000 haseł i raczej nie sądze żeby dawał jedną odpowiedź, zakładająć że wogóle uda się wyliczyć zbiór możliwych rowiązań (a nie uda się). Czy to nie jest tak, że te krzyżówki które Twój program rozwiązuje, to te same które inny program generuje, z tego samego niedużego słownika?

    Co do "generowania krzyżówek", to można wylosować zbiór słów, które słowa z którymi i w jakim miejscu mają się przecinać. To nie jest trudne, a dużo szybsze.

    To ja sobie grzecznie pójde :)

  • #14

    Tak, słownik jest ten sam (rozwiązujący też mają do niego dostęp). A losowanie grup słów (jeśli dobrze zrozumiałem ideę) nie będzie dawało za często takich samych fragmentów krzyżówki?

  • #15

    Po każdym wylosowaniu słowa usuwasz je ze słownika i losujesz potem z tego już ogarniczonego zbioru słów.

  • #16

    Co do pierwszego punktu algorytmu - wypadałoby na początku posortować hasła malejąco według długości, żeby zwiększyć wydajność. Im dłuższe słowo, tym mniej możliwości, tym szybciej dojdzie do ewentualnej blokady i tym mniej czasu się zmarnuje na badanie błędnych kombinacji.

  • #17

    Ja bym wpisywał pojedyncze litery (zamiast od razu całych haseł) starając się z grubsza wypełniać kwadraty/prostokąty kratek, tak żeby jak najszybciej opuszczać ślepe uliczki w przestrzeni rozwiązań.

    Żeby to było efektywne, trzeba by utworzyć osobne drzewo trie słów dla każdej długości słowa i każdej pozycji startowej w słowie. Wyjdzie jakieś kilkaset takich drzew, więc od biedy ujdzie.

    Może przykład, jakby działał ten algorytm: załóżmy, że mamy wypełnione:
    ___
    |ob
    |a*
    |

    I teraz w miejscu oznaczonym gwiazdką na pewno nie będziemy mogli wstawić "b", bo z drzewa trie odczytamy, że nie ma wyrazu zaczynającego się na "bb".

    A, jeszcze jedno: należy zacząć wypełnianie od kratek w "najgęstszych" obszarach (z największą liczbą sąsiednich kratek na litery).

    doktorek Nerwosolek
  • #18

    Nie wspomniałem nic o kolejności wypełniania krzyżówki. Dobrym rozwiązaniem wydaje się być znalezienie hasła, które ma możliwie dużo "skrzyżowań" (powiedzmy, że jest poziome), następnie sprawdzenie haseł które się z nim przecinają (pionowych) i następnie haseł poziomych leżących w okolicy.
    Nie mam też nic do zarzucenia metodzie Doktorka, pewnie wyjdzie na to samo;).

  • #19

    To jezeli ktoś z was opracuje taki działąjący programik do pisania i rozwiązywania krzyżówek to z miłą chęcią go ściągnę :)

    xyz
  • #20

    Witam.

    Tak się składa, że jestem jednym z współautorów serwisu szarada.net i jak się można przekonać na naszej stronie, mam w dziedzinie układania krzyżówek (zarówno wspomaganych komputerowo, jak i nie) spore doświadczenie i osiągnięcia wykraczające nawet poza wspomniane '500 panoramicznych'.

    Niestety, problem układania krzyżówek jest dużo bardziej złożony, niż zostało tu przedstawione. Problem jest NP-zupełny, a czas wykładniczy. Ponadto, kilka przedstawionych tez mija się z prawdą:
    - typowy słownik krzyżówkowy to raczej kilkadziesiąt tysięcy haseł, nie kilka
    - duże krzyżówki mają zdecydowanie więcej możliwych rozwiązań, niż małe
    - przedstawiony algorytm układania krzyżówki zakłada, że krzyżówki da się wygenerować dokładając iteracyjnie po jednym słowie. Niezmiennikiem jest założenie, że w kroku iteracji wciąż mamy prawidłową krzyżówkę. Tymczasem nie da się w ten sposób ułożyć krzyżówek gęstych, zawierających słowa 'przylegające' do siebie poziomo lub pionowo - gdyż każde takie dołożenie generuje zalążki nowych słów prostopadle.

    Zapraszam do sprawdzenia naszych dokonań na http://szarada.net/krzyzowki/ - szczególnie w sekcjach krzyżówek tematycznych bądź ciekawych kształtów.

    Pozdrawiam,

    p

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.

Ostatnie wpisy

O mnie

konrad michalak e-conversion Na co dzień jako freelancer zajmuję się analizą konwersji stron. Aktualnie zajmuję się głównie poprawą skuteczności reklam dla ClickFactory.EU.

Wpisy Wybrane Specjalnie Dla Ciebie

X