PiSudoku
Zdarzają się łamigłówki, których forma zdecydowanie góruje nad treścią. Mają w sobie coś takiego, że zamiast rozwiązywać chciałoby się je oprawić w ramki i powiesić na ścianie jako perełki łamigłówkowego konceptualizmu. Jednym z przykładów tego, co mam na myśli, jest poniższe sudoku.
Tytuł wpisu wszystko wyjaśnia. Można podziwiać, ale rozwiązać jednak też warto, zwłaszcza że końcówka nie jest taka hop-siup. Warto także zwrócić uwagę, że wciśnięcie w diagram 32 cyfr (teoretycznie mogłoby ich być oczywiście mniej) było możliwe, ponieważ zero pojawia się w rozwinięciu dziesiętnym pi dopiero jako 32 cyfra po przecinku.
A pytania mam trzy:
Łatwe: jaka cyfra znajdzie się w lewym górnym rogu?
Trudne (żmudne): czy można przesunąć jakąś cyfrę (oczywiście bez psucia właściwej kolejności cyfr) tak, aby sudoku nadal miało jedno rozwiązanie? A jeśli tak, to którą i jak?
Problemowe: czy jest możliwe rozmieszczenie w diagramie sudoku cyfr tworzących rozwinięcie dziesiętne pi (kolejno rzędami od góry – jak w powyższym zadaniu; liczba cyfr nie jest ściśle określona) tak, aby ich układ był symetryczny (osią symetrii może być przekątna), a rozwiązanie było jedno?
PiSudoku jest dziełkiem holenderskiego łamigłówkarza Johana de Ruitera, twórcy i administratora wortalu PuzzlePicnic.
Komentarze
Panie Marku, pisałem o Pana tekstach dot. gier sprzed nie mała trzydziestu lat w biuletynie „Inspiracje”. Czy nie zechciałby Pan odpowiedzieć mi kilka moich pytań odnośnie tamtych czasów?
Tu jeden z kilku tekstów: http://gitgames.blogspot.co.uk/2014/02/historia-rpg-w-polsce-biuletyn.html
Najlepiej oczywiście na prv – borejko małpa gmail kropka com
Gdyby Pan zechciał się odezwać byłoby mi niezmiernie miło.
Odpowiedź na pytanie 1:
W lewym górnym rogu znajduje się cyfra 5.
Ogólnie cały diagram wygląda tak:
597823614
386741592
142965873
621358947
459617328
738492156
265184739
974536281
813279465
Odpowiedź na pytanie 2:
Tak, można. Odpowiedź na to pytanie jest chyba nawet prostsza niż na pytanie 1, bowiem aby odpowiedzieć na pytanie 1 trzeba rozwiązać całą łamigłówkę, natomiast do twierdzącej odpowiedzi na pytanie 2 wystarczy poniższe spostrzeżenie.
Cyfra 3 w skrajnej prawej kolumnie jest nadmiarowa. Można ją zatem usunąć nie zmieniając jednoznaczności rozwiązania. Usuniętą cyfrę 3 można bezkarnie umieścić w górnym rzędzie środkowego kwadratu. Bezkarnie, bowiem umieszczenie jej w tym miejscu i tak wynika z pozostałych danych. Układ liczby PI nie pozostaje naruszony.
Warto zwrócić uwagę, że powyższy przykład potwierdza tylko twierdzącą odpowiedź na pytanie 2, natomiast w ogóle nie wyjaśnia czy można (i na ile sposobów) wykonać przesunięcia innych cyfr.
Odpowiedź na pytanie 2 – kontynuacja.
Istnieją 4 sposoby przesunięcia jednej cyfry tak, aby rozwiązanie pozostało jednoznaczne oraz układ liczby PI nienaruszony:
* cyfrę 4 z 1 rzędu do 2 rzędu i 5 kolumny
* cyfrę 2 z 2 rzędu do 3 rzędu i 3 kolumny
* cyfrę 3 z 3 rzędu do 4 rzędu i 4 kolumny
* cyfrę 8 z 8 rzędu do 9 rzędu i 1 kolumny
W przypadku przesunięcia cyfry 3 łatwo podać argument, że diagram pozostaje jednoznaczny (było w poprzednim komentarzu).
W pozostałych przypadkach jednoznaczność potwierdziłem komputerowo i nie próbowałem szukać argumentów łatwych do ogarnięcia umysłem ludzkim (choć nie twierdzę, że takie nie istnieją).
Ad łatwe: 5
Ad średnie:
Można przesunąć 6 w rzędzie nr 3
592783614
387641592
641925873
126358947
459167328
738492156
265814739
974536281
813279465
lub
592783614
387641592
146925873
621358947
459167328
738492156
265814739
974536281
813279465
Z powyższych 2 rozwiązań pierwsze ma rozwiązanie jednoznaczne, drugiego nie sprawdzałem.
5 🙂
Stworzyć takie sudoku to dość proste zadanie (trudniej jest wpaść na taką ideę).
1.W lewym górnym jest 5.
2.Można przesunąć 5 w czwartym wierszu do drugiej kratki. Drugim rozwiązaniem jest przeniesienie 6 w trzecim wierszu do pierwszej lub trzeciej kratki.
3.Sudoku z osią symetrii przez środek diagramu.
3xxx1xxx4
1x5xxx9x2
x6xx5xx3x
58xxxxx97
xx9x3x2xx
xx38x46xx
2x6xxx4x3
xxx3x8xxx
x3xx2xx7x
Kolejna cyfra w ostatnim rzędzie też zgodna z rozwinięciem PI. Nie wiem czy można w symetrycznym sudoku użyć 32 cyfry.
Pytanie 3 nawet z pomocą komputera wydaje się bardzo trudne. Program który wygeneruje wszystkie symetryczne pisudoku (jeśli istnieją) jest bardzo prosty do napisania, jednak jego czas działania jest bardzo niezadowalający. Moje pierwsze próby dają oszacowanie na czas działania kilka miesięcy. Oczywiście można go usprawnić pomijając z rozważania ogromną liczbę diagramów, które ze względu na właściwości ciągu cyfr dziesiętnej wartości PI są skazane na porażkę, jednak to strasznie komplikuje logikę jego działania.
Pozostawiam sobie ten problem w pamięci i obiecuję powrócić do niego w wolnej chwili. Jak uzyskam jakieś ciekawe wyniki, to oczywiście wspomnę o tym w komentarzach do przyszłych wpisów 🙂
Oczywiści szukając symetrycznych pisudoku zafixowałem się przy zachęcie do poszukania diagramów symetrycznych względem przekątnej.
Tymczasem po głębszej chwili zastanowienia dochodzę do wniosku, że najprostsze do wygenerowania są diagramy symetryczne względem pionowej osi.
Oto lista wszystkich (jest ich 418) pisudoku symetrycznych względem osi pionowej: http://www.gg.pl/dysk/CIPDIcSzfj9QCYPDIcSzbhY/symetryczne%201.txt
Usprawnienia w programie pomogły przyspieszyć również generator diagramów symetrycznych względem przekątnej – jednak tutaj na pełne wyniki musimy poczekać… jest szansa, że w poniedziałek rano będą kompletne wyniki. Na chwilę obecną mam już ok. 200 diagramów symetrycznych względem jednej przekątnej oraz 4 diagramy symetryczne względem drugiej 😉
Najciekawsze są te z minimalną i maksymalną liczbą cyfr.
mp
Po godzinie pracy mój komputer wyprodukował coś takiego:
..31.4…
.1.5…9.
2….6.5.
35…….
…..89..
7.9.3….
….2..3.
.84…6..
………
po 8 godzinach pracy komputer znalazł ponad 43 tysięcy rozwiązań, w tej chwili produkuje ich kilka na sekundę, a przeszukał zaledwie nanofragment dopuszczalnej przestrzeni rozwiązań.
Kilka przykładów:
pięć pod rząd:
.3..1….
41592….
.6….53.
.5….8.9
79……3
………
..23…84
..6…2..
…64.3..
prawie zero:
……31.
..415….
.9…2…
.6…5..3
.5..89..7
..932….
3……8.
4…..6.2
…64..3.
wstęga:
……31.
.4…15..
….92…
…65…3
..58.9..7
.93.2….
38…….
4…….6
…26..4.
trzy puste klatki:
…..3.14
….159..
…….2.
……653
.5…..8.
97…….
.9.3…..
2.384….
6..2…..
12 rozwiązań z 20 cyframi
(mniej prawie na pewno nie ma przy symetrii względem głównej przekątnej, ale żeby uzyskać pewność, trzeba by lekko zmodyfikować program):
…..3.1.
…..4…
..1…5..
…92…6
…5..3..
58……9
..7.9….
3…….2
…3.8.4.
3..1.4…
.1…..59
…2…..
6.5.3….
…5..8..
9…..7..
….93…
.2……3
.8…..4.
…3.1..4
.1…5…
……9.2
6..5…..
…….35
89…….
..7……
….9…3
2.3.8..4.
….3..1.
.4…….
…15.92.
..6…5..
3.5……
…..8..9
..79..3..
2.3….8.
…..4…
3……1.
..415….
.92……
.6.53….
.5.8…..
……9.7
…..9..3
2……..
…..38.4
.3.1…..
41.5…..
….9.2..
65…….
..3…..5
…..897.
..9..3…
…..2.3.
….8…4
..3….1.
.4…1…
5.9……
……26.
…..5..3
.5..89…
…7….9
3..2…..
….3.8.4
…31….
..4…1..
.59……
2……65
3…5..8.
…..9…
.7….9.3
…23….
…8..4..
….3..1.
..41…..
.59…..2
.6.5.3…
5…….8
…9..7..
…..93..
2……..
..3.8…4
3..1.4…
..1……
.5….9.2
6..5..3..
……..5
8….9…
..79…..
……..3
..2.3..84
3…1…4
..1….5.
.92..6…
…53….
5..8…..
..9…7..
…..93.2
.3…….
8…..4..
….3…1
.41…..5
.9…2…
…65…3
5..8…..
..9….7.
……9..
…..3.2.
38.4…..
A tu jest rozwiązanie mające 2 ciekawe cechy:
a) zajęte wszystkie miejsca na jednej z przekątnych
b) żadne 2 cyfry się nie stykają „bokami bokami”
.3.1….4
1.5..9.2.
.6..5.3..
5….8.9.
..7.9…3
.2.3…..
..8……
.4.6….2
6…4..3.
Śliczna struktura (zajęte 3 pełne przekątne):
…3..14.
…..15..
….92…
6..53….
..58….9
.79….3.
23….8..
4….6…
….2…6
Umieszczam jeszcze obiecane diagramy symetryczne względem przekątnych:
http://www.gg.pl/dysk/MFF8hZvucsRQMVF8hZvuYu0/symetryczne%202.txt
http://www.gg.pl/dysk/XO1NC_vY5XFQXe1NC_vY9Vg/symetryczne%203.txt
Przy okazji sprostowanie: przesłane przeze mnie diagramy nie są wszystkimi możliwymi. Przy generowaniu wykonałem bowiem założenie, że diagram powinien zawierać wszystkie 32 cyfry rozwinięcia dziesiętnego PI, co spowodowało, że pominąłem sporo przypadków diagramów z mniejszą liczbą cyfr. Natomiast wśród przesłanych znajdują się wszystkie możliwe diagramy z kompletem 32 cyfr (oraz inne, które udało się znaleźć przy okazji).