Je jasné, že hlavolam s jedním předtištěným číslem asi těžko doplníme. Hlavolam, kde bude zase jediné číslo chybět (předtištěných tedy bude osmdesát) doluštíme hned. Je tedy jasné, že v nějakém počtu čísel musí existovat hranice ‚doluštitelnosti‘. Kolik nejméně čísel musí mít i to nejobtížnější Sudoku? Je možné, že to bude odmocnina s jeden a osmdesáti – tedy devět? Pokud ano – proč?
Doplňuji: Doplňuji nadpisovou část otázky. Myslela jsem, že to nebude třeba a každý pochopí, že je tato podmínka samozřejmě brána v úvahu. Btw. zadání Sudoku bez jakýchkoli předtištěných čísel není hlavolam Sudoku – pro ten snad vždy platí POUZE JEDINÉ ŘEŠENÍ. I když je pravda, že jsem už narazila i na takové, kde byla možná 2 i 4 řešení. Ale to je teď snad fuk, ne? Zajímá mne to minimum…
ohodnoťte nejlepší odpověď symbolem palce
Zajímavá 4Pro koho je otázka zajímavá? anonym, orwell, Muso, aliendrone před 2457 dny |
Sledovat
Nahlásit
|
Odpoveď byla označena jako užitečná
17
tedy pokud tomu rozumím dobře, v roce 2012 hrubou silou ověřili, že žádné sudoku s 16 předtištěnými čísly nemá jediné řešení (všechna mají několik)
a teď je to trochu složitější: je jasné, že když mezi sudoku s „n“ předtištěnými čísly je aspoň jedno s jediným řešením, tak už jen když přitisknu kterékoli z jeho vyplněných čísel, tak vytvořím nejméně (81-n) sudoku s „n+1“ předtištěnými čísly
a protože je taky jasné, že všechna sudoku s počtem čísel 7 a méně mají pouze více řešení – a hrubou silou se spočetlo, že stejné je to u sudoku s 16 čísly, tak… odpověď je sedumnáct
Zdroj: https://www.technologyreview.com/s/426554/mathematicians-solve-minimum-sudoku-problem/
Upravil/a: magorvkleci
1 NominaceKdo udělil odpovědi nominaci?zeeue Nahlásit |
taková hranice doluštitelnosti neexistuje. Naopak s klesajícím počtem předtištěných čísel exponenciálně roste počet možných řešení. Takže hlavolam může mít předtištěno NULA čísel a stále je vyluštitelný a to přibližně 6.671×1021 různými způsoby.
Ta otázka by zřejmě měla být položena jinak: „Kolik nejméně čísel může být předtištěno, aby sudoku mělo právě jedno řešení“ 🙂
Upravil/a: anonym
1Kdo udělil odpovědi palec? aliendrone
před 2457 dny
|
0 Nominace Nahlásit |
magorvkleci: Díky za zdroj. Asi tuším, proč to tak bude. 17 je totiž 9(počet číslic)*2(každá číslice,musí být 2×/jedna číslice chybí,jedna je 3×,ostatní 2×/atd.)-1.
annas | 5284 | |
Kepler | 2867 | |
Drap | 2620 | |
quentos | 1803 | |
mosoj | 1594 | |
marci1 | 1356 | |
led | 1345 | |
aliendrone | 1172 | |
zjentek | 1059 | |
Kelt | 1003 |
Astronomie |
Fyzika |
Jazyky |
Matematika |
Sociální vědy |
Technické vědy |
Ostatní věda |