Bla bl.a.

Program för att lösa Sudoku

Har funderat på att bygga ett program som löser Sudoku-pussel automatiskt ett tag nu. En simpel algoritm är följande:

1. Upprepa följande, så länge det finns någon tom ruta i pusslet:
2. Leta upp en ruta, som har precis en "kandidatsiffra"
3. Fyll i rutan med kandidaten

Det låter väldigt enkelt, men jag tror att det räcker långt. Fullt ut vet jag inte ännu. Så jag funderar på att koda ihop algoritmen (mha. TDD såklart!) och se hur långt den räcker.

I Pseudokod skulle de kunna se ut något sånt här:

sudoku = GetInputSudoku()
GreedySolver(sudoku)
print sudoku

function GreedySolver(sudoku)
__do
____pos = FindCandidatePos(sudoku)
____if pos!=null
______sudoku.Set(pos, sudoku.FindCandidates(pos)[0])
__while pos!=null

function FindCadidatePos(sudoku)
__foreach(pos in sudoku)
____cands = sudoku.FindCandidates(pos)
____if(cands.Count == 1)
______return pos
__return null


Läs även andra bloggares åsikter om programmering, sudoku, tdd

Jag tror att algoritmen du föreslår inte räcker riktigt. Det är inte alltid som man är i ett läge där det finns någon ruta som bara har en kandidatsiffra. Man måste då göra lite mer avancerade uteslutningsmetoder.

Jepp, upptäckte det också efter diskussion med Mozhdeh . Men det kanske duger som "stödprogram"..?

Är nästan klar med en version av programmet förresten.

i sanning, det skulle underlätta det första stadiet