algorytm do układania krzyżówki

Chodzi o proste krzyżówki tematyczne, czyli układane z zadanego niedużego zbioru słówek - kilkaset sztuk góra.

Przykładowo: bierzemy nazwy drzew, albo ryb, i robimy z tego krzyżówkę o zadanym maksymalnym rozmiarze, np. 10x12 kratek.

Wynik wygląda zazwyczaj tak:

nie chodzi mi oczywiście o rysowanie tego w taki sposób, a jedynie o utworzenie samej krzyżówki... z zadanych słówek.

Zwyczajną krzyżówkę, tj. z dowolnych słów pospolitych, znacznie łatwiej zrobić:

Ja coś czuję, że to śmierdzi słownikiem z posortowanym kontentem według długości, każda długość sortnięta po alfabecie i kończy się to na wyszukaniu randomowego wyrazu spełniającego aktualnie zamierzone kryteria dotyczące danej prostej.

Jaki hajs przewidziany na to zadanie?

Jaki język uznajesz za stosowny?

Nieposkromiony Pomidor napisał(a):

Ja coś czuję, że to śmierdzi słownikiem z posortowanym kontentem według długości, każda długość sortnięta po alfabecie i kończy się to na wyszukaniu randomowego wyrazu spełniającego aktualnie zamierzone kryteria dotyczące danej prostej.

Nie mam pojęcie co i jak sobie tam będziesz tworzył.

na wejściu masz: listę słówek np. 50, czy 200 sztuk, powiedzmy że limit = 5000,
oraz matrycę NxM (maks. 50x50), w którą masz wpakować krzyżówkę, używając maksymalnie dużo słówek.

Na wyjściu ma być lista słówek gotowej krzyżówki:
słowo, jego pozycja początkowa (x,y) oraz kierunek poziomo/pionowo.

Jaki hajs przewidziany na to zadanie?

Chyba tak ze 100 zł, bo chodzi o malutki algorytm - z 20 instrukcji, czyli z strona co najwyżej.

Jaki język uznajesz za stosowny?

Chodzi o algorytm w ogólnej postaci, czyli taki opis - schemat postępowania...
można użyć schemat blokowy, albo jakiś tam dowolny ogólny slang typy: paskal, c/c++, java, itp.

Do zaimplementowania tego powinien zostać zastosowany algorytm z dziedziny spełniania ograniczeń. Wykonanie wzorowego rozwiązania jest trudniejsze niż się wydaje.

finalsrebrny napisał(a):

Do zaimplementowania tego powinien zostać zastosowany algorytm z dziedziny spełniania ograniczeń. Wykonanie wzorowego rozwiązania jest trudniejsze niż się wydaje.

Nie chodzi o jakiś tam super-perfekt program do krzyżówek (taki jak np. mój Kretor Krzyżówek),
lecz o taki leciutki algorytm, który będzie produkował takie małe krzyżóweczki ze słówek wpisywanych ręcznie.

Ogólna procedura może wyglądać tak:

1. wpisujemy te swoje słówka, np. imiona, albo nazwy państw, itp.
2. ustawiamy rozmiar diagramu, np. 10x12 kratek
3. puszczamy ten algorytm, no i on produkuje - próbuje wstawiać losowo różne słówka,
   tak aby się krzyżowały, oczywista (minimum 2 razy... bo taki jest warunek krzyżówki);
   gdy wstawił np. 20 słówek a więcej już nie można dopasować, no to zapisuje to sobie i zaczyna od nowa - i tak 1000 razy (kilka sekund, czy minuta).
4. finalnie drukuje najlepsze rozwiązanie, które znalazł, tz., to w którym jest najwięcej słówek (ewentualnie liter, albo skrzyżowań...).

Można próbować użyć coś bardziej zaawansowanego - pewnie lepiej zadziała od czyste losówki,
np. algorytm genetyczny czy coś pokrewnego. :)