Sudoku

// 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