public class SudokuLoeser implements SudokuLoeserInterface {
	static SudokuLoeser Sudoku = new SudokuLoeser();
	
	
	int[][] block = new int[9][9]; //[Blocknummer][Zahlen im Block]
	int[][][] nichtMoeglich;
	

	public static void main(String[] args) {
		
		System.out.println("Beispiel 1: ");
		Sudoku.loese(Beispiel1);
		System.out.println("");
		System.out.println("Beispiel 2: ");
		Sudoku.loese(Beispiel2);
		System.out.println("");
		System.out.println("Beispiel 3: ");
		Sudoku.loese(Beispiel3);
		System.out.println("");
		System.out.println("Beispiel 4: ");
		Sudoku.loese(Beispiel4);
	}
	
	
	
	public boolean arrayBeinhaltet(int[] array, int zahl) {
		boolean beinhaltet = false;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == zahl) {
				beinhaltet = true;
				break;
			}
		}
		return beinhaltet;
	}
	
	public boolean loese(int[][] feld) {
		int ausgleichX;
		int ausgleichY;
		int[] moeglicheZahlen;
		nichtMoeglich = new int[9][9][9];
		boolean aenderung;
		int durchgaenge = 0;
		int gleich;
		boolean gleichX, gleichY;
		do {
			aenderung = false;
			for (int blockNummer = 0; blockNummer <= 8; blockNummer++) { //Durchgang Block für Block
				if (blockNummer >= 6) {
					ausgleichX = ((blockNummer - 6) * 3);
					ausgleichY = 6;
				} else if (blockNummer >= 3) {
					ausgleichX = ((blockNummer - 3) * 3);
					ausgleichY = 3;
				} else {
					ausgleichX = (blockNummer * 3);			
					ausgleichY = 0;
				}
				for (int y = 0; y <= 2; y++) { //er schnappt sich jede Zahl aus dem Block...
					naechsteZahl: 
					for (int x = 0; x <= 2; x++) {
						moeglicheZahlen = moeglicheZahlen(feld, x + ausgleichX, y + ausgleichY);
						if (moeglicheZahlen.length == 1) {
							feld[y + ausgleichY][x + ausgleichX] = moeglicheZahlen[0];
							aenderung = true;
							continue naechsteZahl;
						}
						naechsteMoeglichkeit:
						for (int moeglichkeit:moeglicheZahlen) { //und geht Moeglichkeit fuer Moeglichkeit durch...
							gleich = 0;
							gleichX = false;
							gleichY = false;
							for (int checkY = 0; checkY <= 2; checkY++) {
								for (int checkX = 0; checkX <= 2; checkX++) {
									if ((checkY != y)||(checkX != x)) {
										for (int moeglichkeitCheck:moeglicheZahlen(feld, checkX + ausgleichX, checkY + ausgleichY)) {
											if (moeglichkeitCheck == moeglichkeit) { //und prüft ob diese Moeglichkeit nochmal vorkommt (im Block)
												if (gleich == 0) { //Falls erster Durchlauf
													gleichX = (checkX == x);
													gleichY = (checkY == y);
												}
												gleich++;
												if (gleich > 2) { 
													continue naechsteMoeglichkeit;
												} else if ((gleichX != (checkX == x)) || (gleichX == gleichY)) {
													continue naechsteMoeglichkeit;
												}																						
												break;
											}
										}
									}
								}
							} 
							if (gleich == 0) {
							feld[y + ausgleichY][x + ausgleichX] = moeglichkeit;
							aenderung = true;
							continue naechsteZahl;
							} else { // 0 < gleich <= 2; alle zu 'moeglichkeit' gleiche Moeglichkeiten in diesem Block liegen...
								if (gleichX == true) { //untereinander
									for (int nichtMoeglichY = 0; nichtMoeglichY <= 8; nichtMoeglichY++) {
										if ((ermittleBlock(x + ausgleichX, nichtMoeglichY) != blockNummer) && (!arrayBeinhaltet(nichtMoeglich[nichtMoeglichY][x + ausgleichX], moeglichkeit))) {
											for (int i = 0; i <= 8; i++) {
												if (nichtMoeglich[nichtMoeglichY][x + ausgleichX][i] == 0) {
													nichtMoeglich[nichtMoeglichY][x + ausgleichX][i] = moeglichkeit;
													aenderung = true; break;
												}
											}
											
										}
									}
									System.out.println("Untereinander: "+(x + ausgleichX)+" "+(y + ausgleichY)+" Moegl. "+moeglichkeit);
								} else { //oder nebeneinander
									for (int nichtMoeglichX = 0; nichtMoeglichX <= 8; nichtMoeglichX++) {
										if ((ermittleBlock(nichtMoeglichX, y + ausgleichY) != blockNummer) && (!arrayBeinhaltet(nichtMoeglich[y + ausgleichY][nichtMoeglichX], moeglichkeit))) {
											for (int i = 0; i <= 8; i++) {
												if (nichtMoeglich[y + ausgleichY][nichtMoeglichX][i] == 0) {
													nichtMoeglich[y + ausgleichY][nichtMoeglichX][i] = moeglichkeit;
													aenderung = true; break;
												}
											}
											
										}
									}
									System.out.println("Nebeneinander "+(x + ausgleichX)+" "+(y + ausgleichY)+" Moegl. "+moeglichkeit);
								}							
							}
						}					
					}
				}
			}
			durchgaenge++;
		} while (aenderung == true);
		
		
		
		for (int y = 0; y <= 8; y++) {
			for (int x = 0; x <= 8; x++) {
				System.out.print(feld[y][x]);
			}
			System.out.println();
		}
		System.out.println("Durchgaenge: "+durchgaenge);
		return false;
	}

	
	public boolean loese_rec(int[][] feld, int x, int y) {

		return false;
	}
	
	public int[] moeglicheZahlen(int[][] feld, int x, int y) {
		int[] moegliche = fehlendeZahlen(feld, x, y);
		int[] moeglicheNeu = new int[0];
		int arrayZaehler = 0;
		boolean vorhanden;
		if (feld[y][x] != 0) {
			return moeglicheNeu;
		}		
		naechsteNummer:
		for (int nummer:moegliche) {
			vorhanden = false;
			for (int checkY = 0; checkY <=8 ; checkY++) {
				if ((feld[checkY][x] == nummer)&&(checkY != y)) {
					vorhanden = true; break;
				}
			}
			if (vorhanden == false) {
				for (int checkX = 0; checkX <= 8; checkX++) {
					if ((feld[y][checkX] == nummer)&&(checkX != x)) {
						vorhanden = true; break;
					}
				}
			}
			if (vorhanden == false) {
				if (arrayBeinhaltet(nichtMoeglich[y][x], nummer)) {
					vorhanden = true;
				}
			}
			if (vorhanden == true) {
				arrayZaehler = 0;
				moeglicheNeu = new int[moegliche.length - 1];
				for (int i = 0; i < moeglicheNeu.length; i++) {
					if (moegliche[arrayZaehler] == nummer) {
						arrayZaehler++;
					}
					moeglicheNeu[i] = moegliche[arrayZaehler];
					arrayZaehler++;
				}
				moegliche = moeglicheNeu;
				continue naechsteNummer;
			}
		}	
		return moegliche;
	}

	public void aktualisiereBlock(int[][] feld, int blockNummer) {
		int arrayZaehler = 0;
		int ausgleichY = 0;
		int ausgleichX = 0;
		switch (blockNummer) {
		case 0:
			break;
		case 1:
			ausgleichX = 3; break;
		case 2:
			ausgleichX = 6; break;
		case 3:
			ausgleichY = 3; break;
		case 4:
			ausgleichY = 3;
			ausgleichX = 3; break;
		case 5:
			ausgleichY = 3;
			ausgleichX = 6; break;
		case 6:
			ausgleichY = 6; break;
		case 7:
			ausgleichY = 6;
			ausgleichX = 3; break;
		case 8:
			ausgleichY = 6;
			ausgleichX = 6; break;
		case 9:	System.out.println("Fehler bei Blockzuweisung"); System.exit(0);
		}
		for (int y = 0; y <= 2; y++) {
			for (int x = 0; x <= 2; x++) {
				block[blockNummer][arrayZaehler] = feld[y + ausgleichY][x + ausgleichX];
				arrayZaehler++;
			}
		}		
	}
	
	public int ermittleBlock(int x, int y) {
		int[] xArray = new int[3];
		int[] yArray = new int[3];
		int blockNummer = 9;
		if (x >= 6) { //speichert die durch x moeglichen y-Bloecke
			yArray[0] = 2;
			yArray[1] = 5;
			yArray[2] = 8;
		} else if (x >= 3) {
			yArray[0] = 1;
			yArray[1] = 4;
			yArray[2] = 7;
		} else {
			yArray[0] = 0;
			yArray[1] = 3;
			yArray[2] = 6;			
		}
		if (y >= 6) { //und das gleiche für y
			xArray[0] = 6;
			xArray[1] = 7;
			xArray[2] = 8;
		} else if (y >= 3) {
			xArray[0] = 3;
			xArray[1] = 4;
			xArray[2] = 5;
		} else {
			xArray[0] = 0;
			xArray[1] = 1;
			xArray[2] = 2;			
		}
		for (int yBlock=0; yBlock <= 2; yBlock++) { //Der gemeinsame Teil aus beiden Arrays wird gesucht
			for (int xBlock=0; xBlock <= 2; xBlock++) {
				if (yArray[yBlock]==xArray[xBlock]) { 
					blockNummer = yArray[yBlock]; 
				}
			}
		}
		return blockNummer;
	}
	
	public int[] fehlendeZahlen(int[][] feld, int x, int y) {
		int[] fehlend = new int[] {1,2,3,4,5,6,7,8,9};
		int[] fehlendNeu;
		int arrayZaehler = 0;
		int blockNummer = ermittleBlock(x, y);
		aktualisiereBlock(feld, blockNummer);
		for (int blockStelle:block[blockNummer]) {
			for (int nummer:fehlend) {
				if (blockStelle == nummer) { //falls es die Zahl 'nummer' im Block 'blockNummer' gibt,
					fehlendNeu = new int[fehlend.length - 1];
					arrayZaehler = 0;
					for (int i = 0; i < fehlendNeu.length; i++) {
						if (fehlend[arrayZaehler] == nummer) {
							arrayZaehler++; //wird sie beim schreiben des fehlend-Arrays ausgelassen
						}
						fehlendNeu[i] = fehlend[arrayZaehler];
						arrayZaehler++;
					}
					fehlend = fehlendNeu;
				}
			}
		}
		return fehlend;
	}
}