Dobrý den.
Luštím amatérsky sudoku a při tom mne napadlo několik otázek. Obrátil jsem se s nimi na Český svaz hádankářů a křížovkářů, ale ti mne odkázali na vaši Hráčskou asociaci logických her a sudoku.
Dovoluji si zaslat vám svoje svoje dotazy a prosím vás, pokud víte, o odpověď či odkaz na zdroj, ze kterého bych se mohl k dotazům něco dozvědět.
Děkuji vám mnohokrát.
S přátelským pozdravem
Pavel Navrátil
Toto jsou moje dotazy:
1) Kolik je vlastně možné vytvořit různých řešení, tj. sestav číslic (symbolů) v mřížce a hlavně podle jakého matematického vzorce by se tento počet sestav dal vypočítat s využitím kombinatoriky?
2) Jak lze poznat, že počet a rozmístění zadaných číslic (symbolů) jsou dostatečné pro nalezení právě jednoho řešení?
3) Podle čeho se určuje obtížnost řešení pro dané zadání?
4) Je normální, že v určité fázi řešení (u obtížných zadání) nelze postupovat dál použitím žádné z možných technik eliminace a je nutné pokračovat zkusmo?
5) Kdo v ČR sestavuje sudoku a jaký software na sestavování sudoku existuje?
Pokoušel jsem se hladat odpovědi na tyto svoje dotazy na internetu a také pomocí ChatGPT, ale výsledky hledání jsou zatím nedostatečné a neuspokojily mě:
ad 1)
a) Na stránkách https://en.wikipedia.org/wiki/Sudoku a jinde se uvádí, že počet řešení klasického sudoku 9x9 je 6 670 903 752 021 072 936 960. Podle mé komunikace s ChatGPT (viz příloha) žádný vzorec z kombinatoriky pro stanovení tohoto čísla neexistuje (nejde vytvořit) a číslo bylo stanoveno výpočtem na počítači v roce 2005 (Felgenhauer & Jarvis).
b) Pro malé sudoku 4x4 je podle ChatGPT složitost problému menší a vzorec se odvodit dá: 12 * 4! = 12 * 24 = 288. Když jsem ovšem chtěl vědět, kterých je těch 12 základních uspořádání, z nichž se permutacemi symbolů (počet těchto permutací je 4!) vypočte celkový počet 288, poslal mi ChatGPT oněch 12 uspořádání, z nichž ovšem 4 byla chybně (viz příloha). Momentálně si tedy myslím, že počet řešení je 8 * 24 = 192, ale neumím si zdůvodnit ono číslo 8.
ad 2) Na uvedených stránkách wikipedie a jinde se uvádí, že pro klasické sudoku 9x9 musí zadání obsahovat minimálně 17 vyplněných políček. Uvítal bych vysvětlení, jak se k číslu 17 dospělo (2x9 - 1 ??), jak souvisí nezbytný počet vyplněných políček s jejich rozmístěním v mřížce (matici) a s tím, kolikrát je které číslo (symbol) v zadání použito. A pochopitelně jak se pozná, že zadání je jednoznačné?
ad 3) Jsou nějaká objektivní kritéria pro posouzení obtížnosti řešení? V mnoha případech se mi stalo, že se můj názor na obtížnost neshodoval s tím, co bylo uvedeno u zadání.
ad 4) Řeším sudoku mj. i v aplikaci v telefonu, která poskytuje nápovědu. Třikrát se mi stalo, že aplikace ohlásila, že mi neumí žádnou další nápovědu dát. Myslíte si, že je to nedokonalostí použité aplikace, nebo prostě už žádná další logická dedukce nebyla možná? (Nevím, jestli ona 3 uvedená problematická zadání si aplikace sestavila sama nebo je odněkud převzala.)
1) Počet možných sudokových obrazců se spočítal počítačem, je to příliš komplikované na vzoreček. Dokonce ani pro daleko jednodušší latinské čtverce není vzoreček znám. On vlastně ani není vzoreček pro sudoku 4x4.
1b) Počet sudoku 4x4 je opravdu 288. Když si zvolím pevně levý horní čtverec 2x2 a pevně jedničku v pravém dolním čtverci 2x2, mám 3 možnosti:
1243 . . 1234 . . 1243
3421 . . 3421 . . 3421
4312 . . 4312 . . 2314
2134 . . 2143 . . 4132
Prohazováním 3. a 4. řádku a/nebo 3. a 4. sloupce dostanu jedničku v pravém dolním čtverci na libovolné místo, tím vznikne základních 12 uspořádání. Všechna možná uspořádání pak dostanu permutacemi oněch 12, tj. celkem 12x4! = 288.
2) Jednoznačnost zadání se zjistí tak, že se najdou všechna (nebo aspoň dvě) řešení. Jak se přišlo na minimální počet 17 zadaných čísel? Našla se úloha se 17 čísly s právě jedním řešením (takových úloh jsou hromady a jsou mezi nimi i velmi lehká sudoku) a počítačem se ověřilo, že žádné zadání s 16 políčky jednoznačné řešení nemá.
3) Počítač to určuje podle obtížnosti jednotlivých kroků nutných k vyřešení úlohy. Počítačový pohled se nemusí shodovat s lidským. Snadný krok podle počítače nemusí být pro člověka dobře viditelný (typicky "naked single"), a naopak obecně náročná metoda může být v konkrétním zadání snadná. Na soutěžích používáme předluštitele a ti měří čas luštění jednotlivých úloh.
4) Ano, někdy je nutné tipovat.
5) Existují tuny stránek, které generují klasická sudoku. Mnoho našich členů dělá různé varianty sudoku pro soutěže, ty se pak dělají vesměs ručně.
ad 1] Pár dalších čísel je tady https://www.sudopedia.org/wiki/Mathematics_of_Sudoku
Já bych spíš počítal těch cca 5,5 miliardy unikátních zadání, protože permutace čísel, řádků, sloupců nevytovoří zadání nové, ale jenom odvozené. Technicky odvozené. Člověk to může vnímat jinak, protože jinak vidí různé číslice, nebo třeba lépe čte řádky, než sloupce...
ad 2] Minimum je 17, platné zadání (= má 1 řešení) s menším počtem nikdo nenašel. Pokud jde o číslice, tak tam musí být alespoň 8 z 9, jinak by další řešení vzniklo permutací těch chybějících čísel. Někde jsem měl kompletní seznam všech unikátních zadání o 17 číslech (nevím jestli bych to ještě našel) a jsou to úlohy všech možných obtížností.
Opačný problém je kolik je maximální počet čísel, které tvoří minimální množinu nutnou pro správné zadání (= odebráním jakéhokoliv bude mít úloha víc řešení) a to je 39.
ad 3] Já na to používal https://www.sudokuwiki.org/sudoku.htm tam je seznam technik i s vysvětlení jak je použít; včetně mořnosti nechat si spočítat počet řešení a obtížnost úlohy. Bere to podle jednotlivých kroků s tím, že cyklicky zkouší od nejjednodušších po složité.
Asi mám k otázkám nejblíž a pokusím se během pár dnů odpovědět. Ale klidně mě může někdo předběhnout.
Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer
