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

Téma:

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

Spravuje:

Twiggy_4st_7lb

Reklama


Zasláno do klubu

Sudoku


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:)