Python —> Sudoku
De Sudoku puzzel is een 9×9 matrix met 81 velden die gevuld moeten worden. Op iedere rij, in iedere kolom en binnen ieder blok moeten de getallen 1 t/m 9 worden ingevuld, zonder dat een getal dubbel voorkomt. Dat zijn dus 27 voorwaarden. Door iedere cel als volgt te nummeren
kunnen de 27 voorwaarden aan de volgende getal-reeksen worden gekoppeld.
De rijen:
- 1, 2, .. , 9
- 10, 11, .. , 18
:
: - 73, 74, .. , 81
De kolommen:
- 1, 10, .. , 73
- 2, 11, .. , 74
:
: - 9, 18, .. , 81
De blokken:
- 1, 2, 3, 10, 11, 12, 19, 20, 21
- 4, 5, 6, 13, 14, 15, 22, 23, 24
:
: - 61, 62, 63, 70, 71, 72, 29, 80, 81
Een algoritme zou alle mogelijkheden langs kunnen lopen. Dat houdt in dat in iedere cel een van de getallen 1 t/m 9 zal worden ingevuld. Dat is erg inefficiënt omdat bijvoorbeeld 2 dezelfde getallen naast elkaar sowieso al niet zijn toegestaan. Je kunt het aantal combinaties flink te verminderen door tijdens de zoektocht ervoor te zorgen dat per blok altijd 9 verschillende getallen worden ingevuld. Echter ook dan gaat het nog om enorm veel combinaties. Immers, in ieder van de 9 blokken zijn er 362.880 mogelijke combinaties (9*8*7*6*5*4*3*2). In de meeste blokken zijn al getallen aanwezig. Dat reduceert het aantal combinaties. Is er één ingevuld dan daalt het aantal met een factor 9. Zijn er twee ingevuld dan daalt het met een factor 9*8. Het aantal mogelijkheden voor de hele Sudoku is gelijk aan het product van het aantal combinaties per blok. Dat gaat om extreem veel. De vraag is hoe het algoritme geoptimaliseerd kan worden.
In het boek Softwareontwerp en programmeren met Python 3 van Ignace Van de Woestyne & Jan Vathienen wordt uitgelegd hoe een Sudoku opgelost kan worden met behulp van backtracking. Zij kiezen voor een benadering, waarbij de condities veel meer vanuit een matrix-structuur worden getest. Ik heb voor een meer generieke werkwijze gekozen, door de 81 velden als één vector te zien. De 27 voorwaarden kunnen dan worden gekoppeld aan telkens 9 elementen uit de vector. In mijn aanpak worden achtereenvolgens de lege vector-elementen gevuld. Zodra duidelijk wordt dat het niet voldoet aan één van de 27 voorwaarden, wordt direct gestopt met het verder invullen en wordt teruggegaan naar een eerdere stap.
Voorbeeld van een op te lossen Sudoku:
Hieronder staan voor een voorbeeld alle processtappen die het algoritme heeft gezet. Een -1 geeft aan dat in dat geen toegestaan getal mogelijk is en dat backtracking wordt uitgevoerd.
Op te lossen sudoku:
0 0 7 6 0 0 0 0 0
0 0 3 0 4 5 0 0 2
0 0 0 0 0 0 5 9 0
0 0 0 0 0 0 0 4 0
0 4 1 0 2 0 0 0 0
3 0 0 0 0 9 0 0 0
5 0 0 7 0 4 9 0 0
0 8 0 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
1
---------------------------
Veld
---------------------------
index 1
rij 1
kolom 1
---------------------------
Blok (veld linksboven)
---------------------------
index 1
rij 1
kolom 1
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
stap 1: geldig getal gevonden
1 0 7 6 0 0 0 0 0
0 0 3 0 4 5 0 0 2
0 0 0 0 0 0 5 9 0
0 0 0 0 0 0 0 4 0
0 4 1 0 2 0 0 0 0
3 0 0 0 0 9 0 0 0
5 0 0 7 0 4 9 0 0
0 8 0 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
2
---------------------------
Veld
---------------------------
index 2
rij 1
kolom 2
---------------------------
Blok (veld linksboven)
---------------------------
index 1
rij 1
kolom 1
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
2
---------------------------
Veld
---------------------------
index 2
rij 1
kolom 2
---------------------------
Blok (veld linksboven)
---------------------------
index 1
rij 1
kolom 1
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
stap 2: geldig getal gevonden
1 2 7 6 0 0 0 0 0
0 0 3 0 4 5 0 0 2
0 0 0 0 0 0 5 9 0
0 0 0 0 0 0 0 4 0
0 4 1 0 2 0 0 0 0
3 0 0 0 0 9 0 0 0
5 0 0 7 0 4 9 0 0
0 8 0 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
3
---------------------------
Veld
---------------------------
index 5
rij 1
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
3
---------------------------
Veld
---------------------------
index 5
rij 1
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
3
---------------------------
Veld
---------------------------
index 5
rij 1
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
stap 3: geldig getal gevonden
1 2 7 6 3 0 0 0 0
0 0 3 0 4 5 0 0 2
0 0 0 0 0 0 5 9 0
0 0 0 0 0 0 0 4 0
0 4 1 0 2 0 0 0 0
3 0 0 0 0 9 0 0 0
5 0 0 7 0 4 9 0 0
0 8 0 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
4
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
4
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
4
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
4
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 4
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
4
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 5
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
4
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 6
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
4
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 7
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
4
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 8
---------------------------
Resultaat
---------------------------
stap 4: geldig getal gevonden
1 2 7 6 3 8 0 0 0
0 0 3 0 4 5 0 0 2
0 0 0 0 0 0 5 9 0
0 0 0 0 0 0 0 4 0
0 4 1 0 2 0 0 0 0
3 0 0 0 0 9 0 0 0
5 0 0 7 0 4 9 0 0
0 8 0 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
5
---------------------------
Veld
---------------------------
index 7
rij 1
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
5
---------------------------
Veld
---------------------------
index 7
rij 1
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
5
---------------------------
Veld
---------------------------
index 7
rij 1
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
5
---------------------------
Veld
---------------------------
index 7
rij 1
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 4
---------------------------
Resultaat
---------------------------
stap 5: geldig getal gevonden
1 2 7 6 3 8 4 0 0
0 0 3 0 4 5 0 0 2
0 0 0 0 0 0 5 9 0
0 0 0 0 0 0 0 4 0
0 4 1 0 2 0 0 0 0
3 0 0 0 0 9 0 0 0
5 0 0 7 0 4 9 0 0
0 8 0 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
6
---------------------------
Veld
---------------------------
index 8
rij 1
kolom 8
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
6
---------------------------
Veld
---------------------------
index 8
rij 1
kolom 8
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
6
---------------------------
Veld
---------------------------
index 8
rij 1
kolom 8
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
6
---------------------------
Veld
---------------------------
index 8
rij 1
kolom 8
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 4
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
6
---------------------------
Veld
---------------------------
index 8
rij 1
kolom 8
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 5
---------------------------
Resultaat
---------------------------
getal komt al voor in dit blok
---------------------------
Stap
---------------------------
6
---------------------------
Veld
---------------------------
index 8
rij 1
kolom 8
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 6
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
6
---------------------------
Veld
---------------------------
index 8
rij 1
kolom 8
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 7
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
6
---------------------------
Veld
---------------------------
index 8
rij 1
kolom 8
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 8
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
6
---------------------------
Veld
---------------------------
index 8
rij 1
kolom 8
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 9
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
stap 6: geen geldig getal ---> backtrack
1 2 7 6 3 8 4-1 0
0 0 3 0 4 5 0 0 2
0 0 0 0 0 0 5 9 0
0 0 0 0 0 0 0 4 0
0 4 1 0 2 0 0 0 0
3 0 0 0 0 9 0 0 0
5 0 0 7 0 4 9 0 0
0 8 0 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
7
---------------------------
Veld
---------------------------
index 7
rij 1
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 5
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
7
---------------------------
Veld
---------------------------
index 7
rij 1
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 6
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
7
---------------------------
Veld
---------------------------
index 7
rij 1
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 7
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
7
---------------------------
Veld
---------------------------
index 7
rij 1
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 8
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
7
---------------------------
Veld
---------------------------
index 7
rij 1
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 7
rij 1
kolom 7
---------------------------
Invulpoging
---------------------------
getal 9
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
stap 7: geen geldig getal ---> backtrack
1 2 7 6 3 8 -1 0 0
0 0 3 0 4 5 0 0 2
0 0 0 0 0 0 5 9 0
0 0 0 0 0 0 0 4 0
0 4 1 0 2 0 0 0 0
3 0 0 0 0 9 0 0 0
5 0 0 7 0 4 9 0 0
0 8 0 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
8
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 9
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
stap 8: geen geldig getal ---> backtrack
1 2 7 6 3-1 0 0 0
0 0 3 0 4 5 0 0 2
0 0 0 0 0 0 5 9 0
0 0 0 0 0 0 0 4 0
0 4 1 0 2 0 0 0 0
3 0 0 0 0 9 0 0 0
5 0 0 7 0 4 9 0 0
0 8 0 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
9
---------------------------
Veld
---------------------------
index 5
rij 1
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 4
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
9
---------------------------
Veld
---------------------------
index 5
rij 1
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 5
---------------------------
Resultaat
---------------------------
getal komt al voor in dit blok
---------------------------
Stap
---------------------------
9
---------------------------
Veld
---------------------------
index 5
rij 1
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 6
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
9
---------------------------
Veld
---------------------------
index 5
rij 1
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 7
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
9
---------------------------
Veld
---------------------------
index 5
rij 1
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 8
---------------------------
Resultaat
---------------------------
stap 9: geldig getal gevonden
1 2 7 6 8 0 0 0 0
0 0 3 0 4 5 0 0 2
0 0 0 0 0 0 5 9 0
0 0 0 0 0 0 0 4 0
0 4 1 0 2 0 0 0 0
3 0 0 0 0 9 0 0 0
5 0 0 7 0 4 9 0 0
0 8 0 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
10
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10
---------------------------
Veld
---------------------------
index 6
rij 1
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 4
rij 1
kolom 4
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
stap 10: geldig getal gevonden
1 2 7 6 8 3 0 0 0
0 0 3 0 4 5 0 0 2
0 0 0 0 0 0 5 9 0
0 0 0 0 0 0 0 4 0
0 4 1 0 2 0 0 0 0
3 0 0 0 0 9 0 0 0
5 0 0 7 0 4 9 0 0
0 8 0 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
:
:
:
:
:
:
:
:
:
:
:
:
:
: tussenstappen
: weggelaten
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
---------------------------
Stap
---------------------------
10779
---------------------------
Veld
---------------------------
index 66
rij 8
kolom 3
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10779
---------------------------
Veld
---------------------------
index 66
rij 8
kolom 3
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10779
---------------------------
Veld
---------------------------
index 66
rij 8
kolom 3
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10779
---------------------------
Veld
---------------------------
index 66
rij 8
kolom 3
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 4
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10779
---------------------------
Veld
---------------------------
index 66
rij 8
kolom 3
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 5
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10779
---------------------------
Veld
---------------------------
index 66
rij 8
kolom 3
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 6
---------------------------
Resultaat
---------------------------
stap 10779: geldig getal gevonden
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 0 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
10780
---------------------------
Veld
---------------------------
index 68
rij 8
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10780
---------------------------
Veld
---------------------------
index 68
rij 8
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10780
---------------------------
Veld
---------------------------
index 68
rij 8
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10780
---------------------------
Veld
---------------------------
index 68
rij 8
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 4
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10780
---------------------------
Veld
---------------------------
index 68
rij 8
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 5
---------------------------
Resultaat
---------------------------
stap 10780: geldig getal gevonden
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 5 0 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
10781
---------------------------
Veld
---------------------------
index 69
rij 8
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10781
---------------------------
Veld
---------------------------
index 69
rij 8
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10781
---------------------------
Veld
---------------------------
index 69
rij 8
kolom 6
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
stap 10781: geldig getal gevonden
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 5 3 0 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
10782
---------------------------
Veld
---------------------------
index 70
rij 8
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10782
---------------------------
Veld
---------------------------
index 70
rij 8
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
stap 10782: geldig getal gevonden
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 5 3 2 7 0
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
10783
---------------------------
Veld
---------------------------
index 72
rij 8
kolom 9
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10783
---------------------------
Veld
---------------------------
index 72
rij 8
kolom 9
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10783
---------------------------
Veld
---------------------------
index 72
rij 8
kolom 9
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10783
---------------------------
Veld
---------------------------
index 72
rij 8
kolom 9
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 4
---------------------------
Resultaat
---------------------------
stap 10783: geldig getal gevonden
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 5 3 2 7 4
0 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
10784
---------------------------
Veld
---------------------------
index 73
rij 9
kolom 1
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10784
---------------------------
Veld
---------------------------
index 73
rij 9
kolom 1
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10784
---------------------------
Veld
---------------------------
index 73
rij 9
kolom 1
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10784
---------------------------
Veld
---------------------------
index 73
rij 9
kolom 1
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 4
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10784
---------------------------
Veld
---------------------------
index 73
rij 9
kolom 1
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 5
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10784
---------------------------
Veld
---------------------------
index 73
rij 9
kolom 1
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 6
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10784
---------------------------
Veld
---------------------------
index 73
rij 9
kolom 1
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 7
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10784
---------------------------
Veld
---------------------------
index 73
rij 9
kolom 1
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 8
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10784
---------------------------
Veld
---------------------------
index 73
rij 9
kolom 1
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 9
---------------------------
Resultaat
---------------------------
stap 10784: geldig getal gevonden
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 5 3 2 7 4
9 0 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
10785
---------------------------
Veld
---------------------------
index 74
rij 9
kolom 2
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10785
---------------------------
Veld
---------------------------
index 74
rij 9
kolom 2
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10785
---------------------------
Veld
---------------------------
index 74
rij 9
kolom 2
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10785
---------------------------
Veld
---------------------------
index 74
rij 9
kolom 2
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 4
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10785
---------------------------
Veld
---------------------------
index 74
rij 9
kolom 2
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 5
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10785
---------------------------
Veld
---------------------------
index 74
rij 9
kolom 2
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 6
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10785
---------------------------
Veld
---------------------------
index 74
rij 9
kolom 2
---------------------------
Blok (veld linksboven)
---------------------------
index 55
rij 7
kolom 1
---------------------------
Invulpoging
---------------------------
getal 7
---------------------------
Resultaat
---------------------------
stap 10785: geldig getal gevonden
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 5 3 2 7 4
9 7 4 0 0 2 0 8 0
---------------------------
Stap
---------------------------
10786
---------------------------
Veld
---------------------------
index 76
rij 9
kolom 4
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
stap 10786: geldig getal gevonden
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 5 3 2 7 4
9 7 4 1 0 2 0 8 0
---------------------------
Stap
---------------------------
10787
---------------------------
Veld
---------------------------
index 77
rij 9
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10787
---------------------------
Veld
---------------------------
index 77
rij 9
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10787
---------------------------
Veld
---------------------------
index 77
rij 9
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10787
---------------------------
Veld
---------------------------
index 77
rij 9
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 4
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10787
---------------------------
Veld
---------------------------
index 77
rij 9
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 5
---------------------------
Resultaat
---------------------------
getal komt al voor in deze kolom
---------------------------
Stap
---------------------------
10787
---------------------------
Veld
---------------------------
index 77
rij 9
kolom 5
---------------------------
Blok (veld linksboven)
---------------------------
index 58
rij 7
kolom 4
---------------------------
Invulpoging
---------------------------
getal 6
---------------------------
Resultaat
---------------------------
stap 10787: geldig getal gevonden
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 5 3 2 7 4
9 7 4 1 6 2 0 8 0
---------------------------
Stap
---------------------------
10788
---------------------------
Veld
---------------------------
index 79
rij 9
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10788
---------------------------
Veld
---------------------------
index 79
rij 9
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10788
---------------------------
Veld
---------------------------
index 79
rij 9
kolom 7
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
stap 10788: geldig getal gevonden
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 5 3 2 7 4
9 7 4 1 6 2 3 8 0
---------------------------
Stap
---------------------------
10789
---------------------------
Veld
---------------------------
index 81
rij 9
kolom 9
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 1
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10789
---------------------------
Veld
---------------------------
index 81
rij 9
kolom 9
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 2
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10789
---------------------------
Veld
---------------------------
index 81
rij 9
kolom 9
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 3
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10789
---------------------------
Veld
---------------------------
index 81
rij 9
kolom 9
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 4
---------------------------
Resultaat
---------------------------
getal komt al voor in deze rij
---------------------------
Stap
---------------------------
10789
---------------------------
Veld
---------------------------
index 81
rij 9
kolom 9
---------------------------
Blok (veld linksboven)
---------------------------
index 61
rij 7
kolom 7
---------------------------
Invulpoging
---------------------------
getal 5
---------------------------
Resultaat
---------------------------
stap 10789: geldig getal gevonden
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 5 3 2 7 4
9 7 4 1 6 2 3 8 5
Sudoku is opgelost:
2 5 7 6 9 1 4 3 8
6 9 3 8 4 5 7 1 2
4 1 8 2 3 7 5 9 6
8 2 9 5 7 6 1 4 3
7 4 1 3 2 8 6 5 9
3 6 5 4 1 9 8 2 7
5 3 2 7 8 4 9 6 1
1 8 6 9 5 3 2 7 4
9 7 4 1 6 2 3 8 5
De totale rekentijd bedraagt slechts 0,32 sec. (Windows laptop met i5 1035G1 processor).
De volgende oplossing is gevonden:
