Avatar uživatele
zeeue

Kolik nejméně předtištěných čísel v zadání musí obsahovat hlavolam Sudoku, aby se zbytek čísel dal doluštit s 1 řešením?

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…

Uzamčená otázka

ohodnoťte nejlepší odpověď symbolem palce

Upravil/a: annas

Zajímavá 4Pro koho je otázka zajímavá? anonym, orwell, Muso, aliendrone před 2235 dny Sledovat Nahlásit



Nejlepší odpověď
Avatar uživatele
magorvkleci

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.techno­logyreview.com/s/42655­4/mathematici­ans-solve-minimum-sudoku-problem/

Upravil/a: magorvkleci

1 NominaceKdo udělil odpovědi nominaci?zeeue Nahlásit

Další odpovědi
Avatar uživatele
anonym

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

0 Nominace Nahlásit


Diskuze k otázce
Avatar uživatele
zeeue

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.

před 2235 dny Odpovědět Nahlásit
Nový příspěvek