Sudoku 17 indicií Snadné
Nejnovější seznam skóre pro #21q05
Nejnovější seznam skóre pro Sudoku 17 indicií
Jak hrát Sudoku 17 indicií
Bylo prokázáno, že standardní sudoku musí mít alespoň 17 indicií, aby mělo jedinečné řešení.
Pravidla sudoku:
-
Vyplňte čísla 1–9 v každém řádku, sloupci a dílčí mřížce 3x3 v mřížce 9x9.
-
Každé číslo se může v každém řádku, sloupci a dílčí mřížce 3x3 objevit pouze jednou.
-
Vyplňte prázdná místa čísly 1-9 tak, aby každý řádek, sloupec a podmřížka 3x3 měla všechna čísla 1-9.
Sudoku je logická hádanka s umisťováním čísel. Cílem je vyplnit mřížku 9x9 čísly 1-9 tak, aby každý řádek, sloupec a podmřížka 3x3 obsahovala všech devět čísel právě jednou.
V roce 2009 Gary McGuire a jeho tým dokázali, že každý hlavolam Sudoku s 16 indiciemi musí mít alespoň dvě řešení. Udělali to pomocí techniky zvané "mrtvé vzory."
Mrtvý vzor je konfigurace sudoku, která má dvě nebo více možných řešení. McGuire a jeho tým zjistili, že každý sudoku s 16 indiciemi musí obsahovat alespoň jeden mrtvý vzor. Tyto hádanky proto musí mít alespoň dvě řešení.
Tento výsledek má několik důsledků. Zaprvé to znamená, že neexistuje nic takového jako 16ti klíčová hádanka sudoku s jedinečným řešením. Zadruhé to znamená, že jakýkoli sudoku s 16 klíči lze vyřešit několika způsoby. Za třetí, znamená to, že existuje nekonečný počet 16-ti klíčových sudoku.
Zde je techničtější vysvětlení důkazu, že sudoku musí mít alespoň 17 vodítek, aby mělo jedinečné řešení:
Důkaz začíná zvažováním sudoku s 16 indiciemi. Tuto hádanku si můžeme představit jako sadu omezení na čísla, která lze umístit do prázdných polí.
Pak můžeme použít techniku zvanou „backtracking“, abychom se pokusili najít řešení hádanky. Backtracking je rekurzivní algoritmus, který zkouší všechny možné kombinace čísel v prázdných polích, dokud nenajde řešení.
Pokud existuje jedinečné řešení hádanky, zpětné sledování jej nakonec najde. Pokud však existuje více řešení, pak zpětné sledování nemusí nikdy najít řešení.
McGuire a jeho tým použili backtracking, aby ukázali, že pokud existuje 16-stopá hádanka Sudoku s jedinečným řešením, pak musí existovat způsob, jak spustit algoritmus backtrackingu tak, aby vždy našel řešení.
Následně ukázali, že to není možné. Udělali to vytvořením sady 16 vodítek, které vedou k mrtvému vzoru. Tento mrtvý vzorec znamená, že existují dvě možná řešení hádanky a žádný způsob, jak spustit algoritmus zpětného sledování tak, aby vždy našel stejné řešení.
Tento výsledek ukazuje, že každý 16-klíčový sudoku musí mít alespoň dvě řešení.
