Linia łamana zamknięta

Mam planszę 7x7 kratek (kwadratów). Zadanie polega na narysowaniu linii łamanej zamkniętej łączącej środki kratek. Linie mogą być poprowadzone tylko pionowo lub poziomo. Nie musimy wykorzystywać wszystkich środków kratek. Jak przeiterować się po wszystkich tego typu liniach łamanych zamkniętych dla
a) lini, która może przecinać samą siebie (nawet wielokrotnie)

b) lini, która nie może przecinać samą siebie

W przypadku b) można wykorzystać krzywą Hilberta.

SkrzydlatyWąż napisał(a):

W przypadku b) można wykorzystać krzywą Hilberta.

Chodzi o wszystkie przypadki takich lini, a i nie może mieć końca i początku - linia ma być zamknięta.

Czy zadanie na 100% polega na tym żeby wygenerować wszystkie kombinacje takiej linii?

katakrowa napisał(a):

Czy zadanie na 100% polega na tym żeby wygenerować wszystkie kombinacje takiej linii?

Odnośnie do punktu b) pod tym linkiem jest pełna treść zadania. Zastanawiałem, czy można napisać do tego program. Iterowanie po wszystkich liniach łamanych to jeden z pomysłów. Chociaż w tej chwili wydaje mi się, że to słaby pomysł, bo przy takim podejściu stopień komplikacji jest podobny do problemu komiwojażera.

adam_qwe napisał(a):

katakrowa napisał(a):

Czy zadanie na 100% polega na tym żeby wygenerować wszystkie kombinacje takiej linii?

Odnośnie do punktu b) pod tym linkiem jest pełna treść zadania. Zastanawiałem, czy można napisać do tego program. Iterowanie po wszystkich liniach łamanych to jeden z pomysłów. Chociaż w tej chwili wydaje mi się, że to słaby pomysł, bo przy takim podejściu stopień komplikacji jest podobny do problemu komiwojażera.

Coś czułem, że to zadanie rodem z "ligi szarych komórek" " :-)
Właśnie dlatego pytałem o pełną treść zadania.

adam_qwe napisał(a):

Zastanawiałem, czy można napisać do tego program. Iterowanie po wszystkich liniach łamanych to jeden z pomysłów. Chociaż w tej chwili wydaje mi się, że to słaby pomysł, bo przy takim podejściu stopień komplikacji jest podobny do problemu komiwojażera.

Można. Ja ponieważ mam ogarnięte to wykorzystałbym algorytmy genetyczne. Wcześniej jednak bym pomyślał czy na 100% nie da się tego ugryźć analitycznie.
Trzeba by najpierw oszacować ilość kombinacji takich krzywych spełniających warunki ... Być może to jakaś przeliczalna wartość.

katakrowa napisał(a):

adam_qwe napisał(a):

katakrowa napisał(a):

Czy zadanie na 100% polega na tym żeby wygenerować wszystkie kombinacje takiej linii?

Odnośnie do punktu b) pod tym linkiem jest pełna treść zadania. Zastanawiałem, czy można napisać do tego program. Iterowanie po wszystkich liniach łamanych to jeden z pomysłów. Chociaż w tej chwili wydaje mi się, że to słaby pomysł, bo przy takim podejściu stopień komplikacji jest podobny do problemu komiwojażera.

Coś czułem, że to zadanie rodem z "ligi szarych komórek" " :-)
Właśnie dlatego pytałem o pełną treść zadania.

Takie hobby, jestem na urlopie i trochę mi się nudzi. Zamiast rozwiązywać takie zadanie, jak Bóg przykazał „na piechotę” zastanawiam się jak napisać do tego program. (oczywiście tylko do tych gdzie stanowi to wyzwanie), ale to zadanie jest wyjątkowo perfidne i nie mam za bardzo pojęcia jak się za nie zabrać.

katakrowa napisał(a):

adam_qwe napisał(a):

Zastanawiałem, czy można napisać do tego program. Iterowanie po wszystkich liniach łamanych to jeden z pomysłów. Chociaż w tej chwili wydaje mi się, że to słaby pomysł, bo przy takim podejściu stopień komplikacji jest podobny do problemu komiwojażera.

Można. Ja ponieważ mam ogarnięte to wykorzystałbym algorytmy genetyczne. Wcześniej jednak bym pomyślał czy na 100% nie da się tego ugryźć analitycznie.
Trzeba by najpierw oszacować ilość kombinacji takich krzywych spełniających warunki ... Być może to jakaś przeliczalna wartość.

Jak by zastosować brute-force to każdą kratkę (przy brzegach trochę mniej) można wypełnić na 7 sposobów, co daje liczbę wszytkich możliwości 7^(10*10) = 3234476509624757991344647769100216810857203198904625400933895331391691459636928060001 trochę duzo :)

Ja bym to zrobił deklaratywnie w jakimś ILP.
Edycja: Zaimplementowałem przykład b i czas działania to jakiś ułamek sekundy.

Na mój gust, słowa kluczowe dla Google'a to będą "hamilton cycle on lattice". Prowadzi to do różnych interesujących wyników, na przykład self-avoiding walks. Z grubsza patrząc na rezultaty wydaje się, że zadany problem jest raczej trudny.