Dlaczego niektóre układy w sortowaniu kul nie mają rozwiązania

Układ, ruch i ułożenie: trzy pojęcia, od których wszystko się zaczyna

Układ to zdjęcie całej planszy w jednej chwili: które kule leżą w której probówce i w jakiej kolejności. Dwa układy różnią się, jeśli choć jedna kula leży gdzie indziej. Na starcie poziomu jest dokładnie jeden układ, a każdy ruch zamienia go w inny.

Ruch to przełożenie kul z wierzchu jednej probówki do drugiej. Kula może trafić na kulę tego samego koloru albo do pustej probówki. Jeśli na wierzchu leży kilka kul tego samego koloru, przechodzą razem, tyle, ile zmieści probówka docelowa, i to wciąż jest jeden ruch. Pełne zasady opisuje strona gry Sortowanie Kulek.

Ułożenie to układ, w którym każda pełna probówka na 4 kule ma jeden kolor, a krótsze probówki, czyli bufory na 2 i 3 kule, są puste. Bufor nigdy nie zostaje ułożony, bo pełny kolor liczy 4 kule. Probówki są takie same, więc ten sam podział kolorów może wypaść w różnych probówkach: już do najprostszego poziomu 1 prowadzi 59 różnych ułożonych układów.

Z tych trzech pojęć powstaje mapa całego poziomu. Każdy układ to punkt, a każdy możliwy ruch to strzałka do innego punktu. Taką mapę nazywa się grafem stanów. Obok widać pełny graf poziomu 1: 596 układów i 2 138 przejść między nimi. Złota kulka idzie od startu do ułożenia najkrótszą drogą, w 4 ruchy.

Ważna rzecz kryje się w samej zasadzie ruchu: nie każdy ruch da się odwrócić. Jeśli przełożysz czerwoną kulę na czerwoną, a w probówce, z której wyszła, na wierzchu zostanie żółta, czerwona już tam nie wróci jednym ruchem. Mapa ma więc strzałki w jedną stronę. To właśnie z nich biorą się miejsca, z których nie ma powrotu.

Ile układów ma jeden poziom

Liczba układów rośnie szybko z każdym kolorem i każdą probówką. Poziom 1 z 3 kolorami i 5 probówkami ma 596 układów. Poziom 8, ostatni w etapie Nauka, ma już 5 kolorów, 7 probówek i 68 933 układy. Etap Bufory zaczyna się znów od 3 kolorów (poziom 9: 1 241 układów), a nowością są w nim krótsze probówki. Największy jest poziom 22: 89 946 układów przy 6 kolorach i 8 probówkach.

• 599 082układy we wszystkich 24 poziomach
• 89 946układów ma poziom 22, największy
• 309ruchów to suma najkrótszych rozwiązań

Ułożeń jest przy tym niewiele. Poziom 24 ma 192 ułożone układy na 79 011, czyli mniej więcej jeden na 412. Poziom 22, największy, ma ich 135. Przekładanie kul bez planu to więc błądzenie po mapie, na której cele są nieliczne, a większość punktów to układy pośrednie. Nie trzeba jednak liczyć całej mapy w głowie: wystarczy kilka prostych zasad z porad na stronie gry i cierpliwość, bo każdy ruch można cofnąć.

Najdalszy układ poziomu 24 leży 33 ruchy od startu, licząc najkrótszą drogę, choć najkrótsze rozwiązanie ma tylko 21 ruchów. Mapa ma więc wiele zakamarków, w które można zajść, zanim wróci się na dobrą drogę. Na mapie obok kolor kropki mówi, ile ruchów dzieli dany układ od ułożenia: im cieplejszy, tym bliżej celu.

Takiej mapy nie da się sprawdzić okiem. Dlatego gra liczy ją sama: przy wejściu na poziom buduje mapę odległości w tle, a przycisk podpowiedzi wskazuje ruch, po którym zostaje o jeden ruch mniej do ułożenia. Kolejne poziomy przejdziesz w grze Sortowanie Kulek, z podpowiedzią i cofaniem bez limitu.

Jak to policzyliśmy: dwa przejścia po mapie

Pierwsze przejście idzie od układu startowego w przód. Program wykonuje każdy możliwy ruch, zapisuje każdy nowy układ dokładnie raz i powtarza to dla nowych układów, aż nie pojawi się żaden nowy. Tak powstaje pełna lista układów osiągalnych ze startu i wszystkich przejść między nimi. Dla poziomu 22 to 89 946 punktów.

Drugie przejście idzie od końca. Zaczyna od wszystkich ułożonych układów i cofa się po strzałkach: układ, z którego jeden ruch prowadzi do ułożenia, jest 1 ruch od celu; układ, z którego jeden ruch prowadzi do tamtego, jest 2 ruchy od celu, i tak dalej. Po tym przejściu każdy układ ma liczbę: ile ruchów zostało do ułożenia, gdy grasz najlepiej. Układ, do którego to przejście nie dotarło, nie ma drogi do ułożenia.

Ślepy zaułek a pułapka

Łatwo pomylić dwie różne rzeczy. Ślepy zaułek to układ, w którym nie ma żadnego ruchu: wszystkie wierzchy się kłócą, a wolnego miejsca brak. Widać go od razu, bo gra nie pozwala nic przełożyć. Pułapka jest groźniejsza: ruchy są, kule da się przekładać w kółko, ale każda dalsza droga prowadzi tylko do innych pułapek.

Wcześniejsze testy poziomów sprawdzały tylko ślepe zaułki i we wszystkich poziomach wychodziło zero. Dopiero drugie przejście, liczenie wstecz od ułożenia, pokazało, że jeden poziom ma pułapki, choć ślepych zaułków ma w nim 0.

Pułapka z poziomu 23: siedem ruchów do miejsca bez wyjścia

Wcześniejsza wersja poziomu 23 miała 55 971 układów, z czego 216 nie miało drogi do ułożenia. Najbliższa pułapka leżała 7 ruchów od startu. Poniżej możesz przejść tę drogę ruch po ruchu. Liczba obok mówi, ile ruchów zostało do ułożenia przy najlepszej grze.

Pierwsze 4 ruchy są idealne: odległość spada z 20 do 16. Piąty ruch oddala o jeden (17), szósty niczego nie zmienia (dalej 17). Siódmy ruch, z probówki 5 do 6, wygląda zwyczajnie: kula ląduje na kulę tego samego koloru. Po nim gra nadal pozwala wykonać 2 ruchy, ale obydwa prowadzą do kolejnych pułapek. Wszystkie 216 pułapek tworzy zamknięty obszar: kto do niego wejdzie, nie wyjdzie, dopóki nie cofnie ruchów.

W tym układzie bufor na 3 kule jest pełny niebieskich kul, w buforze na 2 leży zielona kula, a trzy pierwsze probówki wciąż mają po 4 kule w trzech kolorach. Program sprawdził każdy dalszy ruch i każdą dalszą serię ruchów: żadna nie kończy się ułożeniem.

Twój ruch: który ruch zamyka drogę?

To układ sprzed siódmego ruchu. Do ułożenia zostało 17 ruchów, a możliwych jest 8 ruchów. Siedem z nich zostawia drogę otwartą, jeden zamyka ją na zawsze. Wskaż probówkę, z której chcesz przełożyć kule, a potem probówkę docelową.

Pułapki nie widać, bo na planszy niczego jej nie zdradza. Kolory się łączą, ruchy są dozwolone, nic się nie blokuje. Pułapka to cecha przyszłości, a nie chwili: dopiero sprawdzenie wszystkich dalszych dróg pokazuje, że żadna nie kończy się ułożeniem. Dlatego w grze cofanie ruchów nie ma limitu, a podpowiedź zawsze liczy drogę do ułożenia od aktualnego układu.

Jak naprawiliśmy poziom 23

Od tamtej chwili każdy poziom musi spełnić nowy warunek: zero układów bez drogi do ułożenia, liczonych dwoma przejściami opisanymi wyżej. Sam brak ślepych zaułków już nie wystarcza.

Nowy poziom 23 zachował wszystko, co było w nim ważne: te same probówki, te same bufory na 3 i 2 kule, 6 kolorów i najkrótsze rozwiązanie w 20 ruchów. Zmienił się tylko układ kul w drugiej połowie probówek. Znalazło go pełne przeszukanie rodziny podobnych układów: z 10 420 sprawdzonych klas układów tylko jedna spełniła wszystkie warunki naraz. Losowe układy przy buforach na 3 i 2 kule nie dały ani jednego trafienia.

Bufory: kieszeń, która może się zatkać

Bufory pojawiają się od poziomu 9 i bardzo pomagają: można w nich odłożyć kulę, która blokuje dno innej probówki. Mają jednak tę samą zasadę co zwykłe probówki: przyjmują kulę tylko na kulę tego samego koloru albo wtedy, gdy są puste. Bufor wypełniony jednym kolorem staje się więc magazynem, który oddaje kule tylko na ten sam kolor. W pułapce z poziomu 23 bufor na 3 kule był pełny niebieskich kul. Dlatego porady na stronie gry mówią, żeby bufor trzymać jak najdłużej pusty.

Co to znaczy, gdy grasz

• W 24 poziomach nie da się utknąć na zawsze. Z każdego układu każdego poziomu istnieje droga do ułożenia.
• Cofanie nie ma limitu. Każdy ruch da się cofnąć, więc nawet długa błędna seria nie kończy partii.
• Podpowiedź liczy od Twojego układu. Wskazuje ruch z najkrótszej drogi, także wtedy, gdy wcześniej oddalisz się od niej.
• Finał ma limit. Poziom 24 da się ułożyć w 21 ruchów, a limit wynosi 28, więc zostaje 7 ruchów zapasu na błędy.

Jeśli wolisz zasady pokazane na planszy, zajrzyj do poradnika Jak grać w kulki: tak samo, krok po kroku, tłumaczy on zasady kulek 5 w linii. Wszystkie artykuły znajdziesz na stronie Artykuły.

Jak sprawdzamy każdy poziom

Sprawdzenie nie jest jednorazowe. Przy każdej zmianie gry automatyczny test buduje mapę każdego z 24 poziomów i sprawdza trzy rzeczy: czy z każdego układu jest droga do ułożenia, czy najkrótsze rozwiązanie ma tyle ruchów, ile podaje opis poziomu, i czy suma najkrótszych rozwiązań wynosi 309 ruchów. Jeśli którykolwiek warunek nie jest spełniony, zmiana nie trafi do serwisu.

Ta sama mapa służy grze na co dzień. Podpowiedź na poziomach 22–24 liczona osobno dla każdego naciśnięcia zajmowała do ćwierć sekundy, więc gra buduje mapę raz, w tle, zaraz po wejściu na poziom. Mapa zajmuje kilka megabajtów pamięci i buduje się w małych porcjach, żeby nie przerywać animacji.

Czytaj dalej