Sudoku

Je to už hodně dávno, kdy jsem měl potřebu napsat svůj program na luštění Sudoku. Když tak nad tím přemýšlím, je to letos přesně dvacet let. Tedy v roce 2006. Tuto hru jsem rád hrál a tak jsem začal přemýšlet. Jak by to bylo složité, kdybych si program na luštění napsal sám? Ač normálně programuji v Turbo Pascalu, teď jsem zvolil Quick Basic. A když nad tím zpětně přemýšlím, vůbec netuším proč. I když teď už tuším. Potomek měl potřebu také programovat, takže jsem zvolil jednodušší jazyk. Ale druhý den to už bylo jedno. Na začátečníka to bylo asi složité téma ☺

Začal jsem tvořit nejdříve mřížku, která se skládala z buněk 9 x 9. Pravidla jistě všichni znáte, ale i tak je v rychlosti připomenu. Dříve se této hře říkalo magický čtverec. Účelem hry je umístit číslice jedna až devět tak, aby v každém řádku i každém sloupci byly tyto číslice umístěny jedinečně. A to platí i pro ten malý čtverec. Takže součet těchto prostorů je vždy 45. A přes to vlak nejede. Hra začíná tak, že některé buňky už jsou vyplněné. A postup hráče je takový, aby chybějící číslice doplnil. A jsou samozřejmě různé úrovně složitosti. Nejsložitější varianta, kterou vymyslel jistý profesor matematiky, se jmenuje Everest. Ale to jsem tenkrát ještě nevěděl.

Programování tedy započalo. V mřížce o rozměru 9 x 9 bodů jsem se pohyboval pomocí šipek. A při nájezdu do buňky jsem provedl tři cykly. Jeden v aktuálním řádku, druhý v aktuálním sloupci a třetí v malém čtverci. Tady jsem zjistil, které hodnoty jsou již obsazené, a zároveň jsem tyto vypsal pod tabulkou. Bylo tedy zřejmé, jaké hodnoty tam mohu doplnit.

Když jsem si s tímto polotovarem hrál, a hrál jsem si docela dlouho, něco mě napadlo. Co kdybych si našel buňku, ve které je nejméně možností? A když tam bude jen jedna, pak je jasné, jak mám pokračovat. Tomuto principu se říká Warnsdorfovo pravidlo a používá se třeba při takzvané jezdcově procházce. Při stisku klávesy Enter jsem našel první pole s nejmenším počtem možností. A dál už to byla jen manuální hledačka. Nutno říct, že tenhle způsob k řešení nevedl. Těch možností bylo tolik, že postup metodou pokus - omyl, nevedl vůbec nikam. A tady bych mohl svoje povídání ukončit.

Konec skutečně nastal a já se věnoval úplně něčemu jinému. Plno věcí se změnilo, ale ty do tohoto příběhu nepatří. Uběhlo šest let a já si najednou vzpomněl, že jsem kdysi začal tenhle problém řešit, ale nedořešil. A tak jsem zapnul počítač, ale začal jsem úplně od začátku. A navíc v Turbo Pascalu. Tušil jsem, že teď už to nebudou jen tři cykly a ověření pole s nejmenším počtem možností. Můj odhad byl naprosto správný. Začátek probíhal následovně. To, co jsem měl hotové v Quick Basicu jsem přepsal do Pascalu a začal uvažovat dál. Když nejsem schopen vyzkoušet všechny možnosti manuálně, musí toto za mě udělat stroj. A tak jsem začal řešit backtracking. Ta místa, kde je víc možností jsem pojmenoval křižovatky. Tyto fungovaly jak při manuálním zadávání, ale i v okamžiku, kdy jsem spustil automatické řešení. Prostě jsem našel první buňku, kde je nejméně možností, a když byla jen jedna, bylo to v pořádku. Pokud jich bylo víc, poznamenal jsem si ji a šel jsem touto větví. A tohle se opakovalo tak dlouho, až žádná možnost nebyla. Pokud toto nastalo, vrátil jsem se o úroveň výš a šel jinou cestou. A tak pořád dokola, až byla tabulka vyřešena. Mohla nastat i druhá varianta, kdy tabulka řešení neměla.

Pokud jde o ty křižovatky, docela jsem se s tím řešením trápil, ale nakonec se mi rozsvítilo a já najednou v hlavě viděl celé řešení jako na talíři. Měl jsem několik dvourozměrných matic (záloha tabulky), které jsem si třídil při každém návratu, a najednou to začalo fungovat. Navíc jsem si mohl při manuálním řešení křižovatky zobrazit a sám se vracet zpět a jít jinou cestou. Tohle zafungovalo a já měl řešení. Od tohoto okamžiku jsem mohl vyřešit jakékoliv zadání. Vytvářel jsem si svoje úlohy, hledal v různých časopisech a prováděl testování několik týdnů. Fungovalo to. Pak už jsem jen dotahoval user interface a bylo hotovo. Jen zmíním jednu věc. Jak ten první pokus, tak i tento druhý, jsem psal v textovém režimu. A tady bych mohl zase povídání ukončit.

Neudělám to, protože vývoj pokračoval. Asi o tři roky později jsem se rozhodl zkusit ještě jedno vylepšení. Tentokrát jsem chtěl mrknout na grafický režim a zkusit řešení nikoliv automaticky, ale manuálně. Zde měla zafungovat metoda kandidátů. A tady byl grafický režim nezbytný. V textovém režimu jsem měl v buňce buď prázdno anebo jednu hodnotu. Při řešení pomocí kandidátů je nutné mít v buňce všechny dostupné číslice. A tu, se kterou pracuji, bych měl zobrazit odlišnou barvou. Pak se dá postupovat už celkem systematicky. Tady jsem si musel s tím grafickým rozhraním trochu pohrát, protože většinou řeším úlohy, kde si vystačím s textem. A tak jsem měl najednou tři verze. Ta první v Quick Basicu byla jen taková rozjezdová. Druhá a třetí už byla plnohodnotná, ale každá postupovala úplně jiným způsobem. A tak jsem řešil různá zadání a hrál si.

Opět by se mohlo zdát, že už je mému povídání konec. Ale přišel rok 2017 a já narazil na článek, který pojednával právě o výše zmíněné úloze Everest. No a já ji musel okamžitě vyzkoušet. Průser, můj program řešení nenašel. Co teď, kde jsem udělal chybu? Na serveru Slunečnice jsem asi před dvěma roky našel program Sudoku od českého vývojáře. Ten jsem občas používal na testování. Teď jsem ho také zkusil a ani on nebyl úspěšný. Že by mně i kolegovi Everest zlomil vaz a my zůstali kousek pod vrcholem? Ale řešení bylo více méně okamžité. Stačilo změnit takzvanou hloubku backtrackingu. Já ji měl od začátku nastavenou na hodnotu 2048. Nyní jsem ji pro jistotu nastavil na 32767 a hned jsem na ten Everest vystoupil. Zatím nic složitějšího neexistuje. A i kdyby to ještě nestačilo, Pascal má typ WORD a LONGINT.

Tak a teď už můžu svoje povídání o Sudoku a Everestu ukončit. Tímto jsem si odškrtl zase jednu položku ve svém programátorském seznamu. Ještě jich tam pár zůstalo.