Soduko solver, starthjälp

Detta skulle säkert bli en bra programmeringstävling

Har funderat på hur man skulle kunna lösa detta tidigare, men inte kommit på något riktigt bra sätt. Men det skulle vara väldigt kul att sätta sig ned med det någon gång när man har en massa tid över.

Inte för att jag är så värst insatt i Sudoko .. men en Breadth-First sökning bör fungera och vara enkel att implementera .. språket spelar inte allt för stor roll, men om du vill ha den snabb och minneseffektiv så rekommenderas C/C++.

Sudoku. Med två U.

Faktiskt en riktigt bra programmeringstävling. Kanske ska vi försöka på något till helgen!
Problemet är väl att det finns tusen algoritmer redan ute på webben..

En consoleapp där du kan flytta runt i en matris? Lättast är nog bara enkelt korrdinatsystem där du skriver kordinater och sedan siffran.

  A B C
1 X X X 
2 X X X
3 X X X
Change (A2 5):

Här finns alla tekniker för att lösa sudokus. Om man implementerar dessa har man ett väl fungerande program, som klarar de flesta sudokus. Gissande är förbjudet, alla tal man fyller i måste följa logiskt av de man redan har!
http://www.angusj.com/sudoku/hints.php

Tänkte det skulle vara ett trevligt tidsfördriv ikväll

import Helper
cRow s i = [s!!!(i,p) | p<-[0..8], s!!!(i,p) /= 0]
cCol s j = [s!!!(p,j) | p<-[0..8], s!!!(p,j) /= 0]
cBox s i j = [s!!!(p,q) | p<-(box i),q<-(box j), s!!!(p,q) /= 0]
box n = [(3*(div n 3))..(3*(div n 3) +2)]
done s = null $ [s!!!(p,q) | p<-[0..8],q<-[0..8], s!!!(p,q) == 0]
free s i j = [y|y<-[1..9],notElem y $ (cRow s i)++(cCol s j)++(cBox s i j)]
sudoku s | done s    = s
         | otherwise = sudoku $ unConcat 9 $ 
                        [if s!!!(i,j) == 0 && (length $ free s i j) == 1
                          then head $ free s i j
                          else s!!!(i,j)
                         |i<-[0..8],j<-[0..8]]

test = 
   [[0,6,0,1,0,4,0,5,0],
    [0,0,8,3,0,5,6,0,0],
    [2,0,0,0,0,0,0,0,1],
    [8,0,0,4,0,7,0,0,6],
    [0,0,6,0,0,0,3,0,0],
    [7,0,0,9,0,1,0,0,4],
    [5,0,0,0,0,0,0,0,2],
    [0,0,7,2,0,6,9,0,0],
    [0,4,0,5,0,8,0,7,0]]

easy =
   [[0,6,0,1,0,4,2,5,0],
    [0,0,8,3,0,5,6,0,0],
    [2,0,0,0,0,0,0,0,1],
    [8,0,0,4,0,7,0,0,6],
    [0,0,6,0,0,0,3,0,0],
    [7,0,0,9,0,1,0,0,4],
    [5,0,0,0,0,0,0,0,2],
    [0,0,7,2,0,6,9,0,0],
    [0,4,0,5,0,8,0,7,0]]

Och från Helper.hs

...
-- 2D !!
(!!!) :: [[a]] -> (Int,Int) -> a
(!!!) x (i,j) = (x !! i) !! j

-- unConcat, splits up to a list again
unConcat :: Int -> [a] -> [[a]]
unConcat _ [] = []
unConcat 0 _  = error "Can't do 0 elements / row"
unConcat i a | (length a) < i = error "Can't be split up"
             | otherwise      = [take i a] ++ unConcat i (drop i a)
...

Men den är för dum just nu!
Jag behövde hjälpa den med ett extra värde så kunde den ta den, får väl ta och fixa det lite senare

Har polare som håller på med det där faktiskt, just en sodukosolver. Kan ju säga att det är inte det lättaste att programmera. De provar lite olika lösningar, får se vilken som funkar bäst, om någon funkar vill säga...

Bara för det var jag tvungen att prova. Funkar fint på lättare varianter, provade en svår och då gick det inte. Får kolla lite mer på det i helgen.

Gjord i qbasic för övrigt.

Jag snickrade ihop en liten SuDoku-lösare i c++ för ett tag sedan. Den fungerar ganska bra faktiskt.

Gjorde ett web-interface till den:
http://ookk.mine.nu/SuDoku/sudoku.php

Här är källkoden till c++-programmet:
http://ookk.mine.nu/SuDoku/SuDokuSolver.cpp

Kul att jag hittade den här tråden nu, jag började nämligen i veckan att jobba på en sudoku solver till pocket pc (funkar på vanlig pc också). Just nu löser den alla lätta och medelsvåra. Jag använder 3 olika algoritmer för att lösa pusslena med. Jag hittade först på en egen som till min förvåning löste alla enkla direkt, tog bara någon timme att skriva den.

Jag hittade sedan en hemsida som har en sudoku solver, och förklarar hur logiken fungerar: http://www.sudokusolver.co.uk/solvemethods.html . Jag har implementerat metod A och metod B enligt dom metoderna. Metod B funkar inte riktigt som den ska än, så den klarar fortfarande inte dom svåraste. Jag har även lagt in så att den kan rätta färdiga lösningar.

Jag skrev även en fjärde algoritm som testar slumpmässiga lösningar när ingen lösning hittas, och då klarade den att lösa dom svåraste ibland, men inte alltid.

Tycker det borde gå att göra en lösning på problemet som klarar alla sudukos som går att lösa.. klart iterativtproblem.

Mitt program klarar det, jag använder en rekursiv sökning.

Du har inte lust att släppa den i php?

Fast ditt program verkar ju inte lösa problemet genom logik, utan snarare genom att testa sig fram till första bästa lösning. Det klarar ju till och med att ta fram en lösning på en helt tom sudoku. Lite fusk att göra så tycker jag

php-sidan kommunicerar med c++-programmet så jag har ingen php-kod för själva sudoku-lösaren.

Pff. klarar programmet att lösa uppgiften är det ju inte fusk!
Lyckas man göra en så pass bra bruteforce som blir klar den här evigheten så har man gjort rätt tycker jag.

Efter att ha läst lite på http://www.setbb.com/phpbb/?mforum=sudoku så verkar det som om det finns sudokus som inte går att lösa på annat sätt än genom att testa sig fram på ett eller annat sätt, så om man vill göra ett program som klarar alla sudokus har man inget val, man måste ha en funktion för att testa sig fram med (även om dom flesta sudokus går att lösa logikvägen).

Crap!

Då är det väl bara sätta sig och läsa igenom din kod 2000 gånger till jag kan konvertera till php själv då :(.

Jag har en version av koden skriven i python om det är till någon hjälp.
http://ookk.mine.nu/SuDoku/SuDokuSolver.py

Jag kan c++ och php, så det är nog lättare att konvertera från c++, men tack ändå :).

Jo, det vet jag, men utmaningen ligger ju i att försöka klara så svåra sudokus som möjligt med bara logik. Sidan jag länkade till har flera svårighetsgrader på sodukos, och en avdelning med sudokus som inte går att lösa med logik.

Jag började koda en lösare för ett tag sedan. När jag implementerat flera knep men trots det misslyckades på några sudokus, så började jag googla och hittade sidan ovan som Igor nämnde (http://www.angusj.com/sudoku/hints.php), där det stod att det finns sudokus som helt enkelt inte går att lösa rent deduktivt, så jag blev lite deprimerad och blev tvungen att ge upp. Men en djupet-först-sökning är rätt trivialt att implementera.