© Harry Broeders.
Deze pagina is bestemd voor studenten van de THRijswijk groepen EPm en EPv die de module SOPX1 volgen.
Op deze pagina wordt een programma beschreven waarmee de op dit moment populaire Sudoku puzzels kunnen worden opgelost. De Sudoku puzzel moet in een invoerbestand worden opgeslagen waarbij voor elk leeg hokje een nul moet worden ingevoerd.
De bovenstaande puzzel moet als volgt in het invoerbestand sudoku.txt worden opgeslagen:
1 0 0 0 0 0 0 0 6 0 0 6 0 2 0 7 0 0 7 8 9 4 5 0 1 0 3 0 0 0 8 0 7 0 0 4 0 0 0 0 3 0 0 0 0 0 9 0 0 0 4 2 0 1 3 1 2 9 7 0 0 4 0 0 4 0 0 1 2 0 7 8 9 0 8 0 0 0 0 0 0
Andere voorbeelden (afkomstig uit het boekje "Sudoku boek 3" ISBN: 90-5515-631-0) zijn sudoku098.txt, sudoku099.txt en sudoku100.txt.
Het programma vraagt om de naam van het invoerbestand en geeft dan de oplossing.
De sourcecode van het programma sudoku.c is als volgt:
#include <stdio.h>int leesin(int s[][9]) {char naam[80];FILE* invoer;int r, k;printf("Geef de naam van het invoerbestand: ");if (scanf("%79s", naam)!=1) {printf("Fout bij inlezen bestandsnaam.\n");return 0;}invoer=fopen(naam, "r");if (invoer==0) {printf("De file %s kan niet gevonden of niet gelezen worden.\n", naam);return 0;}for (r=0; r<9; r++) {for (k=0; k<9; k++) {if (fscanf(invoer, "%d", &s[r][k])!=1) {printf("Fout bij inlezen %s.\n""Dit bestand moet 81 getallen van een sudoku bevatten.\n""Lege plaatsen moeten met een 0 worden aangegeven.", naam);fclose(invoer);return 0;}if (s[r][k]<0 || s[r][k]>9) {printf("Fout bij inlezen %s.\n""Dit bestand moet 81 getallen tussen 0 en 10 van een sudoku bevatten.\n""Lege plaatsen moeten met een 0 worden aangegeven.", naam);fclose(invoer);return 0;}}}fclose(invoer);return 1;}void drukaf(int s[][9]) {int r, k;for (r=0; r<9; r++) {for (k=0; k<9; k++) {printf("%d ", s[r][k]);}printf("\n");}}int controleer(int s[][9]) {int r, k, b;// rijfor (r=0; r<9; r++) {int afvinklijst[9]={0};for (k=0; k<9; k++) {if (s[r][k]!=0 && ++afvinklijst[s[r][k]-1]>1) {return 0;}}}// kolomfor (k=0; k<9; k++) {int afvinklijst[9]={0};for (r=0; r<9; r++) {if (s[r][k]!=0 && ++afvinklijst[s[r][k]-1]>1) {return 0;}}}// blokfor (b=0; b<9; b++) {int afvinklijst[9]={0};int rb=b/3 * 3;int kb=b%3 * 3;for (r=rb; r<rb+3; r++) {for (k=kb; k<kb+3; k++) {if (s[r][k]!=0 && ++afvinklijst[s[r][k]-1]>1) {return 0;}}}}return 1;}int losop(int s[][9]) {int probeer(int [][9], int);int i;for (i=1; i<10; i++) {if (probeer(s, i)==1) {return 1;}}return 0;}int probeer(int s[][9], int p) {int r, k, i;for (r=0; r<9; r++) {for (k=0; k<9; k++) {if (s[r][k]==0) {s[r][k]=p;if (controleer(s)==0) {s[r][k]=0;return 0;}for (i=1; i<10; i++) {if (probeer(s, i)==1) {return 1;}}s[r][k]=0;return 0;}}}return 1;}int main() {int sudoku[9][9];int leesin(int [][9]);void drukaf(int [][9]);int controleer(int [][9]);int losop(int [][9]);if (leesin(sudoku)) {if (controleer(sudoku)==0) {printf("Deze sudoku is niet geldig!\n");}if (losop(sudoku)==0) {printf("Deze sudoku kun je niet oplossen!\n");}drukaf(sudoku);}fflush(stdin);getchar();return 0;}
We kunnen het best beginnen met het verklaren van het hoofdprogramma.
De getallen uit de Sudoku puzzel worden opgeslagen in de 2 dimensionale array
sudoku. Deze array bevat 9 x 9 = 81 int
getallen. Een lege plaats wordt aangegeven met een 0. In main
worden de prototypes van 4 functies gedefinieerd en worden deze functies
aangeroepen. De functie leesin leest de als argument meegegeven
2 dimensionale array in vanuit een tekstfile. Als het inlezen gelukt is geeft
deze functie de waarde 1 terug en als het inlezen niet gelukt is wordt de
waarde 0 teruggegeven. De functie controleer kijkt of de als
argument meegegeven 2 dimensionale array voldoet aan de regels van een Sudoku
puzzel. Daarbij worden de niet ingevulde vakjes (met de waarde 0) buiten
beschouwing gelaten. De functie losop probeert de als argument
meegegeven sudoku puzzel op te lossen. Als dit gelukt is geeft deze functie
de waarde 1 terug en als het oplossen niet gelukt is wordt de waarde 0
teruggegeven. Omdat al deze 4 functies een array als argument gebruiken werken
ze allemaal met call by reference. In feite wordt alleen het beginadres van
de array doorgegeven.
Bij het doorgeven van een meerdimensionale array aan een functie mag alleen het aantal elementen van de eerste dimensie worden weggelaten. Het aantal elementen van de overige dimensies is namelijk nodig om het adres van een bepaald element in de meerdimensionale array te kunnen berekenen. Dit is in de les verder uitgelegd. Is hier nog verdere uitleg nodig?
De functie leesin leest de sudoku uit het invoerbestand en vult
de 2 dimensionale array.
Bij het inlezen van bestandsnaam wordt
bufferoverrun voorkomen. Als het openen
van het invoerbestand niet lukt dan wordt een foutmelding gegeven. Als het
openen wel gelukt is wordt regel voor regel en dan kolom voor kolom ingelezen.
Met behulp van fscanf wordt telkens een int getal
ingelezen uit het invoerbestand en in het "hokje" s[r][k]
geplaatst. Als bij het inlezen een fout optreedt dan wordt een foutmelding
gegeven en het inlezen afgebroken. De foutmeldingen zijn hier opgegeven als
3 losse C-strings achter elkaar maar de compiler
maakt hier 1 lange C-string van!
De functie drukaf heeft geen verder verklaring nodig.
De functie losop roept de functie probeer aan met
als tweede parameter het getal wat in het eerste vrije hokje moet worden
geprobeerd. De getallen 1 t/m 9 worden achtereenvolgens geprobeerd. Deze
functie geeft 1 terug zodra de functie probeer aangeeft dat
het invullen van de geprobeerde waarde gelukt is. Als alle getallen van 1
t/m 9 geprobeerd zijn er geen enkele geprobeerde waarde gelukt is dan geeft
de functie losop 0 terug om aangeven dat geen oplossing gevonden
is.
De functie probeer is de belangrijkste functie in het programma.
Deze functie is recursief, dat wil zeggen dat deze functie zichzelf aanroept.
De functie probeer zoekt eerst een leeg hokje waarvoor geldt:
s[r][k]==0.
In dit hokje wordt de waarde die geprobeerd moet worden ingevuld:
s[r][k]=p. Met de functie
controleer wordt nu bepaald of de sudoku nog geldig is. Als
dit niet het geval is
(controleer(s)==0)
dan wordt het hokje weer leeggemaakt met:
s[r][k]=0
en geeft de functie 0 terug om aan te geven dat de geprobeerde waarde niet
juist is. Als de functie controleer aangeeft dat de sudoku nog
geldig is mag nog niet geconcludeerd worden dat het invullen
van deze waarde gelukt is. Het invullen levert misschien niet meteen een
ongeldige sudoku op maar kan er voor zorgen dat je bij het verder oplossen
van de puzzel vastloopt. Je kunt ontdekken of de geprobeerde waarde echt
de juiste waarde is door te proberen in het volgende lege vakje een geldige
waarde te vinden. Dit doe je door de functie probeer aan te
roepen!
for (i=1; i<10; i++) {if (probeer(s, i)==1) {return 1;}}
In het volgende hokje worden dus achtereenvolgens de getallen 1 t/m 9 geprobeerd.
Zodra 1 van deze getallen correct is (de returnwaarde van
probeer is 1) weet je dat dit hokje ook correct is (en kun je
1 teruggeven). Als geen van de geprobeerde waarden voor het volgende hokje
een oplossing oplevert dan was de geprobeerde waarde dus niet juist. Dan
wordt het hokje weer leeggemaakt met:
s[r][k]=0
en geeft de functie 0 terug om aan te geven dat de geprobeerde waarde niet
juist is. Deze oplossingsmethode wordt
backtracking genoemd.
Tot slot de functie controlleer. Deze functie bepaalt of de
sudoku geldig is waarbij de lege hokjes buiten beschouwing worden gelaten.
Als eerste wordt per rij gekeken of de rij dubbele getallen bevat. Dit wordt
gedaan met behulp van de array
afvinklijst die bij het begin van
het controlleren van de rij met 9 nullen wordt gevuld. Op de eerste plaats
(met index 0) van de
afvinklijst worden de 1-en geteld.
Op de tweede plaats (met index 1) van de
afvinklijst worden de 2-en geteld.
Enz. Deze afvinklijst wordt als volgt gebruikt:
if (s[r][k]!=0 && ++afvinklijst[s[r][k]-1]>1) {return 0;}
s[r][k]!=0
test of het vakje niet leeg is. Als het vakje leeg is dan is de voorwaarde
van de if altijd false en wordt de rest van de voorwaarde niet
uitgerekend. s[r][k] is de waarde
die in het te controlleren hokje zit.
s[r][k]-1
is de index in afvinklijst waar deze waarde bijgehouden (geteld)
wordt. Het getal in de afvinklijst op positie
s[r][k]-1
wordt eerst met 1 verhoogd (door er ++ voor te zetten)
en daarna wordt gekeken of deze waarde in de afvanklijst
>1 is. Als dit zo is dan heb je hetzelfde getal al eerder
op deze rij gezien en is de sudoku niet geldig.
Als alle rijen geldig zijn wordt per kolom gekeken of de kolom dubbele getallen bevat. Dit gaat op dezelfde manier als bij het controlleren van de rijen.
Als alle kolommen geldig zijn wordt per blok gekeken of het blok dubbele
getallen bevat. Dit gaat op dezelfde manier als bij het controlleren van
de rijen. Het bepalen van de rij en kolomnummers van elk blok is iets
ingewikkelder. Maak zelf eens een tabel waarin je de waarden van
rb en kb berekent voor de verschillende waarden
van b (0 t/m 8).
Als ook alle blokken geldig zijn dan is de sudoku geldig en wordt de waarde 1 teruggegeven.
Kun je een programma schrijven dat de puzzel op een logische manier oplost? Dit programma kan dan ook gebruikt worden om een hint te geven. Zoiets als sudoku_stap_voor_stap.exe.
Kun je een programma schrijven dat een sudoku puzzel aanmaakt? Hoe kun je puzzles met verschillende moeilijkheidsgraden maken?