Generowanie krzyżówek

0

Właśnie przymierzam się do zagadnienia zawartego w temacie.... by z zadanego zbioru wyrazów ułożyć (wygenerować) krzyżówkę.... dla mnei jest to zadanei z kategorii bardzo ambitne (dla Was pewnie nie ;) ), ale bardzo chciałbym owy problem rozwiązać... a by to zrobić jakiś plan działania muszę mieć...

dodam że chodzi o krzyżówkę najprostszą (nie panoramiczna)
http://www.nienacki.art.pl/galeria/nienacki/artykuly/rewia_rozrywki_lektury_nadobowiazkowe_krzyzowka.gif

czy ktoś ma przemyślany problem generowania krzyżowek... chodzi o algorytm postępowania lub materiały które moga pomóc...

podejrzewam że pierwszy logiczny krok to znalezienei najdłuższego wyrazu ze zbioru, a potem jakies sortowanei zbioru z uwzględnieniem jakiś statystyk literowych...

...z góry dzięki...

0
  1. wez olowek i kartke
  2. wyposaz sie w duze ilosci napoju i weglowodanow
  3. stworz dowolna krzyzowke z haslem
  4. poloz sie spac
  5. powtorz czynnosc od 2 do 5 az do osiagniecia celu
  6. opisz algorytm
  7. przelej swoja ekspresje do jakiegos jezyka programowania
  8. idz i przedstaw swoje dzielo wykladowcy

to powinno pomoc

PS. Nie zaczynaj od implementacji, chyba ze masz ogromna wyobraznie.

0

@si3ma, opuściłeś bardzo ważny krok

  • zainstaluj program prezydent, wpisujesz np. p***nie i dostajesz taką odpowiedź:

PADANIE PASANIE PCHANIE PĘKANIE PĘTANIE PIKANIE PILENIE PIRANIE
PISANIE PODANIE POLANIE PUKANIE PYKANIE PYLENIE PYTANIE

0

Moja propozycja jest inna:

1.Tworzysz pustą krzyżówkę(dowolnie)
2.Używasz brute-force do wstawienia słów ze słownika tak, żeby pasowały
3.Zadajesz pytania pasujące do słów
4.Ustalasz miejsca w których mają być liczby określające litery hasła

Czasem warto jest zacząć od końca.

0
Karton napisał(a)

1.Tworzysz pustą krzyżówkę(dowolnie)
2.Używasz brute-force do wstawienia słów ze słownika tak, żeby pasowały

To jest wykonalne w sensownym czasie?

0

To zależy od skomplikowania diagramu. Dla tego się chyba dauser image

0

Ale to nie jest krzyżówka.

0

Dlaczego?

0

Bo w krzyżówce każde słowo musi się wiązać z innymi co najmniej dwiema literami. Inaczej to by trochę bez sensu było.

0

Moja propozycja diagramu nie była całkiem serio, też uważam że realistycznej krzyżówki nie ułoży się metodą brute-force w akceptowalnym czasie. Dodatkowo, uważam że słowa w krzyżówce winny być znane (ale określenia niebanalne), trudno spełnić ten warunek przy metodzie brute-force. Trzeba by chyba rozpocząć od przypisania każdemu słowu liczby - miary akceptowalności.

0
somekind napisał(a)
Karton napisał(a)

1.Tworzysz pustą krzyżówkę(dowolnie)
2.Używasz brute-force do wstawienia słów ze słownika tak, żeby pasowały

To jest wykonalne w sensownym czasie?

Wszytko zależy od stopnia skomplikowania, słownika i sprzętu.

Przeciętną krzyżówkę używając jakiegoś ograniczonego(np bez fachowych słów lub same informatyczne) słownika można by tak zrobić.
Zawsze słownik można podzielić na kilka pod względem długości i przeszukiwać tylko ten którego długość pasuje.
Wg tej strony http://poradnia.pwn.pl/lista.php?id=5606 słów jest co najmniej 350k.
Nawet jeżeli jest ich nawet 700k to po podzieleniu wcale nie stanowi to jakiejś zawrotnej liczby.
Poza tym jeżeli zostawić tylko formy podstawowe liczba ta znacznie spadnie.

Jeżeli nie chcesz aby hasła były ogólne lub masz co do nich jakieś specjalne wymagania to:
krok0: Dobranie odpowiedniego słownika.

Wydaje mi się, że programy do skrabli tak właśnie robią, ale pewności nie mam.

0
bo napisał(a)

Trzeba by chyba rozpocząć od przypisania każdemu słowu liczby - miary akceptowalności.

Ale jak ją wyznaczyć? Trzeba by chyba zrobić chyba ankietę wśród ludzi z pytaniem czy znają dane słowo, i wybrać te najczęściej wybierane...

Karton napisał(a)

Nawet jeżeli jest ich nawet 700k to po podzieleniu wcale nie stanowi to jakiejś zawrotnej liczby.
Poza tym jeżeli zostawić tylko formy podstawowe liczba ta znacznie spadnie.

Ile różnych krzyżówek można ułożyć mając do dyspozycji 10 słów siedmioliterowych?

0

Z 10. słów można by ułożyć całkiem sporo(imo >5k) krzyżówek.
Nie bardzo widzę jednak związek.

W tym przypadku nie robiło by się żadnych permutacji czy kombinacji a jedynie dopasowywało słowo po słowie czyli przypadków było by dużo mniej(bo szukając następnego słowa opieralibyśmy się na literach z poprz4edniego) mniej niż x o y, gdzie:
x -liczba słów w słowniku
o -dolna silnia
y -liczba haseł

1 użytkowników online, w tym zalogowanych: 0, gości: 1