Autorem blogu je 
Sudoku je věc, která mě nikdy nebavila; snad to bude tím, že jsem nikdy žádné nevyluštil. Nezaujalo mne ani mathematicky: jde o klasický problém úplného pokrytí, který se algorithmicky řeší methodou (mírně sofistikovaný) pokus-omyl, vznešeně arci nazývanou Dancing Links (pěkně je to vysvětleno např. zde).
K implementaci generátoru sudoku pro PMD 85 mne přivedlo, že jsem hledal program, na kterém bych mohl vyzkoušet kompilátor pro Small-C, který jsem si před časem modifikoval a napsal v něm jednu aplikaci pro PMI-80. Vše ale bylo nakonec jinak.
Potíž spočívá ve způsobu, jak se sudoku sestavuje. Nejprve vezmeme vyplněnou mřížku a náhodně z ní odebíráme čísla, až se dostaneme do stavu, kdy odebráním dalšího čísla přestane mít výsledek pouze jedno řešení. Výsledné sudoku pak vyhodnotíme z hlediska složitosti a pokud vyhovuje tomu, co si přeje uživatel, použijeme ho; pokud ne, pokus opakujeme (u lehkých sudoku, která se paradoxně sestavují složitěji než těžká, mohou být potřebných pokusů i stovky).
Věřím, že bych v C anebo přinejhorším v assembleru napsal rutinu pro řešení sudoku, která by pracovala hluboko pod sekundu, možná i pod 100 ms, ale s ohledem na to, kolikrát se při generaci jednoho sudoku tato rutina spouští, nebylo reálné dostat jiný výsledek, než u kterého by si uživatel mohl před zobrazením prvního sudoku jít uvařit kávu (případně oběd).
Přišel na řadu Plán B. Při něm jsem nechal programem qqwing, který mám ve své linuxové distribuci, vygenerovat pro každou ze čtyř obtížností 128 sudoku, a ta v komprimované podobě uložil do programu. Sudoku se náhodně vybere a poté se nechá projít serií náhodných transformací a permutací, takže výsledků je mnohonásobně víc než jen čtyřikrát 128. Sestavení nového sudoku je přesto téměř okamžité a uživatel těžko kdy přijde na to, že program ve skutečnosti pracuje s presety.
 |
| Ano, trochu jsem fixloval, ale když mě sudoku vážně nebaví! |
Pro náhodnou volbu a modifikaci potřebuji generátor pseudonáhodných čísel. Ten jsem prvně vytvářel u PMI-80, kde nezbylo než využít interakce uživatele s klávesnicí. Při každém čekání na stisk klávesy se měří doba čekání i doba stisknutí a výsledek se pak promíchá ve 32bitovém LCG.
U PMD máme výhodu v tom, že disponujeme obvodem 8253, jehož čítač 1 je zapojen na systémové hodiny. Není proto nutné modifikovat rutinu pro čtení znaku: každé jednotlivé stisknutí klávesy nám poskytuje 16 bitů kvalitní entropie. Těchto 16 bitů jsem rozšířil na 128 bitů tak, že jimi cyklicky XOR-uji 128bitovou proměnnou, a před každým použitím ještě výsledek protřepu
v LCG. Samozřejmě, podmínkou je, aby emulátor tento čítač korektně emuloval; pokud ne, program se vůbec nespustí a ohlásí se chyba hardwaru.
Na programu není jinak nic zajímavého, a jakmile zlikviduji poslední drobnou chybu, o které vím, dám ho opět k disposici váženým čtenářů k beta-testování.
Aktualisováno.
sudoku-1.0-3.ptp
Komentáře
Čo keby sa zobrazoval aj ten čas? V klávesnicovej rutine by sa sledovali sekundové zmeny časovača.
A ešte jedna otázka. V čom tu spočíva tá obtiažnosť? Ja mám pocit, že vo všetkých štyroch obtiažnostiach je to veľmi podobné. Síce sa mierne líši počet pevných čísel, ale napr. vždy 1 číslica chýba, čo nie je, povedzme pri najnižšej obtiažnosti, obvyklé.
Naviac, ten druhý obrázok, na ktorom je čas 2:31 ma dosť frustruje.
Technicky žádný problém, ale měl jsem obavy, abych tím uživatele zbytečně neznervosňoval
A ešte jedna otázka. V čom tu spočíva tá obtiažnosť? Ja mám pocit, že vo všetkých štyroch obtiažnostiach je to veľmi podobné. Síce sa mierne líši počet pevných čísel, ale napr. vždy 1 číslica chýba, čo nie je, povedzme pri najnižšej obtiažnosti, obvyklé.
To je spíš thema do bugzilly ke qqwing-u, kterým jsem generoval vzory. Oni stanoví obtížnost podle celkem podivných kriterií, ale asi je to dost individuální. Suduku sám neřeším, tedy to nedokážu posoudit, mně připadají obtížné (a nudné) všechny.
Naviac, ten druhý obrázok, na ktorom je čas 2:31 ma dosť frustruje.
Když použijete qqwing --solve, možné mě i překonáte
RSS kanál komentářů k tomuto článku