Sudoku (diskuse)

[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