Witam,

Przejrzałem archiwum grupy, pogooglałem, ale wszystko wskazuje na to że
googlać nie umiem, bo nie wierzę żeby podobny temat nie był poruszany :)

Szukam algorytmu albo wręcz metody matematycznej (mam cały czas nieodparte
wrażenie, że problem da się rozwiązać na poziomie pierwszej klasy liceum) na
sprawdzenie zamkniętej pętli. Chodzi o jeden z elementów progamu
rozwiązującego łamigłówki SlitherLink (znane również jako Fences lub
Pokropek)

Mam daną tablicę dwuwymiarową, zawierającą informacje o każdym kwadraciku.
Wymiary x,y określają położenie kwadracika na płaszczyźnie, natomiast w
wartości zakodowane jest położenie kwadratu względem pętli (na zewnątrz lub
wewnątrz) i stan każdego z jego boków (Jedna z trzech wartości: jest/nie
ma/nie jest oznaczone)

Jak sprawdzić/policzyć czy np. narysowanie górnej krawędzi w kwadraciku na
pozycji 1,1 spowoduje domknięcie pętli.

Pozdrawiam,
Kiełpiś


--
Brzdeśniało już; ślimonne prztowie Tomasz Kiełpiński
Wyrło i warło się w gulbieży; a.k.a. "Kiełpiś"
Zmimszałe ćwiły borogowie Odpowiadając prywatnie,
I rcie grdypały z mrzerzy. usuń: FALSZYWY z adresu

do góry

'Twas brillig when Tomasz Kiełpiński wrote:
> Witam,
> Przejrzałem archiwum grupy, pogooglałem, ale wszystko wskazuje na to że
> googlać nie umiem, bo nie wierzę żeby podobny temat nie był poruszany :)
> Szukam algorytmu albo wręcz metody matematycznej (mam cały czas
> nieodparte wrażenie, że problem da się rozwiązać na poziomie pierwszej
> klasy liceum) na sprawdzenie zamkniętej pętli. Chodzi o jeden z
> elementów progamu rozwiązującego łamigłówki SlitherLink (znane również
> jako Fences lub Pokropek)
> Mam daną tablicę dwuwymiarową, zawierającą informacje o każdym
> kwadraciku. Wymiary x,y określają położenie kwadracika na płaszczyźnie,
> natomiast w wartości zakodowane jest położenie kwadratu względem pętli
> (na zewnątrz lub wewnątrz) i stan każdego z jego boków (Jedna z trzech
> wartości: jest/nie ma/nie jest oznaczone)
> Jak sprawdzić/policzyć czy np. narysowanie górnej krawędzi w kwadraciku
> na pozycji 1,1 spowoduje domknięcie pętli.
> Pozdrawiam,
> Kiełpiś

PS. Hobbystycznie, nie komercyjnie :)


--
Bzdrężyło. Szłapy maślizgajne Tomasz Kiełpiński
Bujowierciły w gargazonach a.k.a. "Kiełpiś"
Tubylerczykom spełły fajle, Odpowiadając prywatnie,
Humpel wyświchnął ponad usuń: FALSZYWY z adresu

do góry

Tomasz Kiełpiński <F...@p...onet.pl> writes:

> Witam,
>
> Przejrzałem archiwum grupy, pogooglałem, ale wszystko wskazuje na to
> że googlać nie umiem, bo nie wierzę żeby podobny temat nie był
> poruszany :)
>
> Szukam algorytmu albo wręcz metody matematycznej (mam cały czas
> nieodparte wrażenie, że problem da się rozwiązać na poziomie pierwszej
> klasy liceum) na sprawdzenie zamkniętej pętli. Chodzi o jeden z
> elementów progamu rozwiązującego łamigłówki SlitherLink (znane również
> jako Fences lub Pokropek)
>
> Mam daną tablicę dwuwymiarową, zawierającą informacje o każdym
> kwadraciku. Wymiary x,y określają położenie kwadracika na
> płaszczyźnie, natomiast w wartości zakodowane jest położenie kwadratu
> względem pętli (na zewnątrz lub wewnątrz) i stan każdego z jego boków
> (Jedna z trzech wartości: jest/nie ma/nie jest oznaczone)
>
> Jak sprawdzić/policzyć czy np. narysowanie górnej krawędzi w
> kwadraciku na pozycji 1,1 spowoduje domknięcie pętli.
>
> Pozdrawiam,
> Kiełpiś

Hmm. Czy nie dało by się potraktować tego jak grafu gdzie koszt
przejścia przez nieoznaczoną krawędz jest duży (np. X*Y*1000) a koszt
przejścia na przez zaznaczoną mały (np. 1)? Teraz szukasz optymalnej
drogi dla każdych z par punktów (tzn. 4 punkty więc 6 dróg) i znajdujesz
miminum. Jeśli wynosi ono X*Y*1000 (tzn przejście jest przez ten punkt)
to nie ma takiej pętli. Jeśli jest mniejsza to taka pętla istnieje.

Pozdrawiam

PS. Piszę tak jak rozumiem problem - nie znam tej łamigłówki.
--
I've probably left my head... somewhere. Please wait untill I find it.
Homepage (pl_PL): http://uzytkownik.jogger.pl/
(GNU/)Linux User: #425935 (see http://counter.li.org/)

do góry

'Twas brillig when Maciej Piechotka wrote:
> Tomasz Kiełpiński <F...@p...onet.pl> writes:
>> Witam,
>> Przejrzałem archiwum grupy, pogooglałem, ale wszystko wskazuje na to
>> że googlać nie umiem, bo nie wierzę żeby podobny temat nie był
>> poruszany :)
>> Szukam algorytmu albo wręcz metody matematycznej (mam cały czas
>> nieodparte wrażenie, że problem da się rozwiązać na poziomie pierwszej
>> klasy liceum) na sprawdzenie zamkniętej pętli. Chodzi o jeden z
>> elementów progamu rozwiązującego łamigłówki SlitherLink (znane również
>> jako Fences lub Pokropek)
>> Mam daną tablicę dwuwymiarową, zawierającą informacje o każdym
>> kwadraciku. Wymiary x,y określają położenie kwadracika na
>> płaszczyźnie, natomiast w wartości zakodowane jest położenie kwadratu
>> względem pętli (na zewnątrz lub wewnątrz) i stan każdego z jego boków
>> (Jedna z trzech wartości: jest/nie ma/nie jest oznaczone)
>> Jak sprawdzić/policzyć czy np. narysowanie górnej krawędzi w
>> kwadraciku na pozycji 1,1 spowoduje domknięcie pętli.
>> Pozdrawiam,
>> Kiełpiś
> Hmm. Czy nie dało by się potraktować tego jak grafu gdzie koszt
> przejścia przez nieoznaczoną krawędz jest duży (np. X*Y*1000) a koszt
> przejścia na przez zaznaczoną mały (np. 1)? Teraz szukasz optymalnej
> drogi dla każdych z par punktów (tzn. 4 punkty więc 6 dróg) i znajdujesz
> miminum. Jeśli wynosi ono X*Y*1000 (tzn przejście jest przez ten punkt)
> to nie ma takiej pętli. Jeśli jest mniejsza to taka pętla istnieje.
> Pozdrawiam
> PS. Piszę tak jak rozumiem problem - nie znam tej łamigłówki.

Dzięki Maćku za zainteresowanie.

Koncepcja brzmi dość ciekawie, ale (chyba?) nie spełnia moich oczekiwań.
Może spróbuję narysować o co chodzi?

Przykład I:
.___. .___.
| | | |
|1,1|2,1|3,1|
. .___. .
| |
|1,2 2,2 3,2|
.___.___. .


Przykład II:
. .___.___.
| |
|1,1 2,1 3,1|
. . . .
| |
|1,2 2,2 3,2|
.___.___. .

Z mojego punktu widzenia nie ma znaczenia czy brak linii wynika z ze stanu
"BRAK" czy ze stanu "NIE OZNACZONY" danej krawędzi kwadratu. W przykładzie
pierwszym umieszczenie linii na dole kwadratu 3,2 spowoduje zamknięcie pętli
(przy czym wszystkie kwadraty z wyjątkiem 2,1 będą wewnątrz tej pętli). W
drugim przypadku pętla pozostanie otwarta. Pętla nie rozgałęzia się
natomiast może na tym etapie rozwiązywania urywać się. Ogólnie można
powiedzieć, że chodzi o sprawdzenie czy istnieje jakakolwiek droga między
dwoma punktami.

Pozdrawiam,
Kiełpiś

--
Bzdr

do góry

Tomasz Kiełpiński <F...@p...onet.pl> writes:

> 'Twas brillig when Maciej Piechotka wrote:
>> Tomasz Kiełpiński <F...@p...onet.pl> writes:
>>> Witam,
>>> Przejrzałem archiwum grupy, pogooglałem, ale wszystko wskazuje na to
>>> że googlać nie umiem, bo nie wierzę żeby podobny temat nie był
>>> poruszany :)
>>> Szukam algorytmu albo wręcz metody matematycznej (mam cały czas
>>> nieodparte wrażenie, że problem da się rozwiązać na poziomie pierwszej
>>> klasy liceum) na sprawdzenie zamkniętej pętli. Chodzi o jeden z
>>> elementów progamu rozwiązującego łamigłówki SlitherLink (znane również
>>> jako Fences lub Pokropek)
>>> Mam daną tablicę dwuwymiarową, zawierającą informacje o każdym
>>> kwadraciku. Wymiary x,y określają położenie kwadracika na
>>> płaszczyźnie, natomiast w wartości zakodowane jest położenie kwadratu
>>> względem pętli (na zewnątrz lub wewnątrz) i stan każdego z jego boków
>>> (Jedna z trzech wartości: jest/nie ma/nie jest oznaczone)
>>> Jak sprawdzić/policzyć czy np. narysowanie górnej krawędzi w
>>> kwadraciku na pozycji 1,1 spowoduje domknięcie pętli.
>>> Pozdrawiam,
>>> Kiełpiś
>> Hmm. Czy nie dało by się potraktować tego jak grafu gdzie koszt
>> przejścia przez nieoznaczoną krawędz jest duży (np. X*Y*1000) a koszt
>> przejścia na przez zaznaczoną mały (np. 1)? Teraz szukasz optymalnej
>> drogi dla każdych z par punktów (tzn. 4 punkty więc 6 dróg) i znajdujesz
>> miminum. Jeśli wynosi ono X*Y*1000 (tzn przejście jest przez ten punkt)
>> to nie ma takiej pętli. Jeśli jest mniejsza to taka pętla istnieje.
>> Pozdrawiam
>> PS. Piszę tak jak rozumiem problem - nie znam tej łamigłówki.
>
> Dzięki Maćku za zainteresowanie.
>
> Koncepcja brzmi dość ciekawie, ale (chyba?) nie spełnia moich
> oczekiwań. Może spróbuję narysować o co chodzi?
>
> Przykład I:
> .___. .___.
> | | | |
> |1,1|2,1|3,1|
> . .___. .
> | |
> |1,2 2,2 3,2|
> .___.___. .
>
>
> Przykład II:
> . .___.___.
> | |
> |1,1 2,1 3,1|
> . . . .
> | |
> |1,2 2,2 3,2|
> .___.___. .
>
> Z mojego punktu widzenia nie ma znaczenia czy brak linii wynika z ze
> stanu "BRAK" czy ze stanu "NIE OZNACZONY" danej krawędzi kwadratu. W
> przykładzie pierwszym umieszczenie linii na dole kwadratu 3,2
> spowoduje zamknięcie pętli (przy czym wszystkie kwadraty z wyjątkiem
> 2,1 będą wewnątrz tej pętli). W drugim przypadku pętla pozostanie
> otwarta. Pętla nie rozgałęzia się natomiast może na tym etapie
> rozwiązywania urywać się. Ogólnie można powiedzieć, że chodzi o
> sprawdzenie czy istnieje jakakolwiek droga między dwoma punktami.
>
> Pozdrawiam,
> Kiełpiś

To dobrze chyba zrozumiałem. Przejściu po linii daj koszt równy np. 1 a po
braku X*Y*1000 (albo nie dawaj - to zapewne zależy od konkretnego
algorytmu

Jak masz taką sytłację:

.__. .__.
| | | |
| | | |
. .__. .
| |
| |
.__.__. .

I sprawdzasz dla dolnego kwadratu czy istnieje droga poza tą krawędzią i
jaką ma długość (istnieje inna droga <=> jest pętla).

Tutaj jest droga o długości 11 < 3*4*1000 = 12000 więc zamykamy pętle.

. .__.__.
| |
| |
. . . .
| |
| |
.__.__. .

Tutaj najkrótszą drogą jest 3*4*1000 (dokładnie przez 'nowo zaznaczone'
pole [Albo - nie ma drogi]) więc nie zamyka to pętli.

A algorytmów wyszukiwania drogi w grafie jest mnówtwo - choćby na
wikipedii.

Pozdrawiam

PS. Brak rozgałęzień to wiedza czy wymóg? Jeśli wiedza to można iść po
koleji zaznaczonymi krawędziami aż do końca. Jeśli wymóg to przypisz
drogom z rozgałęzienia koszt 3*4*1000/uczyń nieprzechadzalnymi.
--
I've probably left my head... somewhere. Please wait untill I find it.
Homepage (pl_PL): http://uzytkownik.jogger.pl/
(GNU/)Linux User: #425935 (see http://counter.li.org/)

do góry

Tomasz Kiełpiński wrote:
> Witam,
>
> Przejrzałem archiwum grupy, pogooglałem, ale wszystko wskazuje na to
> że googlać nie umiem, bo nie wierzę żeby podobny temat nie był
> poruszany :)
> Szukam algorytmu albo wręcz metody matematycznej (mam cały czas
> nieodparte wrażenie, że problem da się rozwiązać na poziomie
> pierwszej klasy liceum) na sprawdzenie zamkniętej pętli. Chodzi o
> jeden z elementów progamu rozwiązującego łamigłówki SlitherLink
> (znane również jako Fences lub Pokropek)
>
> Mam daną tablicę dwuwymiarową, zawierającą informacje o każdym
> kwadraciku. Wymiary x,y określają położenie kwadracika na
> płaszczyźnie, natomiast w wartości zakodowane jest położenie kwadratu
> względem pętli (na zewnątrz lub wewnątrz) i stan każdego z jego boków
> (Jedna z trzech wartości: jest/nie ma/nie jest oznaczone)
>
> Jak sprawdzić/policzyć czy np. narysowanie górnej krawędzi w
> kwadraciku na pozycji 1,1 spowoduje domknięcie pętli.


Punkty siatki sa weirzcholkami grafu, oznaczone na 'tak'
kreski są krawedziemi grafu.

Zalozmy, ze dorysowujesz krawedz miedzy wierzcholkami
a i b ( (n,m) --- [(n+1,m) lub (n,m+1)] )

Kiedy zamykami petle? Wtedy, gdy _przed_ dodaniem
naszej krawedzi istnieje polaczenie miedzy a i b.

Wystarczy wiec, ze sprawdzisz, czy istnieje polaczenie
miedzy a i b. Jest to dosc czesto spotykane zagadnienie;)
Algorytm nazywa sie 'przeszukiwanie drzewa w szerz'
(Breadth-first search, w skrócie BFS) jest dobrze
opisany w ksiezkach i sieci. Dlaczego 'w szerz' a nie
'w glab'? ze wzgledu na pesymistyczna ilosc operacji.
Jesli najkrotsza sciazka ma dlugosc L, to odwiedzisz
nie wiecej niz max(4L^2,M) a M to liczba wierzcholkow
do ktorych mozesz dojsc;)
Algorytm zybszy i prostrzy w implementacji niz proponowana
obok Dijkstra, potrzebujesz jedynie kolejki fifo, czyli
zwyklej listy.


Bieresz element z kolejki i wrzucasz do kolejki
wszyskich sasiadow (wierzcholki, do ktorych masz bezposrednie
polaczenie krawedzią 'tak'), przy okazji sprawdzajac,
czy to nie jest nasz cel i czy nie byl 'odhaczony' (tych
nie wrzucasz). Wrzucane wierzcholki zaznaczamy jako 'odhaczone'

W pierwszym kroku wrzucasz do kolejki wierzcholek startowy.


BTW, Mozna to jeszcze zbic (do 2L^/2) idac na zmiane jedno
pietro z wierzcholka 'a' - jedno pietro z wierzcholka 'b'
i czekac na spotkanie, ale algorytm robi sie ciut bardziej
skomplikowany.


pzodrawiam
bartekltg

do góry

'Twas brillig when bartekLTG wrote:
[...]
> Punkty siatki sa weirzcholkami grafu, oznaczone na 'tak'
> kreski są krawedziemi grafu.
> Zalozmy, ze dorysowujesz krawedz miedzy wierzcholkami
> a i b ( (n,m) --- [(n+1,m) lub (n,m+1)] )
> Kiedy zamykami petle? Wtedy, gdy _przed_ dodaniem
> naszej krawedzi istnieje polaczenie miedzy a i b.
> Wystarczy wiec, ze sprawdzisz, czy istnieje polaczenie
> miedzy a i b. Jest to dosc czesto spotykane zagadnienie;)
> Algorytm nazywa sie 'przeszukiwanie drzewa w szerz'
> (Breadth-first search, w skrócie BFS) jest dobrze
> opisany w ksiezkach i sieci. Dlaczego 'w szerz' a nie
> 'w glab'? ze wzgledu na pesymistyczna ilosc operacji.
> Jesli najkrotsza sciazka ma dlugosc L, to odwiedzisz
> nie wiecej niz max(4L^2,M) a M to liczba wierzcholkow
> do ktorych mozesz dojsc;)
> Algorytm zybszy i prostrzy w implementacji niz proponowana
> obok Dijkstra, potrzebujesz jedynie kolejki fifo, czyli
> zwyklej listy.
> Bieresz element z kolejki i wrzucasz do kolejki
> wszyskich sasiadow (wierzcholki, do ktorych masz bezposrednie
> polaczenie krawedzią 'tak'), przy okazji sprawdzajac,
> czy to nie jest nasz cel i czy nie byl 'odhaczony' (tych
> nie wrzucasz). Wrzucane wierzcholki zaznaczamy jako 'odhaczone'
> W pierwszym kroku wrzucasz do kolejki wierzcholek startowy.
> BTW, Mozna to jeszcze zbic (do 2L^/2) idac na zmiane jedno
> pietro z wierzcholka 'a' - jedno pietro z wierzcholka 'b'
> i czekac na spotkanie, ale algorytm robi sie ciut bardziej
> skomplikowany.
> pzodrawiam
> bartekltg

Bartku, Maćku,

Dzięki za cenne uwagi. Poczytałem o BFS (a przy okazji innych algorytmach
związanych z grafami) i przemyślałem wasze propozycje. W efekcie końcowym
zdecydowałem się na uproszczone (ze względu na zasady łamigłówki)
rozwiązanie. Poniżej pseudo algorytm:

1.Ustaw koordynaty wierzchołka A jako początkowe, wierzchołka B jako
końcowe. Wyklucz odcinek AB
2.PETLA:
- sprawdź wszystkie narysowane odcinki z początkowego wierzchołka.
- wybierz pierwszy niewykluczony
- jeśli nie ma niewykluczonego odcinka:
- jeśli koordynaty bieżącego wierzchołka i wierzchołka B są zgodne to
PETLA ZAMKNIĘTA,
jeśli nie to PETLA OTWARTA. Wyjdź z funkcji.
- w przeciwnym razie:
- przejdź do nowego wierzchołka
- wyklucz pokonany właśnie odcinek
- ustaw nowe koordynaty początkowe
- wróć na początek pętli

Pozdrawiam,
Kiełpiś




--
Był czas mrutszławy, ślibkie skrątwy Tomasz Kiełpiński
Na wałzach wiercząc świrypły, a.k.a. "Kiełpiś"
A mizgłe do cna borogłątwy Odpowiadając prywatnie,
I zdomne świszczury zgrzypły. usuń: FALSZYWY z adresu

do góry