Jak rozwiązać bardzo trudne Sudoku. Zagadki logiczne

W tym artykule przyjrzymy się szczegółowo, jak rozwiązać złożone Sudoku na przykładzie diagonalnego Sudoku.

Otrzymujemy warunek numer 437, który pokazano na rysunku 1. I pierwszy kwadrat od razu rzuca się w oczy, jest najbardziej nasycony liczbami otwartymi. Brakuje cyfr 1, 3, 4, 9.

Ale ponieważ linia pozioma a zawiera już trzy, liczba trzy jest umieszczona na c1. Reszty nie jesteśmy w stanie dokładnie umiejscowić.

Przyjrzyjmy się więc, co jeszcze mamy.

Na przykład pion to 4 i tutaj liczba cztery może znajdować się tylko na b4, ze względu na obecność czwórki w piątym kwadracie i na poziomie c.

Pozostałych liczb na razie nie będziemy podawać.

Wszystkie techniki i metody, z których będziemy dalej korzystać, dotyczą rozwiązywania zarówno prostego, jak i złożonego Sudoku.

Co mamy na poziomym b?

Ale teraz możemy całkowicie wypełnić piąty i pierwszy kwadrat!

To, co otrzymaliśmy, pokazano na rysunku 4.

Zwróć uwagę na pion 3. Tutaj musisz umieścić 1, 6, 7. Jednostka jest umieszczana tylko na f3 i na tej podstawie umieszczane są pozostałe - e3 -7, h3-6.

Następna w kolejce jest pionowa 9, której umiejscowienie jest po prostu fantastyczne. d9-2, g9-6, h9-8.

A jeśli sprawdzimy, czy są otwarte single?!

Na przykład cyfra trzy jest bezpiecznie umieszczona w komórkach d2 i h5.

Choć dalsza analiza singletonów nic nie daje. Następnie przejdźmy do pozostałej przekątnej.

Brakuje jej 6, 2, 4. Numer sześć może znajdować się tylko na c7. Resztę łatwo wypełnić. Dlaczego pion 4 nie jest ustawiony na koniec? Naprawmy to. s4-8. Wynik naszych badań przedstawiono na rysunku 5.

Teraz wypełnijmy poziomą linię c. s8-1, s5-9, s6-2. A to wszystko opiera się na obecności tych liczb w innych pionach.

Sudoku to łamigłówka. Czasami skomplikowane, trudne do rozwiązania, ale zawsze interesujące i uzależniające dla każdego, kto zdecyduje się zagrać w tę grę. Nazwa pochodzi z języka japońskiego: „su” oznacza „cyfrę”, a „doku” oznacza „stojący samotnie”.

Nie każdy wie, jak rozwiązać Sudoku. Na przykład skomplikowane łamigłówki mogą rozwiązać zarówno inteligentni, przemyślani początkujący, jak i profesjonaliści, którzy ćwiczą grę dłużej niż jeden dzień. Nie będzie możliwe, aby każdy po prostu wziął to i rozwiązał problem w pięć minut.

Zasady

Jak więc rozwiązać Sudoku. Zasady są bardzo proste i jasne, łatwe do zapamiętania. Nie myśl jednak, że proste zasady obiecują „bezbolesne” rozwiązanie; będziesz musiał dużo myśleć, stosować logiczne i myślenie strategiczne, spróbuj odtworzyć obraz. Prawdopodobnie musisz kochać liczby, aby rozwiązać Sudoku.

Najpierw rysowany jest kwadrat 9 x 9. Następnie grubszymi liniami dzieli się go na tzw. „obszary” po trzy kwadraty każdy. Rezultatem jest 81 komórek, które docelowo powinny zostać całkowicie wypełnione liczbami. W tym właśnie tkwi trudność: cyfry od 1 do 9 umieszczone na całym obwodzie nie powinny się powtarzać ani w „obszarach” (kwadraty 3 x 3), ani w liniach w pionie i/lub poziomie. W każdym Sudoku początkowo jest kilka wypełnionych komórek. Bez tego gra jest po prostu niemożliwa, bo w przeciwnym razie rezultatem nie będzie rozwiązanie, ale wymyślenie. Złożoność łamigłówki zależy od liczby liczb. Złożone sudoku zawierają kilka liczb, często ułożonych w taki sposób, że przed ich rozwiązaniem trzeba się nieźle namęczyć. W płucach około połowa liczb jest już na swoim miejscu, co znacznie ułatwia rozpoznanie.

Przykład całkowicie zdemontowany

Trudno zrozumieć, jak rozwiązać Sudoku, jeśli nie ma konkretnego przykładu pokazującego krok po kroku, jak, gdzie i co wstawić. Dostarczony obraz jest uważany za prosty, ponieważ wiele minikwadratów jest już wypełnionych niezbędnymi liczbami. Nawiasem mówiąc, to na nich będziemy polegać na rozwiązaniu.

Na początek możesz spojrzeć na linie lub kwadraty, gdzie jest szczególnie dużo liczb. Na przykład druga kolumna od lewej pasuje idealnie; brakuje tylko dwóch liczb. Jeśli spojrzysz na te, które już tam są, staje się oczywiste, że w pustych komórkach drugiej i ósmej linii brakuje 5 i 9. Z piątką nie wszystko jest jeszcze jasne, może być i tu, i tam, ale jeśli spojrzysz na dziewiątkę, wszystko stanie się jasne. Ponieważ w drugim wierszu (w siódmej kolumnie) znajduje się już cyfra 9, oznacza to, że aby uniknąć powtórzeń, dziewiątkę należy umieścić w ósmym wierszu. Metodą eliminacji dodajemy 5 do drugiego rzędu - i już mamy jedną wypełnioną kolumnę.

Całą łamigłówkę Sudoku można rozwiązać w podobny sposób, jednak w bardziej skomplikowanych wersjach, gdy w jednej kolumnie, wierszu lub kwadracie brakuje nie tylko kilku liczb, ale znacznie więcej, trzeba będzie zastosować nieco inną metodę. To również teraz przeanalizujemy.

Tym razem za podstawę przyjmiemy środkowy „obszar”, w którym brakuje pięciu liczb: 3, 5, 6, 7, 8. Wypełniamy każdą komórkę nie dużymi liczbami efektywnymi, ale małymi, „roboczymi”. Po prostu wpisz w każdym kwadracie liczby, których brakuje, a które mogą się tam znajdować z powodu ich braku. W górnej komórce jest to 5, 6, 7 (3 w tej linii znajdują się już w „regionie” po prawej stronie, a 8 po lewej); komórka po lewej stronie może zawierać 5, 6, 7; w samym środku - 5, 6, 7; po prawej - 5, 7, 8; od dołu - 3, 5, 6.

Zatem teraz sprawdzamy, które minicyfry zawierają liczby inne od pozostałych. 3: jest tylko w jednym miejscu, nie ma go w pozostałych. Oznacza to, że można go skorygować na większy. Liczby 5, 6 i 7 znajdują się w co najmniej dwóch komórkach, co oznacza, że ​​zostawiamy je w spokoju. W jednym jest 8, co oznacza, że ​​pozostałe cyfry znikają i można zostawić ósemkę.

Naprzemiennie te dwie metody kontynuujemy rozwiązywanie Sudoku. W naszym przykładzie zastosujemy pierwszą metodę, ale należy pamiętać, że w skomplikowanych odmianach konieczna jest druga. Bez niego będzie to niezwykle trudne.

Nawiasem mówiąc, gdy w górnym „obszarze” znajdzie się środkowa siódemka, można ją usunąć z minicyfr środkowego kwadratu. Jeśli to zrobisz, zauważysz, że w tym regionie pozostało już tylko jedno 7, więc możesz je tylko opuścić.

To wszystko; gotowy wynik:

Gatunek

Istnieją różne rodzaje łamigłówek Sudoku. W niektórych warunek wstępny to brak identycznych liczb nie tylko w rzędach, kolumnach i minikwadratach, ale także po przekątnej. Niektóre zamiast zwykłych „regionów” zawierają inne liczby, co znacznie utrudnia rozwiązanie problemu. Tak czy inaczej, wiesz, jak rozwiązać Sudoku, przynajmniej podstawową zasadę, która ma zastosowanie do każdego rodzaju. To zawsze pomoże ci poradzić sobie z zagadką o dowolnej złożoności, najważniejsze jest, aby dołożyć wszelkich starań, aby osiągnąć swój cel.

Wniosek

Teraz wiesz, jak rozwiązać Sudoku, dlatego możesz pobrać podobne łamigłówki z różnych stron, rozwiązać je online lub kupić wersje papierowe w kioskach. W każdym razie teraz będziesz miał co robić przez długie godziny, a nawet dni, ponieważ Sudoku jest nierealistycznie przeciągnięte, zwłaszcza gdy musisz faktycznie wymyślić zasadę ich rozwiązania. Ćwicz, ćwicz i jeszcze raz ćwicz, a wtedy będziesz rozbijał tę łamigłówkę jak orzechy.

Cześć wszystkim! W tym artykule szczegółowo przeanalizujemy rozwiązanie złożonego Sudoku na konkretnym przykładzie.

Przed przystąpieniem do analizy zgodzimy się na nazywanie małych kwadratów liczbami, numerując je od lewej do prawej i od góry do dołu.

Wszystkie podstawowe zasady rozwiązywania Sudoku opisano w tym artykule. Jak zwykle w pierwszej kolejności przyjrzymy się otwartym singlom. A było ich tylko dwóch b5-5, e6-3.

Następnie ustalimy możliwych kandydatów dla wszystkich pustych pól.

Lista kandydatów będzie pisana drobnym drukiem

zielony

, aby odróżnić go od już istniejących numerów.

I tak na drugim pionie liczba 8 może znajdować się tylko na komórkach -h2 i i2, usuńmy liczbę osiem z pozostałych niewypełnionych komórek siódmego kwadratu.

W trzecim pionie liczba osiem może znajdować się tylko na e3. To, co otrzymaliśmy, pokazano na rysunku 3.

Nie da się znaleźć niczego innego, za co można by się chwycić.

Mamy dość trudny orzech do zgryzienia, ale i tak go złamiemy!

Rozważmy więc ponownie naszą parę e1 i d2, ułóżmy ją w ten sposób d2-9, e1 -2.

A w razie naszego błędu jeszcze raz wrócimy do tej pary.

Teraz możemy bezpiecznie zapisać dwójkę w komórce d9!

A w kwadracie siódmym dziewięć może znajdować się tylko na h1.

Następnie w pionie 1 piątka może znajdować się tylko na i1, co z kolei daje prawo do umieszczenia piątki w komórce h9.

Rysunek 4 pokazuje, co otrzymaliśmy.

Rozważmy teraz następną parę, są to d3 i f1.

Mają kandydatów 7 i 6. Patrząc w przyszłość, powiem, że opcja ułożenia d3-7, f1 -6 jest błędna i nie będziemy jej rozważać w artykule, aby nie tracić czasu.

Badacze złożonych sieci Zoltan Torozkay i Maria Erksi-Ravaz z Uniwersytetu Notre Dame również byli w stanie wyjaśnić, dlaczego niektóre łamigłówki Sudoku są trudniejsze od innych. Jedynym minusem jest to, że potrzebujesz doktoratu z matematyki, aby zrozumieć, co oferują.

Czy potrafisz rozwiązać tę zagadkę? Zostało stworzone przez matematyka Arto Incalę i uważane jest za najtrudniejsze Sudoku na świecie. Zdjęcie z nature.com

Torozkay i Erksi-Ravaz rozpoczęli analizę Sudoku w ramach swoich badań nad teorią optymalizacji i złożonością obliczeniową. Mówią, że większość entuzjastów Sudoku do rozwiązywania tych problemów stosuje podejście „brutalnej siły” oparte na technikach zgadywania. Dlatego fani Sudoku uzbrajają się w ołówek i wypróbowują wszystkie możliwe kombinacje liczb, aż znajdą poprawną odpowiedź. Ta metoda nieuchronnie doprowadzi do sukcesu, ale jest pracochłonna i czasochłonna.

Zamiast tego Torozkay i Erksi-Ravaz zaproponowali uniwersalny algorytm analogowy, który jest całkowicie deterministyczny (nie wykorzystuje domysłów ani brutalnej siły) i zawsze znajduje właściwe rozwiązanie problemu i to dość szybko.

Aby ukończyć tę łamigłówkę sudoku, badacze wykorzystali „deterministyczne rozwiązanie analogowe”. Zdjęcie z nature.com

Naukowcy odkryli również, że czas potrzebny na rozwiązanie łamigłówki przy użyciu algorytmu analogowego korelował z poziomem trudności zadania ocenianym przez ludzi. To zainspirowało ich do opracowania skali rankingowej określającej trudność łamigłówki lub problemu.

Stworzyli skalę od 1 do 4, gdzie 1 oznacza „łatwo”, 2 „ stopień średni złożoność”, 3 – „trudne”, 4 – „bardzo trudne”. Rozwiązanie łamigłówki z oceną 2 zajmuje średnio 10 razy więcej czasu niż łamigłówki z oceną 1. Według tego systemu, najwięcej złożona zagadka ze znanych nadal ma ocenę 3,6; Bardziej złożone problemy Sudoku nie są jeszcze znane.

Teoria rozpoczyna się od odwzorowania prawdopodobieństw dla każdego pojedynczego kwadratu. Zdjęcie z nature.com

„Nie interesowałem się Sudoku, dopóki nie zaczęliśmy pracować nad kolejnymi klasa ogólna wykonalność problemów boolowskich, mówi Torozkay. - Ponieważ Sudoku należy do tej klasy, kwadrat łaciński 9. rzędu okazał się dla nas dobrym poligonem doświadczalnym i dzięki temu je poznałem. Ja i wielu badaczy zajmujących się takimi problemami fascynuje nas pytanie, jak daleko my, ludzie, możemy się posunąć w rozwiązywaniu Sudoku w sposób deterministyczny, bez użycia brutalnej siły, która jest wyborem losowym, a jeśli przypuszczenie jest błędne, musimy cofnąć się o krok lub kilka kroków w tył i zacząć od nowa. Nasz analogowy model decyzyjny jest deterministyczny: nie ma losowego wyboru ani zwrotu w dynamice.

Teoria chaosu: Stopień trudności zagadek jest tutaj pokazany jako dynamika chaotyczna. Zdjęcie z nature.com

Torozkay i Erksi-Ravaz uważają, że ich algorytm analogowy ma potencjał do zastosowania w rozwiązaniu duża ilość różnorodne zadania i problemy z zakresu przemysłu, informatyki i biologii obliczeniowej.

Doświadczenie badawcze uczyniło również Torozkai wielkim fanem Sudoku.

„Moja żona i ja mamy kilka aplikacji Sudoku na naszych iPhone'ach i do tej pory graliśmy w nie tysiące razy, rywalizując o najszybszy czas na każdym poziomie” – mówi. „Często intuicyjnie dostrzega kombinacje wzorców, których ja nie zauważam”. Muszę je wyciągnąć. Rozwiązanie wielu zagadek, które w naszej skali sklasyfikowano jako trudne lub bardzo trudne, staje się dla mnie niemożliwe bez zapisania ołówkiem prawdopodobieństw.

Metodologia Torozkai i Erksi-Ravaz została po raz pierwszy opublikowana w Nature Physics, a później w Nature Scientific Reports.

SUDOKU jest popularna gra- łamigłówka, czyli łamigłówka z liczbami, którą można pokonać jedynie budując logiczne wnioski. W nazwie Sudoku, przetłumaczone z japońskiego, „su” oznacza „liczbę”, a doku „doku” oznacza „stojący samotnie”. Dlatego „SUDOKU” w przybliżeniu przetłumaczone oznacza „jednocyfrową”.

Nazwa „Sudoku” została nadana tej łamigłówce przez japońskie wydawnictwo Nicoli w 1984 roku. Sudoku jest skrótem od „Suuji wa dokushin ni kagiru”, co po japońsku oznacza „liczba musi być pojedyncza”. Wydawnictwo Nikoli nie tylko wymyśliło dźwięczną nazwę, ale także po raz pierwszy wprowadziło symetrię w zadaniach do swoich puzzli. Nazwę układanki nadał szef Nicoli – Kaji Maki. Cały świat przyjął tę nową japońską nazwę, ale w samej Japonii łamigłówka nazywa się „Nanpure”. Nicoli zarejestrowała słowo „Sudoku” jako znak towarowy w swoim kraju.

Historia powstania Sudoku

Indie uważane są za kolebkę szachów, a Anglię za kolebkę piłki nożnej. Gra Sudoku, która szybko rozprzestrzeniła się na cały świat, nie ma jako takiej ojczyzny. Za prototyp sudoku można uznać łamigłówkę „Magiczny kwadrat”, która pojawiła się w Chinach 2000 lat temu.

Historia Sudoku jako gry sięga nazwiska słynnego szwajcarskiego matematyka, mechanika i fizyka Leonharda Eulera (1707 - 1783).

W dokumentach znajdujących się w jego archiwum, datowanych na 17 października 1776 r., znajdują się notatki dotyczące sposobu formowania kwadratu magicznego z określonej liczby komórek, zwłaszcza 9, 16, 25 i 36. Inny dokument zatytułowany „ Badania nowe odmiany kwadratu magicznego” Euler umieścił w komórkach litery łacińskie (kwadrat łaciński), później wypełnił komórki literami greckimi i nazwał kwadrat grecko-łaciński. Odkrywanie różne opcje kwadratu magicznego Euler zwrócił uwagę na problem łączenia symboli w taki sposób, aby żaden z nich nie powtórzył się w żadnym rzędzie ani kolumnie.

W nowoczesna forma Sudoku po raz pierwszy opublikowano w 1979 roku w magazynie Word Games. Autorem układanki był Harvard Garys z Indiany. Łamigłówka „Miejsce liczbowe” (przetłumaczona na rosyjski jako „miejsce liczby”) - można to uznać za jedno z pierwszych wydań współczesnego Sudoku. Dodano kwadratowe bloki 3x3, co było ważnym ulepszeniem, ponieważ uczyniło łamigłówkę bardziej interesującą. Użył zasady kwadratów łacińskich Eulera, zastosował ją do macierzy 9x9 i dodał dodatkowe ograniczenia, liczby nie powinny się powtarzać w wewnętrznych kwadratach 3x3.

Zatem pomysł Sudoku nie pochodzi z Japonii, jak wielu ludzi myśli, ale nazwa gry jest rzeczywiście japońska.

W Japonii ta łamigłówka została opublikowana przez Nicoly Inc., głównego wydawcę zbiorów różnych łamigłówek, w gazecie Monthly Nicolist w kwietniu 1984 r. pod tytułem „Liczba może zostać użyta tylko raz”. 12 listopada 2004 roku gazeta The Times po raz pierwszy opublikowała na swoich łamach łamigłówkę Sudoku. Publikacja ta stała się sensacją, a zagadka szybko rozprzestrzeniła się po Wielkiej Brytanii, Australii i Nowej Zelandii; zyskała popularność w USA.

Odmiany sudoku

Czym więc jest Sudoku? Obecnie istnieje wiele modernizacji tego popularnego typu łamigłówek, ale klasyczne Sudoku to kwadrat 9x9, podzielony na podkwadraty o bokach po 3 komórki każdy. Zatem całkowite pole gry wynosi 81 komórek. W załączniku do mojej pracy zamieszczę różne typy Sudoku i rozwiązania (moi rodzice pomogli mi je rozwiązać).

Sudoku różni się poziomem trudności w zależności od wielkości kwadratu:

• 1. Dla małych miłośników puzzli utwórz Sudoku z polami o wymiarach 2x2, 6x6 komórek.
• 2. Dla profesjonalistów dostępne są komórki Sudoku 15x15 i 16x16

Sudoku występuje na różnych poziomach:

• łatwy
• przeciętny
• trudny
• bardzo trudne
• bardzo złożone

Zasady rozwiązań

Sudoku ma tylko jedną zasadę. Należy wypełnić puste komórki tak, aby w każdym rzędzie, w każdej kolumnie i w każdym małym kwadracie 3X3 każda liczba od 1 do 9 pojawiła się tylko raz. Niektóre komórki w Sudoku są już wypełnione liczbami, a resztę musisz tylko wypełnić. Im więcej liczb jest na początku, tym łatwiej jest rozwiązać zagadkę. Nawiasem mówiąc, poprawnie skomponowane Sudoku ma tylko jedno rozwiązanie.

Rozwiązanie sudoku

Strategia rozwiązywania Sudoku obejmuje trzy etapy:

• nauka ułożenia liczb w układance
• wstępne ustawienie liczb
• analiza

Najlepszy sposób rozwiązania - wpisz numery kandydatów w lewym górnym rogu komórki. Następnie możesz dokładnie zobaczyć liczby, które powinny zajmować tę komórkę. Sudoku należy grać powoli, ponieważ jest to gra relaksująca. Niektóre zagadki można rozwiązać w ciągu kilku minut, ale inne mogą zająć wiele godzin, a w niektórych przypadkach nawet dni.

Podstawa matematyczna. Liczba możliwych kombinacji w Sudoku 9x9 wynosi, według obliczeń Berthama Felgenhauera, 6 670 903 752 021 072 936 960.