Sudoku

Pravidla

Hlavní pravidla jsou docela jednoduchá a byla objevena Howardem Garnsem. Jsou následující:

• do tabulky 9×9 se doplňují čísla 1–9
• každý řádek musí obsahovat všechna čísla 1–9 (tedy žádné číslo se nesmí opakovat)
• každý sloupec musí obsahovat všechna čísla 1–9 (tedy žádné číslo se nesmí opakovat)
• každé čtvercové pole 3×3 začínající na souřadnicích 0,0; 3,0; 6,0; 0,3; 3,3; 6,3; 0,6; 3,6; 6,6 musí obsahovat všechna čísla 1–9 (tedy žádné číslo se nesmí opakovat)
• a to je vše.

Matematická teorie

Matematicky lze Sudoku chápat jako typ problému splnění omezení (CSP – Constraint Satisfaction Problem). CSP je formální rámec pro reprezentaci a řešení problémů, kde máte množinu proměnných, každou s doménou možných hodnot, a množinu omezení, která určují povolené kombinace hodnot pro tyto proměnné. V případě Sudoku platí:

Proměnné: Každé pole v mřížce 9×9 je proměnná.

Doména: Doménou každé proměnné je množina celých čísel od 1 do 9.

Omezení: Omezeními jsou pravidla Sudoku, která říkají, že žádný řádek, sloupec ani podmřížka 3×3 nesmí obsahovat opakující se číslice.

Cílem je najít řešení, které přiřadí hodnotu každé proměnné (vyplní každé pole) tak, aby byla splněna všechna omezení.

Sudoku hádanky mohou mít různou úroveň obtížnosti – některé vyžadují složitější řešitelské strategie než jiné. Existují techniky a strategie, které lze při řešení Sudoku využít – od jednoduché eliminace a kontroly kandidátů až po pokročilejší metody jako "nahé dvojice", "skryté jedničky" nebo "X-wing". Tyto strategie vycházejí z logických úvah založených na matematických vlastnostech hádanky.

Matematici a informatici také zkoumali složitost Sudoku a zjistili, že jde o problém třídy NP-úplný (NP-complete), což znamená, že nalezení řešení Sudoku je výpočetně náročný problém. Nicméně pro běžné Sudoku vytvořené lidmi dokážou efektivní algoritmy nalézt řešení poměrně rychle.

Shrnuto: Sudoku je matematická hádanka, kterou lze formalizovat jako problém splnění omezení a která je předmětem matematického a algoritmického zkoumání.

1) Nahé dvojice:

• V řádku, sloupci nebo čtverci, pokud najdete dvě buňky, které obsahují stejnou dvojici možných čísel (kandidátů), tvoří tyto buňky tzv. "nahou dvojici".
• Tuto dvojici čísel pak můžete vyloučit z ostatních buněk ve stejném řádku, sloupci nebo čtverci.
• Tím se rébus zjednoduší a mohou se odhalit další čísla.

2) Skryté jedničky:

• Skrytá jednička nastává tehdy, když v určitém řádku, sloupci nebo čtverci existuje pouze jeden kandidát pro konkrétní buňku./li>
• I když může být v buňce uvedeno více kandidátů, pouze jeden z nich je platný s ohledem na ostatní čísla ve stejném řádku, sloupci nebo čtverci.
• Identifikace a umístění této skryté jedničky může vést k dalším logickým závěrům.

3) X-wing:

• Technika X-wing se používá, když existují dva řádky a dva sloupce, ve kterých se určitá číslice může v každém řádku i sloupci objevit pouze dvakrát – tím vznikne na mřížce tvar "X".
• V takovém případě můžete možnost výskytu dané číslice odstranit z ostatních buněk v protínajících se řádcích a sloupcích.
• Tato technika je o něco složitější, ale velmi účinná, pokud je použitelná.