* Created on Nov 2, 2006
 *
 * @by Marc Woerlein (Woerlein@informatik.uni-erlangen.de)
 */

/**
 * Diese Schnittstelle beschreibt die Funktionalitaet 
 * ein teilweise vorgefuelltes Sudoku-Feld zu loesen.
 * 
 * Ein gueltig ausgefuelltes Sudoku-Feld ist ein 9*9-Zahlenfeld,
 * in dem in jeder Zeile, jeder Spalte und jedem Quadranten 
 * die Ziffern von 1 bis 9 genau einmal vorkommt. 
 * 
 * Hier ein Beispiel-Feld (aufgeteilt in seine 9 Quadranten):
 * 
 *    057|420|000    357|429|681
 *    040|071|090    648|371|592
 *    200|080|000    291|586|437
 *    ---+---+---    ---+---+---
 *    030|704|200    139|754|268
 *    065|800|300 -> 465|812|379
 *    080|903|054    782|963|154
 *    ---+---+---    ---+---+---
 *    800|000|746    823|195|746
 *    914|000|005    914|637|825
 *    500|000|000    576|248|913
 * 
 * Hierbei stellt die Ziffer "0" eine noch zu besetzenden Zelle dar. 
 *
 * @author Marc Woerlein (Woerlein@informatik.uni-erlangen.de)
 *
 */
public interface SudokuLoeserInterface {
	
	/**
	 * ermittelt aus dem uebergebenen Sudoku-Feld, alle moeglichen Zahlen,
	 * die in der Zelle <code>feld[y][x]</code> erlaubt sind.  
	 * 
	 * @param feld ein quadratisches und teilweise vorgefuelltes Sudoku-Feld
	 * @param x X-Koordinate, der zu untersuchenden Zelle
	 * @param y Y-Koordinate, der zu untersuchenden Zelle
	 * @return ein <code>int[]</code>, mit allen erlaubten Zahlen
	 */
	public int[] moeglicheZahlen(int[][] feld, int x, int y);
	
	/**
	 * Sucht nach einer gueltigen Loesung fuer das uebergebene Sudoku-Feld.
	 * Wenn es (irgend-) eine Loesung gefunden hat, steht diese in dem uebergebenen Feld,
	 * wenn nicht, ist das Feld danach wieder so gefuellt wie vorher.
	 * 
	 * @param feld ein quadratisches und teilweise vorgefuelltes Sudoku-Feld
	 * @return <code>true</code>, wenn eine Loesung gefunden wurde
	 */
	public boolean loese(int[][] feld);
	
	/**
	 * Diese Methode versucht die Zelle <code>feld[y][x]</code> nacheinander
	 * mit einem der moeglichen Werte zu fuellen und schaut dann rekursiv,
	 * ob dies zu einer Loesung fuehrt.<p>
	 * Wenn keine Loesung gefunden wurde, muss die Zelle wieder geleert werden. 
	 * <p>
	 * Wenn die Zelle schon durch eine Zahl besetzt ist, 
	 * muss nur rekursiv nach einer Loesung gesucht werde.
	 *  
	 * @param feld ein quadratisches und teilweise vorgefuelltes Sudoku-Feld
	 * @param x X-Koordinate, der zu untersuchenden Zelle
	 * @param y Y-Koordinate, der zu untersuchenden Zelle
	 * @return <code>true</code>, wenn eine Loesung gefunden wurde 
	 */
	public boolean loese_rec(int[][] feld, int x, int y);
	
	/** ein loesbares Beispiel-Feld*/
	final public static int[][] Beispiel1={
		{0,5,7,4,2,0,0,0,0},
		{0,4,0,0,7,1,0,9,0},
		{2,0,0,0,8,0,0,0,0},
		{0,3,0,7,0,4,2,0,0},
		{0,6,5,8,0,0,3,0,0},
		{0,8,0,9,0,3,0,5,4},
		{8,0,0,0,0,0,7,4,6},
		{9,1,4,0,0,0,0,0,5},
		{5,0,0,0,0,0,0,0,0}
	};
	
	/** ein loesbares Beispiel-Feld*/
	final public static int[][] Beispiel2={
		{6,0,0,2,0,0,0,0,0},
		{0,0,2,0,0,8,4,0,0},
		{8,0,0,0,9,0,0,0,0},
		{0,8,0,4,0,0,3,2,0},
		{0,7,5,0,0,0,8,4,0},
		{0,3,1,0,0,7,0,9,0},
		{0,0,0,0,5,0,0,0,9},
		{0,0,3,9,0,0,7,0,0},
		{0,0,0,0,0,1,0,0,3}
	};
	
	/** ein loesbares Beispiel-Feld*/
	final public static int[][] Beispiel3={
		{0,5,0,8,0,1,0,7,0},
		{2,0,0,6,0,0,1,0,8},
		{0,0,0,0,2,0,6,0,0},
		{0,0,3,5,0,0,4,0,0},
		{0,0,0,0,3,0,0,0,0},
		{0,0,7,0,0,6,5,0,0},
		{0,0,8,0,1,0,0,0,0},
		{9,0,6,0,0,2,0,0,5},
		{0,2,0,9,0,8,0,3,0}
	};
	
	/** ein UNloesbares Beispiel-Feld*/
	final public static int[][] Beispiel4={
		{3,0,0,0,0,0,0,5,0},
		{0,5,0,0,0,0,6,4,0},
		{0,0,0,0,4,1,0,0,7},
		{9,0,0,0,2,8,7,0,0},
		{0,0,0,4,0,6,0,0,0},
		{0,0,8,9,7,0,0,0,6},
		{8,0,5,7,1,0,0,0,0},
		{0,3,7,0,0,0,0,2,0},
		{0,9,0,0,0,0,0,0,8}
	};
}