Obrazki logiczne - algorytm

0

Wszyscy juz chyba znamy japońskie Sudoku. Ostatnio zetknąłem się z czymś innym, wcale nie nowym, ale czymś co mnie zaciekawiło.

W kiosku znalazłem "Obrazki logiczne" wydawnictwa Logi. Całkiem przyjemna sprawa - polega na zamalowywaniu planszy wg cyfr podających które pola pomalować. Wynikiem jest obrazek. Przykład poniżej:

user image

Tak jak na temat Sudoku można znaleźć masę przeróżnych informacji na temat sposobu rozwiązywania tak na temat tych obrazków jest nadal ubogo. Konkretnie zainteresowało mnie jak rozwiązać taki obrazek przy pomocy komputera?? Słyszał ktos o jakimś algorytmie?? Tudzież zna jakiś sposób??

Kurcze, obrazka nie pokazało:| Oto link do przykładu dla zainteresowanych: http://www.obrazkilogiczne.pl/ro00502.jpg

0

To był jeden z projektów do wykonania w Clipsie na zajęciach - są 2 wersje tych obrazków.
Jednak wykładowca nie podał nazwy tego.. taki mało wnoszący post.

[możesz edytować swoje posty]

0

No ja jestem na niższym etapie edukacji - ogólniak. Co nieco słyszałem, że to może na grafach byłoby do zrobienia, ale nie bardzo wiem jak (???)

0

Rozpatrzyć wszystkie przypadki? :)

0
Jame napisał(a)

Rozpatrzyć wszystkie przypadki? :)
Szalony.. dla tego przykładowego małego obrazka wszystkich kombinacji jest 2500 - a dla większych? zgroza...

0

Na wykładach na których listy były puszczane, więc trzeba było być, u nas się rozwiązywało :P

Kiedyś sprzeczaliśmy się, czy da się zrobić, aby komputer mógł to sam ułożyć.

Miałem napisać w wolnej chwili coś do tego, ale wolna chwila się nie znalazła :P

Ogólnie wcale nie jest tak źle z kombinacjami, ponieważ jest tutaj wiele ograniczeń. Ale i tak brute force jest nieeleganckim sposobem na rozwiązywanie tego.

Tak na chłopski rozum należałoby zacząć wyszukiwanie od linii, która ma największy stopień wypełnienia, przy czym należy pamiętać, że jeżeli mamy pojedyncze kawałki, to trzeba doliczyć "puste" pola, które muszą rozdzielać te elementy (np. na obrazku w lini 2,2 mamy stopień wypełnienia co najmniej 5).

Wówczas, przy zastosowaniu wszystkich możliwych kombinacji, pomimo, że wciąż mamy problem o czasie wykładniczym, to współczynniki są w miarę niewielkie i można zapuścić program do liczenia.

Oczywiście możnaby dodać jeszcze dodatkowe ograniczenia preferujące pewne rozwiązania, jak np. wymóg, aby każda kratka sąsiadował z chociażby jednym punktem (może być po przekątnej), aby obraz był spójny.

Życzę powodzenia. Jeżeli coś uda Ci się wymyśleć, to daj znać.

0

Ha, nie tak źle z moją pamięcią :P
http://4programmers.net/file.php?id=1885
Jednak 4p to niespodziewanie duże archiwum. :]

0

spox. zapoznalem sie z kodem :) szkoda ze nie ma komentow, bo pomimo ze probowalem analizowac na kartce jakis konkrenty przyklad to nie bardzo rozumiem ten sposób. Może się ktoś bardziej łapie o co biega?

0

Przecież to razwala zwykły układ równań liniowych, a do tego jest z milion algorytmów! :D

0

Dostalem wlasnie takie zadanie do rozwiazania na studiach(I rok inf). W pon. powinienem byc gotowy to wstawie kod zrodlowy. Pozdro;)

0
gruby napisał(a)

Przecież to razwala zwykły układ równań liniowych, a do tego jest z milion algorytmów! :D

pokaz mi w ktorym miejscu masz uklad rownan liniowych bo jakos ja tam tego nie widze :)

ad. 2 wydaje ort! ze systemu jako takiego dla kazdego rysunku nie ma z tego wzgledu ze liczba kombinacjii jest za duza aby jakas liste kroków wyprowadzic ktora to policzy . Chyba ze sposobem na piechote a to jest dosc duzo kombinacjii :)

pozdrawiam :0

// wydajesz misie? zooalfons... zobacz jak stary jest ten temat. (dop. deus)

0

mumia nie watek!!

jaki uklad rownan liniowych? alez prosze, taki banalny przyklad mapowania:
| 0 | 2 | 1

1| | |
2| | |
0| | |

kazda komorka przyjmuje wartosci 0 lub 1. 0 oznacza puste, 1 oznacza pelne. a wiec, liczba na poczatku wiersza/kolumny oznacza liczbe jedynek w wierszu/kolumnie. nazwijmy komorki:

| 0 | 2 | 1

1| A | B | C
2| D | E | F
0| G | H | I

tak wiec, skoro komorki maja wartosci 0/1, to mamy:
poziomo:
1 = A+B+C
2 = D+E+F
0 = G+H+I
pionowo:
0 = A+D+G
2 = B+E+H
1 = C+F+I

i mamy uklad rownan 9 zmiennych, 6 zwiazkow.
dla pewnych ukladow moze sie okazac ze po uprosczeniu rownan nie wszystkie zmienne zostana obliczone - nic w tym zlego, to tylko oznacza ze obrazek ma wiele rozwiazan (acz pewnie te niezamierzone beda wygladac okropnie). w takim przypadku, z racji 0/1 wartosci mozna sobie szybko wygenerowac wszystkie uklady spelaniajace warunki wolnych zmiennych

btw. a jesli pomyslec o optymalizacjach, takich jak przycinanie wejscia dzieki oczywstosciom, np:
0 = G+H+I => G=H=I=0
0 = A+D+G => A=D=G=0
\ ||| //
\|||//
1 = B+C
2 = E+F
0 = 0
pionowo:
0 = 0
2 = E+H
1 = F+I
to wszystko idzie jeszcze szybciej..

aa.. i pamiteac ze a,b,c,d... to 0/1, zeby przypadkiem eni wyszlo w rozwiazaniu ze -3 albo 10 :)

0

tu: http://en.wikipedia.org/wiki/Nonogram jest trochę technik rozwiązywania. ogólnie efektywne rozwiązania polegają na użyciu rozmaitych heurez, a potem w razie konieczności przechodzić stopniowo do bruta (np: wybieranie jednego dwóch elementów i zakładanie ich stanu, a potem sprawdzanie czy nie dojdzie do sprzeczności)

atsd:
robiłem identyczny projekt (obrazki logiczne) na wstęp do programowania na pierwszym roku informatyki.

0

Jest polska strona z obrazkami: gamelo.net</url> - tam są opisane techniki rozwiązywania

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