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

Odpovědět

Zajímavá 4 před 2503 dny

Sledovat Nahlásit

Diskuze: 1 příspěvek, nejnovější před 2503 dny

Nejlepší odpověď

magorvkleci

Odpoveď byla označena jako užitečná

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

3 před 2503 dny

1 Nominace Nahlásit

Další odpovědi

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×10²¹ 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

1 před 2503 dny

0 Nominace Nahlásit

Diskuze k otázce

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 2503 dny Odpovědět Nahlásit

Nový příspěvek

Zajímavé otázky v kategorii Věda