wykreślanki - algorytm tworzenia

Mamy prostokąt o zadanych wymiarach np. 10x14 oraz listę słów.
Układamy te słowa w prostokącie na 8 sposobów: poziomo, pionowo, prawo oraz lewo skośnie, i to wszystko jeszcze może być w dwóch kierunkach: wprost lub wspak, razem 8.

Musimy wypełnić tak cały prostokąt, albo opcjonalnie pozostawiamy kilkanaście kratek, w które potem wpiszemy sobie jakieś hasło - rozwiązanie, może to być np. przysłowie, które rozwiązujący po prostu sobie odczyta po wykreśleniu wszystkich słów (niewykreślone litery czytane np. wierszami dadzą właśnie to hasło).

Ma ktoś na to jakiś prosty pomysł - algorytm?
Nie musi być super - perfekt, wystarczy żeby coś tam mulił w miarę szybko, jakoś losowo,
np. niech robi 100 wariantów, spośród których wybiera potem z 5 najlepszych - wg jakiegoś kryterium,
więc coś tam zawsze przypasuje. :)

Szukaj pod crossword generation algorithm

Shalom napisał(a):

Szukaj pod crossword generation algorithm

Crossword to nie jest wykreślana, lecz krzyżówka.
W angielskim wykreślanka to: word fit, albo word fill, puzzle.

Ogólnie rzecz biorąc krzyżówki są trudniejsze od wykreślanek,
ponieważ w krzyżówkach mamy warunek przecinania słów, przynajmniej z dwoma innymi, zwykle.

Zacznij od planu minimum, wyszukiwania słów do podanego wzorca.
tu masz mój post jako wskazówkę (w kodzie jest mała literówka, brakuje litery ń), twoje wymagania są troszkę inne więc musisz nad tym popracować.

@fanta zauważ że generalnie algorytm generacji krzyżówki jest taki sam jak dla wykreślanki, z dokładnością do ograniczenia dla "wymiarów" wykreślanki.

MarekR22 napisał(a):

Zacznij od planu minimum, wyszukiwania słów do podanego wzorca.
tu masz mój post jako wskazówkę (w kodzie jest mała literówka, brakuje litery ń), twoje wymagania są troszkę inne więc musisz nad tym popracować.

Co mi tym... w wykreślankach jest odwrotny warunek - jak najmniej skrzyżowań, najlepiej wcale.

Shalom napisał(a):

@fanta zauważ że generalnie algorytm generacji krzyżówki jest taki sam jak dla wykreślanki, z dokładnością do ograniczenia dla "wymiarów" wykreślanki.

Tak?
To chyba jeszcze gorzej... :)

fanta napisał(a):

MarekR22 napisał(a):

Zacznij od planu minimum, wyszukiwania słów do podanego wzorca.
tu masz mój post jako wskazówkę (w kodzie jest mała literówka, brakuje litery ń), twoje wymagania są troszkę inne więc musisz nad tym popracować.

Co mi tym... w wykreślankach jest odwrotny warunek - jak najmniej skrzyżowań, najlepiej wcale.

No to dziwna ta twoja wykreślanka, ale jak nie chcesz skrzyżowań to sorry, ale wtedy problem jest wtedy tak prosty, że nie warto zadawać pytania na forach.

Chyba żartujesz sobie.

Masz przykład:

Ale krzyżówki także mnie interesują - takie tematyczne, czyli z zadanego zbioru słówek, np. sport:
tenis, maraton, siatkówka, piłka, judo, zapasy, gigant, sprint, ciężary, szermierka, sanki, łyżwy, itd.

W tym przypadku zadanie jest następujące:
użytkownik określa maksymalne rozmiary diagramu, np. 12 x 15;
oraz podaje tę listę słówek, zwykle niewiele - z 30 powiedzmy, z której należy ułożyć krzyżówkę,
która używa maksimum słówek, oraz spełnia ogólne warunki krzyżówki.

Jaki jest ogólny schemat postępowania - przynajmniej zarys algorytmu, który wyprodukuje coś sensownego.