Sudoku 44
Rozwiązywanie dobrego zwykłego sudoku (bez wariacji na temat lub udziwnień) ma swoją dramaturgię. Trafia się w nim choć jeden moment przełomowy, gdy trudno znaleźć pole dla kolejnej cyfry i trzeba się natrudzić, by ruszyć dalej. Zdarza się jednak, że intensywne próby zawodzą. To zniechęca, bo nie jest przyjemnie nie móc sobie z czymś poradzić (podobnie jak nikła jest przyjemność, gdy wszystko idzie jak po maśle). Jedni w takiej sytuacji poddają się, inni „strzelają”, czyli zakładają coś i ruszają niepewną drogą. A przecież jest kilkanaście bardziej zaawansowanych sposobów (technik, strategii) zmagania się z sudoku. Można się z nimi zapoznać np. w Sudopedii.
Tororo w komentarzu przedstawił na przykładzie działanie jednej strategii – XY-chain. Jest klarowna i piękna logicznie. Dlaczego więc ta i inne niełatwe metody w gruncie rzeczy pozostają sztuką dla sztuki i bardzo rzadko ktoś z nich korzysta?
Zapewne dlatego, że stosowanie bardziej zawiłych technik ma praktyczną wadę, która skłania do umieszczenia ich w szufladce z napisem „metody logiczne z błądzeniem”. Wiadomo, jak pięknie działają, tylko nie wiadomo, gdzie je zastosować, a ściślej – jak znaleźć miejsce, gdzie konkretna strategia mogłaby się przydać. To tak, jak byśmy dostali klucze do pokoju w wielkim hotelu bez informacji o numerze pokoju, a nawet nie mając pewności, czy w ogóle do którychś drzwi pasują.
Szanujące się czasopisma unikają jak ognia zadań, w których bez „strzelania” albo stosowania trudnych metod miłośnik wpisywania cyfr w kratki nie dotrze do celu. Żadne nie opublikowałoby na przykład poniższego sudoku 44. Mickiewiczowska liczba stąd, że po wpisaniu 19 cyfr, czyli gdy w diagramie będzie ich 44, nie sposób ruszyć dalej. Chyba że zastosuje się kolejno (tylko w których miejscach?) piękne, ale „diaboliczne” strategie: X-Cycles, XY-Chain (i to 3-krotnie) oraz Y-Wing. Proszę spróbować lub sprawdzić, korzystając z solvera polecanego przez Tororo. Oczywiście, można zamiast tego parokrotnie „objechać” przeszkodę, próbując i błądząc. W sumie zadanie jest „zabójcze”. Nawet dotrzeć do 44 nie jest łatwo.
Najtrudniejsze sudoku, pojawiające się w japońskich pismach dla miłośników zabaw logicznych, nigdy nie wymagają stosowania trudnych strategii. Zawsze wystarcza siedem podstawowych, podanych na wspomnianej stronie z solverem. Oto przykład takiego ekstremalnie trudnego (dla Japończyków) zadania. Czasy rozwiązywania mile widziane.
Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3 dni.
Komentarze
1) 13 minut (po wpisaniu kilkunastu cyfr, w kwadracie w III kolumnie i III wierszu brakowało 2 i 5. Udało mi się trafić dobre położenie tych cyfr, dalej szło bez problemów. )
2) 17 minut
2. ~10min. (żeby było absurdalnie to podam ostatni szereg – 452816379)
1. około 15 minut, z tym że dwa razy mi przerwano:)
2. 4 minuty
pozdrawiam
Każde z tych zadań zajęłoby mi więcej niż 10 minut (na tyle starczyło mi sił).
Czy ktoś z Państwa może mi odpowiedzieć, na czym właściwie polega fenomen Sudoku? Od kiedy napisałem dla zabawy program, który rozwiązuje każde Sudoku w czasie mniejszym niż 1 ms, łamigłówka ta straciła dla mnie jakikolwiek powab.
Wydaje mi się (chociaż nie potrafię tego na szybko udowodnić), że nie może istnieć strategia lepsza niż przeszukiwanie z nawrotami, gdzie w każdym kroku wybiera się kratkę z najmniejszą liczbą możliwości i przechodzi do stanu, gdzie jest o jeden mniej wolnych pól. Gdyby wybrana cyfra nie doprowadziła do zapełniania planszy, wybiera się kolejną.
Tak to robi komputer, tak może robić człowiek, zamieszczone sudoku
rozwiązuje się kilkudziesięcu krokach.
Jaki jest sens mówić o strategiach rozwiązywania Sudoku? Czy to nie jest dorabianie ideologii?
Co ciekawe, ostatni szereg mojego rozwiązania to: 457 216 389. NIe znam teorii Sudoku, widać jednak, że jeśli rozwiazanie Karzyma jest poprawne, to drugie sudoku ma więcej niż jedno rozwiązanie. Być może jest to banalna obserwacja, w końcu muszą istnieć sudoku „niejednoznaczne” (np. pusta plansza)…
Rozwiązanie Karzyma jest poprawne, Piotra nie
Piotrze, fenomen sudoku polega, a właściwie polegał na tym samym co fenomen krzyżówki: prosta, wciągająca zabawa umysłowa plus szum medialny. Masz rację, jako masówka sudoku jest schematyczne jak dzierganie na drutach, dlatego bardziej wybredni główkołamacze traktują je z politowaniem.
Strategie sudoku to awangarda i ciekawostka dla zakręconych sudokomanów. Ma swój urok, ale jest mało praktyczna. „Dorabianie ideologii” to przesada, ale coś w tym jest.
mp
Moje czasy (na „usprawiedliwienie” dodam, że od b. dawna nie rozwiązywałem sudoku):
1. ok. 30 min (w pewnym momencie uznałem, że gdzieś się pomyliłem, więc wpisywałem trochę strzelając… ale jednak wyszło)
2. ok. 20 min (łatwe, tylko opornie mi coś szło)
Pozwolę sobie wtrącić parę słów do tematu popularności Sudoku. Był taki czas, kiedy szukałem tej rozrywki w gazetach i na stronach internetowych. Każde zadanie, które wpadło mi w ręce starałem się rozwiązać. Ale dość szybko przestały mnie one bawić a nawet zaczęło mnie irytować, gdy oczekując na jakieś nowego typu zadanie znajdywałem kolejne zadanie Sudoku. Wtedy także zastanawiałem się nad tak dużą popularnością tej łamigłówki. Wytłumaczyłem sobie wówczas ten fenomen łatwością tworzenia kolejnych diagramów. Otóż mając jedno dobrze ułożone zadanie można w bardzo prosty sposób tworzyć kolejne, które swoją graficzną postacią nie będą przypominać zadania z którego powstały. Wystarczy wykonać permutację liczb i zamienić miejscami niektóre kolumny czy wiersze a powstałe nowe zadania nijak nie będą przypominać swojego pierwowzoru. Stopień trudności można uzyskiwać ujawniając na wstępie mniej lub więcej liczb. W ten sposób z jednego zadania można wygenerować setki tysięcy nowych. W redakcjach gazet nie trzeba zatrudniać jakiegokolwiek specjalisty sudokuloga do generowania zadań. Tylko bardziej ambitni starają się tworzyć nowe i ciekawe zadania, ale i tak nie umieszczają ich w codziennej prasie. Zadanie w gazecie musi być na tyle proste, aby dało się je względnie szybko rozwiązać podnosząc poczucie wartości rozwiązującego i tym samym zachęcając do kupienia gazety następnego dnia. Do tego celu Sudoku nadaje się ideanie.
Może nie jest dokładnie tak, ale chyba nie jestem daleki od prawdy.
Pozdrawiam,
jazz
Całkiem możliwe, że moje rozwiązanie nie jest poprawne, gdyż kompilując wczoraj mój program, zakomentowałem z pewnych względów kilka linii. Do tego zapomniałem o regule Sudoku, która mówi, że cyfry nie mogą sie powtarzać nie tylko w pionie i w poziomie, ale także w każdym z 9 kwadratowych obszarów.
To jednak nie zmienia faktu, że rozwiązywanie Sudoku to żadna sztuka, tylko żmudne sprawdzanie kolejnych możliwości, których jest tak mało, że tępy komputer podaje natychmiast żadany układ.
Dlatego też nie przestaje mnie dziwić, jak taka – za przeproszeniem -prymitywna łamigłówka zdobyła taką popularność.
Piotrze, właśnie dlatego zdobyła popularność, bo jest „prymitywna” (też za przeproszeniem).
mp
pozwolę się nie zgodzić z opiniami (większością) autora bloga, jak i pozostałych wyznawców niefajności sudoku w porównaniu z… no własnie, z czym?
Piotrze, znajdź proszę we wszystkich wpisach tego blogu KILKA ślicznych łamigłówek, których się nie da zaimplementować tak, by tępy komputer sobie z tym nie poradził (o czasie nie wspomnę).
Otóż moim zdaniem sudoku nie jest prymitywną łamigłówką. Panie Marku, jakie kryterium Pan zastosował? Generalnie zdecydowana większość łamigłówek jakie znam, po straceniu dziewictwa, czyli rozwiązaniu, przeanalizowaniu sposobów rozwiązywania (co nie przeczę daje mi najwięcej radości) staje się prymitywna? czyli była wczesniej już prymitywna, czy dopiero się stała?
Nie będę próbował polemizować o wyższości sudoku nad innymi łamigłówkami. To co mi się w nim podoba, to to, ze mogę rozpocząć prawie KAŻDY dzień od 10 minutowego rozwiązywania kilku diagramów, co daje mi poczucie dobrze rozpoczętego dnia zdrowia umysłowego (można porównać do 10 minutowego truchciku na dobry początek dnia i dla zdrowia ciała).
Zgadzam się, że po rozgryzieniu CAŁKOWITYM łamigłówka staje się tylko ćwiczeniem szybkości i spostrzegawczości. ALe zakładam, ze zdecydowana mniejszość piszących tu poznała te wszystkie tajniki i nie na zasadzie przeczytania o tym w sieci tylko samodzielnego rozpracowania. I jeżeli już miałbym się z czymś zgodzić, to ze zdaniem mistrza świata w łamigłówkach, który nie lubi rozwiązywać sudoku, bo jest NUDNE. Tak, jak się je rozgryzie. Ponadto jednak społeczność sudokowa stara się cały czas rozwijać tę łamigłówkę tak, by zadania nie były sztampowe i wymagały jednak myślenia przy ich pierwszym rozwiązywaniu.
Na koniec mały kamyczek do ogródka – jestem wręc zachwycony, że istnieje mnóstwo ludzi, którzy nie mieli do czynienia z łamigłówkami (jednak porównywanie sudoku do krzyżówek jest dla mnie nie na miejscu, i to nie dlatego że już dawno minął mi czas kiedy się zachłystywałem Jolką) i LUBIĄ rozwiązywać sudoku. Według mnie jest tu duzo więcej dobrego dla nas jako społeczeństwa niż (jezeli ktotkolwiek znajdzie) złego.
Na koniec dodam, że lubię sudoku, ale na pewno mniej niż dobre zadania łamigłówkowe. I nie tylko diagramowe, żeby była jasność sytuacji.
A dla Ciebie Piotrze mam propozycję byś spróbował porozwiązywać naprawdę trudne mistrzowskie sudoku, niestandardowe, w celu znalezienia sposobów rozwiązywania – killera, niesąsiedniego, kropek czy nieregularnego. Są to naprawdę trudne orzechy do rozwiązania i dają mnóstwo satysfakcji ze znalezienia sposobów w sytuacjach wydawałoby się niemożliwych. I nie piszę tu o łatwych diagramach, dla których niepotrzebne są ŻADNE strategie rozwiązywania
pozdrawiam
pafcio – reprezentant Polski w sudoku, żeby nie było niedomówień
Pafciu, ja tylko nieśmiało próbowałem wyjaśnić, skąd się wzięła popularność zwykłego sudoku – bo „niezwykłe” nie jest popularne, raczej niszowe. A wzięła się stąd, że zwykłe, prasowe sudoku to prosta, choć logiczna, wyszukiwanka (określenie „prymitywna” to oczywiście przesada, dlatego było w ptaszkach).
mp
Podobnie jak pafcio chciałbym wystąpić w obronie sudoku, ale odwrotnie niż pafcio właśnie przez porównanie z krzyżówkami.
Jeżeli ktoś odwiedzający tego bloga wziąłby się za rozwiązywanie krzyżowek z czasopisma typu „1000 krzyżowek”, to już po kilku zadaniach uznałby zapewne, że przy ich rozwiązywaniu więcej pracuje ręką niż głową. Myślę, że nieco inne odczucie miałby przy rozwiązywaniu krzyżówki „z przymrużeniem oka” albo „hetmańskiej”.
Podobnie jest w przypadku sudoku. Są zadania dla „szerokiej grupy odbiorców”, gdzie kolejne cyfry wpisuje sie niemal automatycznie i są zadania trudniejsze, szczególnie różne odmiany podstawowej wersji. Jeżeli ktoś miał do czynienia tylko z pierwszą grupą zadań, to faktycznie może traktować sudoku z lekceważeniem.
Chyba każdą łamigłówkę, polegającą na zapełnianiu diagramu cyframi czy innymi znakami, można rozwiązać komputerowo, metodą sprawdzania kolejnych mozliwości. Nie wiem, jaką złozoność czasową ma algorytm zastosowany przez Piotra, ale podejrzewam, że przy bardziej rozbudowanych diagramach: 16×16, 25×25 czy 36×36 (takie zadania pojawiają się czasami w japońskich pismach) mógłby się tak szybko nie uporać z problemem.
A skoro już o zadaniach dla Japończyków mowa, to nie wiem dlaczego drugie z tego odcinka zostało uznane za „ekstremalnie trudne”. Wprawdzie na pierwszy rzut oka widać tylko, gdzie wpisać jedną cyfrę 8, ale szybko można zauważyć, że w 5 rzędzie cyfra 1 może być tylko w 7 lub 8 kolumnie. Stąd wynika natychmiast, że w 1 kolumnie cyfra 1 jest w 4 lub 6 rzędzie, a zatem 1 musi być w r3k2. I dalej idzie jak po sznurku: 1 kolejno w r8k3, r7k8 i r5k7; 8 w r8k7, r1k3, r7k1, r9k4 itd.
Również wg mnie zadanie drugie nie jest takie trudne jak miało być. Jak napisał Michał S – najpierw wpisuje się 8, potem wszystkie jedynki, potem da się uzupełnić górny rząd i dalej idzie gładko. Za to pierwsze – rzeczywiście trudne.
Czasy orientacyjne:
1 – 8’30”
2 – 4’15”
W obu przypadkach czasy nieco przekłamane, 1-zaniżony, 2-zawyżony, a to dlatego, że znałem trudność obydwu zadań, dlatego w pierwszym szybko wziąłem się za wpisywanie pomocnych pencilmarksów, potem jakiegoś XY-Chaina (czy jak mu tam), wykorzystałem, a dalej pozostał tylko kontrolowany strzał. W drugim przypadku zacząłem podobnie, od wielu pencilmarksów, ale jak się później okazało – niepotrzebnie.
Panie Marku, przepraszam, że ja z innej beczki, ale nie mam jak się z Panem skontaktować, więc może Pan to tu jakoś znajdzie i przeczyta. Mam pytanie dotyczące ilości i sposobu ujawniania liczb w sudoku – czy są jakieś zasady, które się do tego stosuje, bo wiadomo, że nie powinno się ich ujawnić za dużo, ale też i nie za mało, żeby zadanie miało tylko jedno rozwiązanie. Jaka jest więc zasada ujawniania liczb, żeby mieć pewność, że zadanie będzie poprawnie przedstawione? Może jakoś Pan zauważy ten mój wpis i raczy odpowiedzieć mi na maila, jaki jest podany? Z góry dzięki! 🙂
Nie ma ścisłych zasad określających, ile liczb i jak rozmieszczonych powinno znaleźć się w diagramie zwykłego sudoku. Wiadomo tylko, że mniej niż 17 być nie może, a więcej niż 30 z małym hakiem jest – że tak powiem – granicą przyzwoitości. Czy układ liczb jest symetryczny, czy nie – to rzecz gustu. Na ogół symetria jest w cenie, ale jednak najważniejsza pozostaje strona merytoryczna, a konkretnie „dramaturgia” rozwiązywania (najpierw łatwo, potem przynajmniej raz pod górkę, pokonanie trudnej przeszkody i sprint do mety z ewentualną niespodzianką w końcówce). Bardzo dbają o to ambitne wydawnictwa japońskie, zamieszczające sudoku układane (podobno) ręcznie, ale trudno uwierzyć, by ich autorzy nie korzystali przynajmniej ze wsparcia komputerowego. Przed kilku laty w sieci można było trafić na szkółki ręcznego układania sudoku. Ostało się ich niewiele, np. ta: http://www.sudokuonline.us/make_your_own_sudoku_puzzle.php.
mp
w sprawie układania diagramów
http://motris.livejournal.com/55833.html
pozdr
Witam Państwa! Oto moje orientacyjne czasy:
1. około 21,4 s
2. 16,76 s
Łyso wam, Łyso!?
Prof. Tomaszu, jak to jest? Czasy są orientacyjne a zarazem podane z dokładnością do setnych sekundy. Póki tego nie pojmę, to i łysym trudno będzie mi zastać 😉
Pozdrawiam,
jazz