hvilke problemer kan programmer have med at løse sudokuer?

Jeg kan desværre ikke henvise til nogen kilder, men Sudoku-problemet er et såkaldt NP-komplet problem. Det betyder, at for at finde det bedste resultat, skal programmet løse samtlige tal-kombinationer.
Det man så gør med NP-komplette problemer er, at man anvender en heuristisk tilgang.

Det er dette NP-komplette problem der er det centrale problem for løsning af en Sudoku.

Der er ikke nogen definerbare mønstre som giver problemer.

Hovedsagen er at sudokuer er kombinatoriske problemer, dvs. at de som udgangspunkt kan løses ved at afprøve samtlige forskellige kombinationer.

Der er blot alt for mange forskellige muligheder til at det er muligt indenfor en rimelig tid at afprøve dem alle. Derfor må et sudokuløsningsprogram ligesom et menneske trinvist finde dele af svaret ved hjælp af diverse udelukkelsesmetoder. Hvis ingen af de givne metoder giver et svar må programmet gætte og derudfra arbejde sig videre og prøve om den kombination kan lade sig gøre, hvis ikke må programmet så gå tilbage og afprøve en anden mulighed. Jo flere steder programmet laver sådanne gæt, jo flere forgreninger bliver der i programflowet, og jo længere tid tager det. Tiden det tager stiger omtrentligt eksponentielt med antallet af forgreninger, så der må ikke forekomme for mange forgreninger hvis det skal blive færdigt indenfor en rimelig tid.

Det er vigtigt at programmet ikke blot placerer et tal så snart det har udelukket de 8 andre, men også tjekker om det kan udelukke det 9. og således bevise at den gren det arbejder på er umulig.

Hvis programmet er sat til at finde samtlige mulige løsninger i stedet for blot en løsning så kommer sudokuer med mange løsninger også til at tage lang tid.

Du kan finde masser af tips og hjælp her, både med programmering og med matematikken (der godt kan blive noget langhåret):
http://www.setbb.com/phpbb/index.php?mforum=sudoku

Helt uden matematik, og med simpel backtracking: http://erikjacobsen.com/sudoku/

Jo flere tal, der er givet, jo hurtigere går det.

Ja, jeg skulle måske lige præcisere: På det forum jeg refererede til arbejdes der primært med programmer, der søger løsninger ved reæsonnement. Altså uden at gætte, og gøre det således at man (i hvert fald i teorien) kan eftergøre det i hånden. Altså modsat erik's "Bruteforce" løser.

@erikjacobsen

Jeg havde egentlig troet at opgaven var for kompliceret til så simpel brute force, men åbenbart ikke.

Tag du og skriv en version til 16x16 sudokuer ;-)

Det er ikke brute force - det er backtracking. Placeringer der ikke giver meningen udforskes ikke yderligere. Man kan optimere lidt på hvor man starter, men det gør min simple version ikke.

Tak for svarene. Der kom ikke noget så konkret som jeg havde håbet på, men der kom nogle stikord og begreber jeg vil søge videre på. tak fordi i lånte mig lidt af jeres tid