![]() |
Kleurenschema: - |
Begin 2006 kreeg ik bij het vak algoritmiek aan het LIACS de huiswerkopdracht om een programma in C++ te schrijven dat in staat is om versimpelde 4x4 sudoku puzzels op te lossen door middel van brute force. Dat resulteerde in onderstaande code, die ook te downloaden is.
// Algoritmiek Programmeeropdracht 1 // uiterlijk 2006-03-31 inleveren bij ******** // // Evert Mouw < ******** > // S 0332291 // // versie 2006-03-31 #include <stdio.h> // **** STENEN **** // 24 stenen geven de 24 mogelijkheden van een 2x2 veld (4! = 4*3*2*1 = 24) // bv. de velden // 12 12 13 13 14 14 ab // 34 43 24 42 23 32 cd struct steenstructuur { int veld[4]; // veld 1 t/m 4 (a, b, c, d) }; struct steenstructuur stenen[24]; // stenen nummers 1 t/m 24 (steen 0 heeft alle velden nul) int stenenmax = 24; // 24 (4!) mogelijke velden per quadrant // het speelveld bestaat uit vier quadranten // 01 // 23 int Q[4]; // met geldige waarden van 1 tot 24, dus bv. Q[2]=10 betekent: quadrant twee bevat steen 2. Q[2] = 0 betekent: quadrant 2 heeft nog geen steen // het speelveld kan ook in coordinaten weergegeven worden (posities) // 0123 x // 1 // 2 // 3 y // **** CLASSES **** class sudokubord { public: int veld[4][4]; int controleer(); void wissen(); void print(); void bestandsinvoer(); }; // in een linked list alle gevonden oplossingen opslaan class oplossing: public sudokubord { public: int *volgende; }; class speelveld: public sudokubord { public: int doorgaan(); speelveld(); // constructor declaratie void plaatssteen(int quadrant, int steennummer); private: int steen[4]; // steen[quadrant] }; // **** FUNCTIES BIJ CLASSES **** void sudokubord::wissen() { int x, y; for (x=0; x<4; x++) { for (y=0; y<4; y++) { veld[x][y] = 0; } } }; void sudokubord::print() { int x, y; for (y=0; y<4; y++) { for (x=0; x<4; x++) { printf("%d ", veld[x][y]); } printf("\n"); } }; void sudokubord::bestandsinvoer() { int x,y; // bestand openen char filename[] = "invoer.txt"; FILE *ifp; ifp = fopen(filename,"r"); // open voor lezen // invoer lezen (eerst y; elke regel is een y) for (y=0;y<4;y++) { for (x=0;x<4;x++) { fscanf(ifp, "%d", &veld[x][y]); } } // sluit bestand fclose(ifp); }; int sudokubord::controleer() { // KIJK OF HET HUIDIGE SPEELVELD EEN GELDIGE OPLOSSING BEVAT int geldig = 0; int h, v; // horizontaal, verticaal int i, j, k, l; // hulpvariabelen ter gemak van de notatie // check de rijen for (v=0; v<4; v++) { i = veld[0][v]; j = veld[1][v]; k = veld[2][v]; l = veld[3][v]; // we hebben een geldige rij als alle waarden ongelijk zijn if (i!=j && i!=k && i!=l && j!=k && j!=l && k!=l ) { geldig++; } } if (geldig==4) { // check de kolommen for (h=0; h<4; h++) { i = veld[h][0]; j = veld[h][1]; k = veld[h][2]; l = veld[h][3]; // we hebben een geldige kolom als alle waarden ongelijk zijn if (i!=j && i!=k && i!=l && j!=k && j!=l && k!=l ) { geldig++; } } } if (geldig==8) { geldig=1; } else { geldig=0; } return geldig; }; // constructor voor speelveld speelveld::speelveld() { int i; for (i=0;i<4;i++) { steen[i]=1; } }; int speelveld::doorgaan() { // naar de volgende situatie // output: // 0 = geen volgende opstelling mogelijk // 1 = volgende opstelling gemaakt int check=0; int i; for (i=3;i>-1;i--) { if ( check!=1 && steen[i] < stenenmax ) { steen[i]++; plaatssteen(i, steen[i]); check = 1; } if ( check!=1 && steen[i] == stenenmax && steen[i-1] < stenenmax && i>0 ) { steen[i]=1; plaatssteen(i,steen[i]); steen[i-1]++; plaatssteen(i-1,steen[i-1]); check = 1; } } if ( check==0 ) { return 0; } else { return 1; } }; void speelveld::plaatssteen(int quadrant, int steennummer){ // plaats een steen in een quadrant van het speelveld // dus een steenstructuur vertalen naar x en y coordinaten in het speelveld int dx, dy; // wat er by x en y opgeteld moet worden om in het goede quadrant uit te komen if (quadrant==0) { dx=0; dy=0; } if (quadrant==1) { dx=2; dy=0; } if (quadrant==2) { dx=0; dy=2; } if (quadrant==3) { dx=2; dy=2; } // vertaal de steenvelden naar het grid veld[0+dx][0+dy] = stenen[steennummer].veld[0]; veld[1+dx][0+dy] = stenen[steennummer].veld[1]; veld[0+dx][1+dy] = stenen[steennummer].veld[2]; veld[1+dx][1+dy] = stenen[steennummer].veld[3]; //printf("steen %d geplaatst in quadrant %d\n",steennummer, quadrant); }; // **** PROTOTYPES **** int stenen_maak(); void steen_print(int nummer); // **** MAIN **** int main() { int stellingen=0; int n; printf("SUDOKU 4x4 oplosser\n"); printf("Evert Mouw <post@evert.net>, S0332291\n"); printf("2006-03-31 Algoritmiek\n"); printf("\n"); stenen_maak(); n = 4 * 4 * 4 * 4 + 1; printf("Eerst 24 stenen (unieke situaties voor een quadrant) gemaakt,\n", n); printf("N: Daarvoor zijn 4^4+1 = %d quadrantcombinaties getest.\n", n); speelveld speelsudoku; speelsudoku.wissen(); //printf("Eerst alle quadranten vullen met steen 1\n"); //steen_print(1); speelsudoku.plaatssteen(0,1); speelsudoku.plaatssteen(1,1); speelsudoku.plaatssteen(2,1); speelsudoku.plaatssteen(3,1); //speelsudoku.print(); // eerst alle geldige stellingen vinden // (bleek 268 te zijn met leeg invoermasker) // en die in een array plaatsen sudokubord geldige[268]; n = 0; while ( speelsudoku.doorgaan()==1 ) { if ( speelsudoku.controleer()==1 ) { stellingen++; geldige[stellingen] = speelsudoku; } n++; } printf("N: In totaal %d stellingen geprobeerd.\n", n); printf("Aantal geldige stellingen: %d\n", stellingen); // alle geldige stellingen vergelijken met de invoer sudokubord invoer; int i; int x,y; int velden; int checkinvoer; int aantaloplossingen=0; printf("Bestandsinvoer:\n"); invoer.bestandsinvoer(); invoer.print(); for (i=1;i<=stellingen;i++){ checkinvoer = 0; for (x=0;x<4;x++){ for (y=0;y<4;y++){ if ( invoer.veld[x][y] == 0 || invoer.veld[x][y] == geldige[i].veld[x][y] ){ checkinvoer++; } } } if ( checkinvoer == 16){ aantaloplossingen++; //printf("Oplossing %d:\n", aantaloplossingen); //geldige[i].print(); if ( aantaloplossingen==1) { // alleen de eerste oplossing tonen printf("Eerste geldige oplossing:\n"); geldige[i].print(); } } } // de hoeveelheid oplossingen tonen, printf("Totaal aantal mogelijke oplossingen: %d\n", aantaloplossingen); }; int stenen_maak() { // MAAK DE STENEN // een steen bevat de vier cijfers {1, 2, 3, 4} in een unieke volgorde // de som is altijd 10 // snelheid van het algoritme is weinig belangrijk; de uitvoering is eenmalig // 4^4 stappen is 256 // de weinig elegante maar wel simpele methode is int s=0; //initiatie steennummer int i, j, k, l; for (i=1; i<5; i++) { for (j=1; j<5; j++) { for (k=1; k<5; k++) { for (l=1; l<5; l++) { // we hebben een geldige steen als alle waarden ongelijk zijn if (i!=j && i!=k && i!=l && j!=k && j!=l && k!=l ) { s++; stenen[s].veld[0] = i; stenen[s].veld[1] = j; stenen[s].veld[2] = k; stenen[s].veld[3] = l; } } } } } // en de nulsteen for (i=0;i<4;i++) { stenen[0].veld[i] = 0; } return s; }; void steen_print(int nummer) { // DRUK EEN STEEN AF printf Evert Mouw | blog | sitemap