Avatar uživatele
Pokročilý

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.

Nejlepší odpověď

Odpoveď byla označena jako užitečná
Avatar uživatele
Bronzový

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.c om/s/426554/mathematicians-sol ve-minimum-sudoku-problem/

 

Další odpovědi:

Avatar uživatele
Zlatý

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^21 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í" :-)

 

Diskuze k otázce

Avatar uživatele
Pokročilý

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 2x/jedna číslice chybí,jedna je 3x,ostatní 2x/atd.)-1.

 

Přihlásit se

Položte otázku, odpovězte, zapojte se, …

začněte zde

Reklama

Kvalitní odpovědi v: Věda

Zlatý annas 3422
Zlatý quentos 1466
Zlatý mosoj 1438
Zlatý Drap 1345
Zlatý Kepler 1175
Zlatý led 782
Zlatý marci1 726
Zlatý gecco 709
Zlatý Lamalam 709
Zlatý hanulka11 627

Zobrazit celkový žebříček

Facebook

 

Váš požadavek se vyřizuje, počkejte prosím.