#include <stdio.h>
#define spalten 40  //Spaltenanzahl fuer die Ausgabe am Bildschirm (horizontale Linien)

/*******************************************************************
Loest das Sudoku
Note: Muss mit -1 angestossen werden, damit die Funktion sudoku_gib_leer()
Feld[0][0] nicht überspringt.

Paramter:
array: Array mit Sudoku-Feld durchnummeriert von 0 bis 80
feldid: Letztes freies Feld
*******************************************************************/
int sudoku_loesen(int *array,int feldid){
    int r = 0,j,i,k;
    j = sudoku_gib_leer(array,feldid);
    if(j >=81){
         r = 1;								// Wenn wir hier sind, dann sind wir fertig mit 
    }else{								    // loesen, und setzen Rueckgabe auf 1.
          for(i=1;i<=9;i++){
                      if(sudoku_feld_ok(j, i, array)){			            // Falls in das naechste Freie Feld (array+j)
                                           *(array+j) = i;		            // i gesetzt werden darf, setzte i in (array+j)
                                           if(sudoku_loesen(array,j)){	    // rufe nochmal sudoku_loesen auf und pruefe fuer
                                                r = 1;			            // naechstes freies Feld.
                                                break;
                                           }else{
                                                 *(array+j) = 0;	// Wenn Ergebnis aus sudoku_loesen() nicht ok war, 
                                           }				        // setze das vorherige Feld wieder auf null
                      }							                    // und mach weiter mit i.
          }
    }
    return r;
}
    
    
    
/*******************************************************************
Gibt das nächste freie Feld aus.

Paramter:
array: Array mit Sudoku-Feld durchnummeriert von 0 bis 80
feldid: Letztes freies Feld
*******************************************************************/
int sudoku_gib_leer(int *array, int feldid){
    int i;
    for(i = feldid+1;i<82;i++){			// Gibt max.81 zurueck, dann ist man am Ende vom Feld. 
    	if(*(array+i) == 0){			// 81 wird in sudoku_loesen() abgefangen
            return i;          
    	}	
    }
}
    


    
/*******************************************************************
Ueberprueft ob ein gegebener Wert in ein Feld geschrieben werden darf.

Paramter:
feldid ist die id des Feldes, durchnummeriert von 0 bis 80 (9x9 -Sudoku)
feldwert ist der Wert auf den feldid Ueberprueft werden soll.
array ist das Array in dem das Sudoku gespeichert ist.

Rueckgabe:
0 falls der uebergebene Wert feldwert nicht in das Feld mit feldid geschrieben werden darf.
1 falls der uebergebene Wert feldwert in das Feld mit feldid geschrieben werden darf.
*******************************************************************/
int sudoku_feld_ok(int feldid, int feldwert, int *array){
    int z,s,f,r = 1,i,j;	
        /*
          z sind in folgendem die Zeilen, s die Spalten, i und j Zaehlvariablen, r die Rueckgabe.
        */
                  
    s = feldid % 9;	                        	// Berechnung der Spalte.
    for(i=0;i<9;i++){
     if(*(array+s ) == feldwert){			// Ueberpruefung der Spalte auf identische Werte
    	r=0;
        break;
     }
    s+=9;
    }
    
    z = (feldid/9)*9;
    for(i=0;i<9;i++){
     if(*(array+z ) == feldwert){			// Ueberpruefung der Zeile auf identische Werte
    	r=0;	
    	break;
     }
     z+=1;
    }
    
    z = (feldid / 9 ) / 3;
    s = (feldid % 9) / 3;
    f = z * 27 + s * 3;                    // Berechnung des linken oberen Feldes in jedem 3x3-Quadranten
    
    for(i=0;i<3;i++){
                     for(j=0;j<3;j++){
                    	 if(*(array+f+j+i*9) == feldwert){          //Ueberpruefung des entsprechenden 3x3-Quadranten
    	                              r=0;	
                                	  break;
                         }
                     if(r==0)
                             break;                                // Abbruch, damits bissle schneller geht.
                     }
    }
    return r;
}
   
    
    
    
/*******************************************************************
Gibt ein Sudoku-Feld(9x9) strukturiert aus.

Parameter: 
array
*******************************************************************/
void sudoku_ausgabe(int *array){
        int i, j,k=0;
        /*
        i j und k sind Zaehlvariablen.
        */
    	   for(j=0;j<spalten;j++)		// Generiert die obere Border
    		printf("=");
    	   printf("\n");	
                   for(i = 0;i < 81;i++){
    		 k++;
    		 if(i%9 == 0)
    		 	printf("|");                     
    		 printf("%3d",*(array+i));
    		 if(k==3){			// Zaehlt die Spalten mit, bei der 3. wird ein | eingefuegt
    		    printf(" |");		// sonst ein Leerzeichen
    		    k=0;
    		  }else	
    		    printf(" ");
    		 if(i == 26 || i == 53){  	// Fuegt eine Zwischenlinie nach 3 Zeilen ein
    		  printf("\n");
    		   for(j=0;j<spalten;j++)
    	         	printf("=");	
    		  }		
    		 if((i%9 == 8 && i >0))		// Fuegt am Zeilenende eine neue Zeile ein
    		 	printf("\n");
                    }                   
    	   for(j=0;j<spalten;j++)		// Generiert die untere Border
    		printf("=");
        printf("\n");    
}
    
    
    
    
/*******************************************************************
Fuellt ein 9x9-Sudokufeld mit Nullen

Parameter:
Array - Array das gefüllt werden soll
*******************************************************************/
void sudoku_fuellen(int *array){
                   int i,j;
                   for(i = 0;i < 81;i++){
                            *(array+i) = 0;
    		}              
}
    
    
    
    
/*******************************************************************
Setzt in vorgegebenes Array in Zeile, Spalte, Wert.

Parameter:
Array
z - Zeile
s - Spalte
w - Wert
*******************************************************************/
void set_num(int *array, int z, int s, int w){
         int feldid = (z-1)*9+(s-1);
         *(array+feldid) = w;
}