Sudoku solve, prestanda

[Kim Simmons]

Just hur lång tid kan egentligen en lösning ta i värsta fall med den naiva backtrack versionen av solve?

Vi är osäkra hurvida vi har en bug, eller om det faktiskt bara tar vansinnigt lång tid för vissa sudokus att bli lösta. Det kan ta timtal för vissa test fall. Först trodde vi att vår funktion gick i en oändlig loop, men nu är vi inte lika säkra. Test funktionen har klarat att gå över hundra fall några gånger.. nuvarande runda har tagit 12 timmar och precis klarat 100 tester. Några specifika tester har nog tagit över två timmar.

[Thomas Högberg]

För oss tar det ett par minuter, Utan att vi har optimerat vår generator eller dylikt.

[mortberg]

Jag håller med om att det låter långsamt... Har ni testat att
kompilera koden och köra time på den?

Dvs ni byter modulnamnet till Main, importerar System.Environment och lägger in

main :: IO ()
main = do
  args <- getArgs
  readAndSolve (head args)

För att kompilera kör ni ghc --make -O2 Sudoku.hs och sen kan ni köra:

time ./Sudoku easy10.sud
761928453
925743168
438615927
357461289
894372615
216589374
689154732
142837596
573296841


real    0m1.027s
user    0m1.017s
sys     0m0.007s


Om ni packar upp sudoku.zip i en mapp som heter sudoku och sen flyttar
alla lätta i en undermapp som heter easy kan ni köra:

for x in $(ls sudokus/easy); do echo; echo $x; time ./Sudoku
sudokus/easy/$x ; done

För att köra time på alla lätta sudokus, detta kan ni sen jämföra med
andra grupper för att se om er lösning är väldigt långsam. Om det
visar sig att den är det kan vi hjälpa er att försöka få den snabbare
på ett labbpass.

--
Anders

[Kim Simmons]

Bra tips Anders, jag har kört alla easy* i sudokus.zip. Det tog mig 1m 48s totalt, vilket låter ganska rimligt. Jag bifogar resultatet.

Jag har också funnit en sudoku som tar vansinnigt lång tid (genererad av quickCheck), bifogad som 'badSud.sud'. Den är nog uppe i snudd på 10 timmar och ännu inte klar.. Om någon har lust att köra time på den och se om den iaf tar över en timme eller inte?

Thomas, vad tar ett par minuter exakt? 100 slumpmässiga sudokus i quickCheck? Varje gång?

Har funderat lite på hur många steg som kan råka genereras av en 'inoptimal' sudoku. Ett rutnät 9x9 med 9 olika siffror kan väl ge 9^81 kombinationer.. algoritmen går såklart inte alls så långt, men om den gör ett dåligt beslut i början som inte stämmer precis i slutet skulle betyda en total omräkning ett flertal gånger. Låter det orimligt att det kan finnas en sudoku som genererar några billjoner steg i en naiv backtrack algoritm?

[Anders]

Det finns 6670903752021072936960 ~= 6.67*10^21 giltiga sudokus (http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_the_Sudoku_9.C3.979_grid_solutions_directly), så att behöva göra ett par biljoner försök innan man hittar en giltig lösning på en slumpmässigt genererad sudoku låter helt klart möjligt.

Ett bra sätt att lista ut hur algoritmen funkar är att skriva en ny version är solve där man sätter in en siffra, printar sudokun och sen kör vidare. Om man även kör clear screen och sleep mellan varje utskrivning får man en fin film/animering av hur sudokun fylls upp med siffror.

Om ni vill göra detta rekommenderar jag er att kolla på:

http://hackage.haskell.org/packages/archive/ansi-terminal/0.5.0/doc/html/System-Console-ANSI.html   (för clear screen och att flytta markören dit ni vill, installera paketet genom att köra cabal install ansi-terminal)
http://hackage.haskell.org/packages/archive/unix/latest/doc/html/System-Posix-Unistd.html#v:usleep   (för att söva tråden)