Reklama
Nepřihlášený uživatel | Zaregistrovat se
 

Téma:

Hry počítačové i jinéOdpad

Spravuje:

Twiggy_4st_7lb



Reklama



Slyšeli jste už o Sudoku? Hře, která u nás vychází v lidovkách a spousta hracích plánů je k mání na internetu?

http://www.angusj.com/sudoku/
http://www.sudoku-league.com/cz/

Twiggy_4st_7lb   25.srpen 2005 11:20:32
Blanchetta
ano stydim se :)))))))))
twiggy : jasne, program
pokud jde o algoritmus, tak ve svym programu mam jeden takovej naivni zpusob implementovanej
delat to rucne, to bych se asi zblaznil
no a není to pravda? ještě máš co zlepšovat :-)
Twiggy_4st_7lb   24.srpen 2005 19:53:40
Blanchetta: tak tam me opravdu pobavilo, kdyz sem nedoplnil nic, dal zkontrolovat a bylo mi oznameno, ze se jeste mam v cem zlepsovat a jestli sem si precetl, jak se to vubec hraje! :D
nebo je taky dobrá stránka sudoku
Twiggy_4st_7lb   24.srpen 2005 10:13:36
Já osobně bych zkusil lidovky: http://zpravy.centrum.cz/sudoku/
Byl by odkaz na nejake vysvetelni?
Twiggy_4st_7lb   23.srpen 2005 17:03:43
pafaa
hele - a to delas rucne, nebo mas sestrojeny nejaky program?
Twiggy_4st_7lb   23.srpen 2005 17:03:27
Blanchetta: melo by mit, ale uz nize sem popsal i jedno sudoku z lidovek, ktere melo resini 2, sice to bylo vcelku zanedbatelne (jen se prohodila 2 cisla), ale prece jenom, pul casu reseni sem nevedel, kde ktere bude a notne me to otravovalo
Musí mít sudoku vždy právě jedno řešení?
no nastesti uz jsem to uz nekomu popisoval, tak to sem muzu preprsknout a mam to bez prace

Pokud jde o můj algoritmus na generování, je vcelku prostý: nejprve do prázdné tabulky rozházím náhodně 30 čísel (ale tak, aby byly splněny podmínky řešení: v žádném řádku/sloupci/regionu nesmí ležet dvě stejná čísla) a tuto tabulku vyřeším (i s tím, že mohu dostat více možných kompletních tabulek sudoku). Číslo 30 je magická konstanta získaná metodou pokus/omyl, pokud dám totiž na začátek do tabulky méně prvků, je řešení hodně a výpočet trvá dlouho, pokud dám naopak více, často žádné řešení není a je nutno tuto fázi opakovat. Jakmile tedy počáteční tabulku vyřeším, vyberu z výsledků náhodně jednu tabulku. A z té potom vybírám prvky. Po každém odebrání prvku (respektive dvojice prvků, pokud chci zachovávat symetričnost tabulky) novou sudoku vyřeším, a pokud obdržím právě jedno řešení, je vše v pořádku a pokračuji stejným způsobem, pokud je řešení více, prvek (dvojici prvků) do tabulky vrátím a zkusím odebrat prvek na jiné pozici.
Algoritmus je to triviální, a pro volbu obtížnosti zde není příliš mnoho prostoru. Jako základní volbu obtížnosti tedy používám počet odebraných prvků, a pak ještě způsob řešení: pro jednoduchou obtížnost řeším tabulku pouze metodou rastrování/skenování, a pokud tato metoda selže, beru to jako neřešitelnou úlohu. Teprve na vyšší obtižnosti dovoluji pro kontrolní řešení ve větší či menší míře používat metodu výpočetně úplnou (v tomto případě hledání odpovídajících si dvojic (neznám český ekvivalent, na wikipedii tomu říkají "matching pairs") + metoda hrubé síly:)).

jinak, kdyby mel nekdo tu trpelivost a popsal tady nejake pokrocilejsi resici techniky (znam jen nazvy z cizich diskuzaku: swordfish, x-wing, barveni...), urcite by to bylo ku prospechu veci..............

jo a taky si pls neutahujte z jednoduchosti algoritmu, ja vas varoval:)
Twiggy_4st_7lb   20.srpen 2005 10:45:27
pafaa
no me by to teda joooo zajimalo :)
Nevíte, existuje někde na netu sudoku v obrázkové verzi?
s tou obtiznosti tezko rict, ja bych ji urcoval podle technik, ktery je nutno k vyreseni pouzit (nektery jsou tezsi, nektery lehci), ale jako velmi hruby odhad by myslim mohl stacit i pocet urcenych prvku.
pokud jde o algoritmus, tak ve svym programu mam jeden takovej naivni zpusob implementovanej, ale verim, ze sami byste prisli na lepsi, takze ho popisu jen kdyz budete joooo chtit:)
Podle čeho se určuje obtížnost?
Tak jsem sudoku objevila před týdnem, a řeknu vám, je to děs, asi by to měli zakázat :-))
Twiggy_4st_7lb   3.srpen 2005 11:42:02
no to by me taky zajimalo...nejvic by meale zajimalo, proc se pise, ze ma vzdy jen jedno reseni, kdyz i v tom, co bylo v lidovkach byla reseni dve - nevim uz kdy, ale staci, aby ve dvou radach u sebe byla kombinace dvou cisel...treba

X3XXXX6XX
X6XXXX3XX

samozrejme musi to sedet i s malymi ctverci...
Uz jsem po netu brouzdal a nasel jsem si par programu na generovani a lusteni, ale docela by me zajimalo matematicjke pozadi. Existuje treba nejaky algoritmus na vytvareni sudoku?
JA si vsiml....
Twiggy_4st_7lb   22.červen 2005 14:19:19
TAK
To sem zvědav, zda si někdo všimne :-/