Sudoku

7.1.2006 22:31 | Přečteno: 6674× | Ostatní

Krátký příběh o tom, jak hraje tuto hru programátor a uživatel Linuxu v jednom

Dnes jsem v jednom nejmenovaném časopise narazil na tuto hru. Rozhodl jsem se, že bych si ji mohl zkusit vyřešit. Sudoku je docela hit a navíc jsem si říkal, že "to přece nemůže být těžké". Asi po půl hodince jsem zjistil, že deterministické řešení daného rozložení prostě neexistuje, a že to zase není tak lehké, jak jsem si myslel. Časopis jsem dosti znechuceně odložil.

Poté jsem se začal učit na zkoušku, což mě příšerně nebavilo, a tak jsem se rozhodl, vrátit se k Sudoku. Tentokrát vśak poněkud jiným způsobem. Přece jen, proč bych se trápil se zkoušením všech možných i nemožných řešení, když můj křemíkový miláček, to zvládne rychleji a lépe? No a protože se mi vhodný program nechtělo hledat, udělal jsem malý (ale plně funkční) návrh v jazyce C (konkrétně C99).

Původně jsem algoritmus chtěl koncipovat jako rekurzivní testování všech možností, ale to jsem brzy zavrhnul kvůli rychlosti. Nakonec jsem vymyslel relativně jednoduchý, průhledný,nerekurzivní a jak se později ukázalo, také velmi rychlý, algoritmus o kterým bych se s vámi rád podělil

Pole sudoku je definováno jako pole (nečekaně ), které je jednorozměrné (což je nedůležité) a konkrétně se jedná o pole struktur. Struktura je jednoduchá. Má hodnotu value (tedy hodnota, která je v poli, kde 0 = neobsazené pole) a constant (tedy konstantní hodnota, která je předtištěná, třeba v časopise). Dále se v programu nachází funkce, která testuje, zda položením hodnoty do určeného políčka, neporuší základní pravidlo sudoku (tedy 1-9 v řádku, sloupci a čtverci 3x3). Tato funkce by zasloužila optimalizaci, ale jak uvedu později, stejně je to celé rychlé. Takže máme datovou strukturu (opravdoví programátoři z ní jistě algoritmus už dávno odhadli ) a máme testovací funkci. Zbývá vlastní implementace vyhledávání. Ta je založena na cyklu s proměnnou pos (pozice v poli). Pozice pos je při volání fce. nastavena na 0. Pokud je menší, než 0, žádné další řešení neexistuje a funkce končí. Pokud je naopak rovna velikosti pole, je nalezeno řešení, které je vypsáno. Pokud se na pozici pos nachází konstanta, inkrementujeme pos (konstanta nemůže být měněna), jinak inkrementujeme hodnotu v poli. Pokud je po inkrementaci hodnota v poli větší než 9, nastavíme pos na index předchozí nejblyžší ne-konstantní hodnoty, jinak inkrementujeme pos. No a nakonec zapíšeme novou hodnotu do pole. A to je vše. Tento jednoduchý algoritmus řeší sudoku bez rekurze (a tím přidané paměti)

Když jsem toto doprogramoval, zkusil jsem rychlost. Byl jsem mile překvapen. Jedna varianta Sudoku (lépe řečeno VŠECHNY jeho možnosti řešení) bylo vyřešeno za asi za 0.1s.

Pokud by někdo měl o implementaci zájem, je ke stažení na http://tux.wz.cz/files/sudoku/sudoku-solve.tar.gz

Jedná se o neúplnou implementaci, která neumí načítat pole ze souboru, což možná dodělám (no a možná taky ne ), nicméně implementace je (aspoň myslím), relativně slušná a i programátor začátečník snadno pochopí, jak definovat vlastní hrací pole (tedy vyplněné hodnoty).

Nakonec malá otázka. Jak byste tento problém řešili vy?

       

Komentáře

[Ondrej Sykora]

Ja jsem sudoku resil docela jednoduchym rekursivnim prohledavanim, ale podstatne vylepsenym o vyskrtavani nepouzitelnych hodnot a okamzitym dosazovanim ve chvili, kdy na policku zustane jenom jedna mozna hodnota (samozrejme nasledovanym dalsim vyskrtavanim v radku, sloupci a ve skupine a pripadne dosazenim).

I kdyz je to jednoducha rekurze a je tam pri ni spousta zbytecnych alokaci pameti pro potreby backtrackingu, tak vsechna testovana zadani vyresila pod 10 ms (to je asi nejmensi casovy rozdil co jde v jave zmerit).

[Honza "tux" Friesse]

Tohle řešení mne taky napadlo, ale nechtěl jsem k řešení používat další paměť, která by vznikla z rekurze a hlavně (pokud jsem to tedy správně pochopil) bych musel mít u každého políčka pole/vektor/list hodnot, které tam mohou být. Nicméně Vaše řešení by zřejmě pro větší sudoku (typu 16x16) bylo rychlejší.

[Ondrej Sykora]

Zas tak strasne to neni, mozne hodnoty pro kazde policko mam reprezentovane pomoci bitove masky v jednom integeru. Tim jsem sice omezeny na sudoku 25x25, ale to me zas tolik nevadi :)

S tou pameti to v mem reseni snad az tak horke neni, ono se tech maximalne 81 poli o velikosti 32bytu (pro sudoku 9x9) nekam posklada ;) A protoze vliv na vykon je dost zasadni, rozhodl jsem se ze pameti tolik setrit nebudu..

V te svoji javove implementaci jsem zkousel vypnout proskrtavani a bez nej byl cas vypoctu nekolikrat vyssi. Semtam i kolem vteriny, prumerne tak 400-500ms. S proskrtavanim (a bez dalsich optimalizaci) jsem se dostal na 10, maximalne 20ms u vsech zadani. A to uz zato stoji :)

[petr_p]

Ja kdybych nebyl liny a rovzpomnel se na Prolog, tak bych to napsal v nem. Prolog je na prohledavani stavoveho prostoru s omezujicimi podminkami jako sity (no, byl prave kvuli tomu navrzen).

Tu hru jsem si zkousel na papire (taky z nejmenovaneho casopisu) a pokud je zadani slusne, tak lze najit reseni i bez prochazeni slepych cest (tak za hodinku).

A jinak pojem deterministicky znamena trochu neco jineho, nez jak jsi to podal. Nedeterministicky program ma totiz tu vyhodu, ze nejdrive uhadne reseni, a pak jej deterministicky overi. Bohuzel takove stroje jeste nemame :( Vsechny ostatni programy jsou deterministicke, i kdyz casto se musi vracet ze slepych cest.

[Lukáš Zapletal]

Nedeterministický program bych chtěl vidět

[Pmx]

Tak jsem si to cvičně vyzkoušel, úspěšně. Akorát jsem si k tomu napsal jednoduché rozhraní v GTK (hafo spinbuttonů)

Už jsem předtím viděl i jeden pythonovej prográmek, který to řešil stejně. Když jsem byl na dni otevřených dveří na matfyzu, tak tam při studijním programu Informatika byla přednáška Od sudoku k omezujícím podmínkám. Úplně jsem ji v závěru nepochopil, ale řekl bych, že tam sudoku řešili nějak podobně.

[Honza "tux" Friesse]

Existuje vůbec pro Linux nějaká implementace v GTK? Pokud ne, tak byste to svoje rozhraní mohl vylepšit a vypustit free.

[Michal Karas]

Ve svých záložkách jsem objevil odkaz na G-Sudoku. Bohužel už nevím, jak se mi tam dostal.

[Filda]

Nijak jsem ten zdroják nestudoval, ale zajímalo by mě, jestli dovede vyřešit i ty opravdu težký případy

[Honza "tux" Friesse]

Jeden jsem zkusil. Výsledek :

honza@daemon:~/Develop/sudoku-solve$ time ./sudoku-solve
2 0 4 0 1 0 0 0 0
0 1 5 0 0 0 0 0 4
0 0 0 9 6 0 0 0 0
3 0 7 0 0 1 0 0 0
0 4 0 0 0 0 0 5 0
0 0 0 4 0 0 9 0 3
0 0 0 0 3 9 0 0 0
1 0 0 0 0 0 6 2 0
0 0 0 0 8 0 3 0 9
Solution :
2 9 4 5 1 8 7 3 6
6 1 5 3 7 2 8 9 4
7 8 3 9 6 4 2 1 5
3 5 7 6 9 1 4 8 2
9 4 6 8 2 3 1 5 7
8 2 1 4 5 7 9 6 3
4 6 8 2 3 9 5 7 1
1 3 9 7 4 5 6 2 8
5 7 2 1 8 6 3 4 9

real    0m0.100s
user    0m0.085s
sys     0m0.003s

Takže ano, dovede řešit i těžké příklady.

[Haaja]

Jsou i težší případy, toto sudoku jak jste sem poslal jsem bez použití jakéhokoliv programu vyřešil cca za 25 minut a musel jsem provést tipnutí pouze tří čísel. Najdou se mnohem složitější. ;)

[kavol]

Sudoku je docela hit

hm, poprvé jsem to viděl před pár lety na matfyzáckejch přijímačkách, a najednou je z toho děsnej hit a říká se tomu sudoku, hm :)

btw, "poprvé" - co pamatuju, určitě se to vyskytuje i v nějaký starší literatuře ...

a navíc jsem si říkal, že "to přece nemůže být těžké".

správný postřeh

Asi po půl hodince jsem zjistil, že deterministické řešení daného rozložení prostě neexistuje

no ... většina mých známých (nejen informatici) to do té půlhodinky vyřeší ... ještě jsem neviděl zadání, které by k jednoznačnému řešení nevedlo ...

[bahno]

Ale ano, najdou se takove, jenze pak to neni sudoku. Sudoku zadani musi mit prave jedno reseni a to ze otisknou sudoku ktere jich ma vice je chyba.

[eXces]

Souhlas s jedním příspěvkem výše. Dnas velký hit, když jdem dělal přijímačky na MAT-FYZ tak jsem si přál ať to tam je, byla to ta nejstupidnější věc, co tam mohli hodit. S tou půlhodinou bych řekl, že to je přehnané. Tohle se řeší do pěti minut. Nechci pochybovat o tvojí inteligenci, ale je celkem nemožný to nevyřešit, pokud to jako neřešitelný není vyrobený...

[Honza "tux" Friesse]

Nechci pochybovat o Vašem egu, ale myslím, že by bylo dobré ho snížit (hodně). Jinak, nevím, že bychom se spolu znali, že si tykáme. A řešit za 5 minut to nejtěžší Sudoku... no nevím nevím.

[eXces]

Sorry za to tykání. Je jasné, že když máte to nejtěžší sudoku, tak je fakt těžký to vyřešit.

[kavol]

no, jsou tací, co to za pět minut tak sotva ručně zkontrolují, že to splňuje podmínky (trošku přeháním, ale ne moc ... a nejsou blbí, jen pomalí)

p.s. "Nechte si už těch svých Kidů!" - nemělo tam být "Nestojím o vaše Kidy"? (případně "I do not care for your kids."?)

[merlik]

Pekne reseni... ;)

[Pavel 'lingeek' Szalbot]

Nechci být sprostý a bývám i slepý, ale pokud místo "prohledávání do hloubky realizované zásobníkem (místo rekurze)" musíš napsat odstavec o tom ... nevím, jak to nazvat ... možná bych si být tebou rozšířil obzory (i v angličtině). Nicméně gratuluju, že jsi úlohu vyřešil a máš z toho radost, to je hlavní.

[Honza "tux" Friesse]

Ale právěže tam není ani rekurze, ani zásobník, vše pracuje pouze v tom poli.

Obzory v angličtině rozšiřuji jak se to jen dá, ale čeština je krásná a myslím, že i informatik by se měl umět vyjádřit v češtině.

Mám radost

[Pavel 'lingeek' Szalbot]

Zásobník to není pravý, je to přímo na místě, budiž. Pěkné.

[janosh]

kdyby se radeji ucil na zkousky

[Honza "tux" Friesse]

Tak někdo paří AOE 3 či jiné, a někdo holt píše v C nerekurzivní, bezzásobníkové (prostě in-situ) řešení Sudoku no. A stejně mě to IMS nebavilo.

[jarek.cz]

Pekny algoritmus na prohledavani reseni (i s popisem) se da najit tady: http://en.wikipedia.org/wiki/Algorithmics_of_Sudoku#Discussion_of_the_reference_implementation

Pred casem sem k nemu vytvoril webove rozhrani: http://www.jarek.cz/logicke-hadanky/sudoku/automaticky-vyresit/

[raven]

Zdravím všechny,

nemá někdo náhodou kód popisovaného řešení sudoku? Odkaz autora již nefunguje a zdroják by mi dost hodně pomohl

Díky všem