Obecné metody pro řešení Sudoku

Existuje několik různých metod a strategií, které lze použít k řešení sudoku. Zde je několik z nich:

Vyloučení kandidátů

Pro každou prázdnou buňku v mřížce Sudoku analyzujte čísla ve stejném řádku, sloupci a bloku a vyloučte čísla, která jsou již přítomna. Zbývající čísla se stanou možnými kandidáty pro danou buňku.

Základní a jednoduchá strategie, kterou lze použít v raných fázích luštění hádanky k eliminaci nesprávných kandidátů a zúžení možností.

Může být časově náročné a neefektivní pro složitější hádanky, které vyžadují pokročilejší strategie.

Jediný kandidát

V daném řádku, sloupci nebo bloku, pokud existuje pouze jedno číslo, které by mohlo být možným kandidátem pro konkrétní buňku, mělo by být toto číslo tam umístěno.

Efektivní strategie pro nalezení a umístění čísla, když pro něj existuje pouze jedno možné místo.

Omezen na jednotlivé buňky a neschopný sám řešit složitější hádanky.

Nahé páry/trojky/kvarteta

Pokud dvě nebo více buněk ve stejném řádku, sloupci nebo bloku obsahují stejnou sadu dvou, tří nebo čtyř možných kandidátů, mohou být všechny ostatní výskyty těchto kandidátů ve stejném řádku, sloupci nebo bloku vyloučeny.

Eliminuje možné kandidáty identifikací společných sad čísel v souvisejících řádcích, sloupcích a blocích.

Vyžaduje, aby dvě nebo více buněk obsahovalo přesně stejné možné kandidáty, což může být vzácný případ.

Skryté jednotky

Pokud v řádku, sloupci nebo bloku zbývá pouze jedno místo pro určité číslo, musí se tam toto číslo umístit.

Rychlá metoda pro nalezení a umístění čísel, když pro dané číslo zbývá pouze jedno možné místo.

Vyžaduje to pečlivé prozkoumání každého řádku, sloupce a bloku, aby se našli jediní možní kandidáti.

X-Wing

Pokud existují dva řádky a dva sloupce, ve kterých pouze čtyři konkrétní buňky obsahují možné kandidáty pro dané číslo, lze toto číslo vyloučit ze všech ostatních buněk v těchto řádcích a sloupcích.

Eliminuje možné kandidáty identifikací vzorů, které zahrnují dva řádky a dva sloupce, kam lze umístit dané číslo.

Vyžaduje šablonu, která obsahuje dva řádky a dva sloupce, což může být vzácné.

Mečoun

Rozšíření techniky X-Wing, kde tři řádky a tři sloupce obsahují pouze devět specifických buněk, které obsahují možné kandidáty pro určité číslo. To může toto číslo vyloučit z ostatních buněk v rámci těchto řádků a sloupců.

Zužuje výběr možných kandidátů identifikací vzorů, které zahrnují tři řádky a tři sloupce, kam lze umístit určité číslo.

Hůře se hledá než X-Wing, protože vyžaduje tři řádky a tři sloupce, aby měl stejný vzor.

Medúza

Rozšíření techniky Swordfish, kde čtyři řádky a čtyři sloupce obsahují pouze šestnáct specifických buněk, které obsahují možné kandidáty na určité číslo. To může toto číslo vyloučit z ostatních buněk v rámci těchto řádků a sloupců.

Identifikuje vzory, které zahrnují čtyři řádky a čtyři sloupce, kam lze umístit určitý počet, čímž se dále omezí možnosti.

Je vzácné najít šablony, které obsahují čtyři řádky a čtyři sloupce.

Zpět na začátek

Pokud neexistují žádné logické závěry, můžete použít zpětný tah. To zahrnuje hádání prázdného políčka a pokus o vyřešení zbytku hádanky. Pokud to vede k nesprávnému řešení, vraťte se a zkuste další tipy. Pokračujte, dokud není hádanka vyřešena.

Tyto metody lze kombinovat k řešení sudoku různé obtížnosti. Použitím logiky a strategie lze mřížku postupně vyplňovat, dokud není dokončena správně.

Používá se, když jiné logické závěry již nejsou platné, a umožňuje dohady pro další postup.

Může to být časově náročné a vyžaduje testování různých odhadů k nalezení správného řešení. Pokud odhad vede k nesprávnému řešení, musíte se vrátit a zkusit další odhad.

Konečně,

Pokud neexistují žádné logické závěry, můžete použít zpětný tah. To zahrnuje hádání prázdného políčka a pokus o vyřešení zbytku hádanky. Pokud to vede k nesprávnému řešení, vraťte se a zkuste další hádání.

Toto jsou jen některé z běžných metod používaných k řešení sudoku. Úroveň obtížnosti konkrétního hádanky může vyžadovat použití pokročilejších strategií nebo kombinací několika metod. Je také možné použít počítačové programy nebo aplikace, které dokáží sudoku automaticky řešit pomocí různých algoritmů a strategií.

Nezapomeňte, že různé metody fungují lépe v různých situacích a úrovních obtížnosti. Kombinací několika metod zvyšujete své šance na vyřešení obtížného Sudoku.

Cílem Sudoku je uspořádat všechna čísla tak, aby v čtvercích, řádcích nebo sloupcích o rozměrech 3×3 nebyla žádná stejná čísla. Zde je příklad vyřešeného Sudoku:

Je možné ověřit, že v každém z devíti čtverců, stejně jako ve všech řádcích a sloupcích, se nenacházejí žádná opakující se čísla. Při řešení sudoku je třeba použít toto pravidlo „jedinečnosti“ čísla a důsledným vyřazováním kandidátů (malá čísla v buňce označují, která čísla se podle názoru hráče mohou v této buňce nacházet) najít místa, kde může být pouze jedno číslo.

Když otevřeme sudoku, vidíme, že v každé buňce jsou označena všechna malá šedá čísla. Můžeme okamžitě odstranit značky z čísel, která již byla označena (značky se odstraní kliknutím pravým tlačítkem myši na malé číslo):

Začnu číslem, které se v této křížovce objevuje pouze jednou – 6, aby bylo snazší ukázat vyloučení kandidátů.

Čísla jsou vyloučena ve čtverci s číslem, v řádku a sloupci jsou červeně označeni kandidáti k vyloučení – klikneme na ně pravým tlačítkem myši s tím, že na těchto místech nemohou být šestky (jinak budou ve čtverci/sloupci/řádku dvě šestky, což je proti pravidlům).

Pokud se nyní vrátíme k jednotkám, obraz výjimek bude následující:

Odstraňujeme kandidátské jedničky z každé prázdné čtvercové buňky, která již má jedničku, z každého řádku, který má jedničku, a z každého sloupce, který má jedničku. Takže pro tři jedničky budou 1 čtverce, 1 sloupce a 1 řádky.

Dále přejdeme rovnou na 4, tam je více čísel, ale princip je stejný. A když se podíváte pozorně, uvidíte, že v levém horním čtverci 3×3 je pouze jedno volné políčko (označeno zeleně), kam může stát 4. Takže tam dáme číslo 4 a smažeme všechny kandidáty (nemohou tam být žádná další čísla). V jednoduchém sudoku lze tímto způsobem vyplnit poměrně dost polí.

Po zadání nového čísla můžete znovu zkontrolovat předchozí, protože přidání nového čísla zužuje rozsah hledání, například v této křížovce díky sadě čtyř zbývá pro číslo v tomto čtverci pouze jedna buňka (zelená):

Ze tří dostupných buněk pro jednotku je pouze jedna neobsazená, takže jednotku umístíme tam.

Proto odstraníme všechny zjevné kandidáty pro všechna čísla (od 1 do 9) a v případě možnosti zadáme čísla:

Po odstranění všech zjevně nevhodných kandidátů zůstala buňka, kde zůstal pouze 1 kandidát (zelená), což znamená, že toto číslo je tři, a tam stojí.

Čísla se zadávají i v případě, že kandidát je posledním zbývajícím v čtverci, řádku nebo sloupci:

Toto jsou příklady na pětkách, vidíte, že v oranžových políčkách nejsou žádné pětky a v zelených políčkách je v oblasti pouze jeden kandidát, což znamená, že tam pětky jsou.

Toto jsou nejzákladnější způsoby zadávání čísel v sudoku, které si můžete vyzkoušet vyřešením sudoku na jednoduchou obtížnost (jedna hvězdička), například: Sudoku #12433, Sudoku #14048, Sudoku #526. Uvedené sudoku jsou kompletně vyřešeny pomocí výše uvedených informací. Pokud ale nemůžete najít další číslici, můžete se uchýlit k metodě výběru – uložte si sudoku a zkuste náhodně zadat nějakou číslici a v případě neúspěchu sudoku načtěte.

Pokud chcete zvládnout složitější metody, čtěte dál.

Zamčení kandidáti

Uzamčený kandidát ve čtverci

Zvažte následující situaci:

V modře zvýrazněném čtverci jsou kandidáti na číslo 4 (zelené buňky) umístěni ve dvou buňkách na jednom řádku. Pokud je na tomto řádku číslo 4 (oranžové buňky), pak v modrém čtverci nebude místo pro 4, což znamená, že 4 vyloučíme ze všech oranžových buněk.

Podobný příklad pro číslo 2:

Uzamčený kandidát v řadě

Tento příklad je podobný předchozímu, ale zde v řádku (modrý) je 7 kandidátů umístěno v jednom čtverci. To znamená, že sedmičky jsou odstraněny ze všech zbývajících polí čtverce (oranžový).

Uzamčený kandidát ve sloupci

Podobně jako v předchozím příkladu, pouze v tomto sloupci je kandidátů 8 umístěno v jednom čtverci. Všichni kandidáti 8 z ostatních buněk čtverce jsou také odstraněni.

Po zvládnutí uzamčených kandidátů můžete řešit sudoku střední obtížnosti bez výběru, například: Sudoku #11466, Sudoku #13121, Sudoku #11528.

Skupiny čísel

Skupiny jsou hůře viditelné než uzamčení kandidáti, ale pomáhají překonat mnoho slepých uliček v obtížných křížovkách.

Nahé páry

Nejjednodušším typem skupiny jsou dva identické páry čísel v jednom čtverci, řádku nebo sloupci. Například holý pár čísel [7, 8] v řádku:

Pokud jakákoli jiná buňka v oranžové řadě obsahuje číslo 7 nebo 8, pak zelené buňky budou obsahovat 7 a 7 nebo 8 a 8, ale podle pravidel je nemožné, aby řada obsahovala 2 stejná čísla, takže všechna 7 a všechna 8 jsou z oranžových buněk odstraněna.

Volná dvojice [5, 8] současně v jednom sloupci a jednom čtverci. Přebyteční kandidáti (červeně) jsou odstraněni ze sloupce i čtverce.

Důležitá poznámka – skupina musí být přesně „holá“, tj. nesmí v těchto buňkách obsahovat jiná čísla. To znamená, že [5, 8] a [5, 8] jsou holá skupina, ale [5, 6, 8] a [5, 8] nikoli, protože skupina již není holá, je zde další číslo – 6. Také [5, 8] a [5, 7] nejsou holá skupina, protože čísla musí být stejná, ale zde jsou ve skupině 3 různá čísla.

Nahé trojky

Holé trojky jsou podobné holým párům, ale je hůře rozpoznatelná – jsou to 3 holá čísla ve XNUMX polích.

V příkladu se čísla [1, 2, 6] opakují třikrát v jednom řádku. Ve skupině jsou pouze tři čísla a jsou umístěna na 3 polích, což znamená, že čísla 3, 3, 1, která zbývají, jsou z oranžových polí odstraněna.

Holá trojka nemusí obsahovat celé číslo, například by se hodila kombinace: [1, 6], [1, 2] a [2, 6] – to jsou všechny stejné 3 typy čísel ve třech buňkách, jen v neúplném složení.

Nahé čtyřky

Dalším rozšířením nahých skupin jsou nahé čtyřky.

Čísla [2, 5], [2, 5, 6, 7], [5, 6, 7], [5, 6] tvoří holou čtveřici čtyř čísel 2, 5, 6 a 7, umístěných ve čtyřech polích. Tato čtveřice se nachází v jednom čtverci, což znamená, že všechna čísla 2, 5, 6, 7 ze zbývajících polí čtverce (oranžových) jsou odstraněna.

Skryté páry

Další variantou skupin jsou skryté skupiny. Podívejme se na příklad:

V nejvyšším řádku se čísla 6 a 9 nacházejí pouze ve dvou buňkách, v ostatních buňkách tohoto řádku žádná taková čísla nejsou. A pokud do jedné ze zelených buněk vložíte jiné číslo (například 1), pak v řádku nebude místo pro jedno z čísel: 6 nebo 9, takže je třeba smazat všechna čísla v zelených buňkách kromě 6 a 9.

Výsledkem by tedy mělo být, že po odstranění přebytečného množství by měla zůstat pouze holá dvojice čísel.

Skryté trojčata

Podobně jako u skrytých dvojic – 3 čísla stojí ve 3 buňkách čtverce, řádku nebo sloupce a pouze v těchto třech buňkách. V těchto buňkách mohou být i další čísla – ta se odstraní.

V příkladu jsou čísla 4, 8 a 9 skrytá. V ostatních buňkách sloupce žádná taková čísla nejsou, takže ze zelených buněk odstraníme přebytečné kandidáty.

Skryté čtyřky

Totéž se skrytými trojkami, pouze 4 čísla ve 4 buňkách.

V příkladu tvoří čtyři čísla 2, 3, 8, 9 ve čtyřech buňkách (zelených) jednoho sloupce skrytou čtyřku, protože v ostatních buňkách sloupce (oranžových) tato čísla nejsou. Přebyteční kandidáti ze zelených buněk jsou odstraněni.

Tímto končíme naši úvahu o číselných skupinách. Pro procvičení si zkuste vyřešit následující křížovky (bez přiřazování): Sudoku #13091, Sudoku #10710

X-wing a mečoun

Tato podivná slova jsou názvy dvou podobných metod vyřazování kandidátů v Sudoku.

X-křídlo

X-wing je zvažován pro kandidáty s jedním číslem, zvažme 3:

Ve dvou řadách (modré) jsou pouze 2 trojice a tyto trojice jsou pouze na dvou řádcích. Tato kombinace má pouze 2 řešení pro trojice a ostatní trojice v oranžových sloupcích toto řešení vyvracejí (zkontrolujte proč), takže červení kandidáti na trojice by měli být odstraněni.

Podobně pro kandidáty na 2 a XNUMX sloupců.

Ve skutečnosti je X-wing docela běžný, ale ne tak časté setkání s touto situací slibuje eliminaci zbytečných čísel.

Toto je složitější varianta X-wingu pro tři řádky nebo sloupce:

Dále uvažujeme 1 číslo, v příkladu je to 3. 3 sloupce (modré) obsahují trojice, které patří do stejných tří řádků.

Čísla nemusí být ve všech buňkách, ale průsečík tří vodorovných a tří svislých čar je pro nás důležitý. Ať už svisle nebo vodorovně, neměla by být ve všech buňkách žádná čísla kromě zelených, v příkladu je to svisle – sloupce. Pak by měla být všechna přebytečná čísla v řádcích odstraněna tak, aby 3 zůstala pouze v průsečících čar – v zelených buňkách.

Další analytické údaje

Vztah mezi skrytými a nahými skupinami.

A také odpověď na otázku: proč nehledají skryté/nahé pětky, šestky atd.?

Podívejme se na následující 2 příklady:

Toto je jedno sudoku, kde se bere v úvahu jeden sloupec čísel. 2 čísla 4 (označená červeně) se eliminují dvěma různými způsoby – pomocí skrytého páru nebo pomocí prázdného páru.

Další sudoku, kde je v jednom políčku jak holá dvojice, tak i skrytá trojka, které odstraňují stejná čísla.

Pokud se podíváte na příklady nahých a skrytých grup v předchozích odstavcích, všimnete si, že se 4 volnými buňkami a nahou grupou budou zbývající 2 buňky rozhodně nahou dvojicí. S 8 volnými buňkami a nahou čtveřicí budou zbývající 4 buňky skrytou čtveřicí:

Pokud vezmeme v úvahu vztah mezi holými a skrytými skupinami, zjistíme, že pokud je ve zbývajících buňkách holá skupina, bude tam určitě i skrytá skupina a naopak.

A z toho můžeme usoudit, že pokud máme 9 volných polí v řadě a mezi nimi je určitě holá šestka, pak bude snazší najít skrytou trojku, než hledat spojení mezi 6 buňkami. Totéž platí pro skrytou a holou pětku – je snazší najít holou/skrytou čtyřku, takže se pětky ani nehledají.

A ještě jeden závěr – má smysl hledat skupiny čísel pouze tehdy, je-li v čtverci, řádku nebo sloupci alespoň osm volných políček; s menším počtem políček se můžete omezit na skryté a holé trojky. A s pěti nebo méně volnými políčky nemusíte trojky hledat – postačí dvojky.

Závěrečné poznámky

Zde jsou nejznámější metody pro řešení sudoku, ale při řešení složitých sudoku nevede použití těchto metod vždy k úplnému řešení. V každém případě vždy pomůže metoda výběru – uložte sudoku na slepé místo, dosadte libovolné dostupné číslo a zkuste hádanku vyřešit. Pokud vás tato substituce dovede k nemožné situaci, znamená to, že je třeba načíst a odstranit dosazené číslo z kandidátů.

Jako 2