Coder Forum

Java Quellcode

package ads;
/**
 * Autoren: Marco May & Torben Brodt
 */
import fhw.ADSTool;
 
public class SudokuPlay {
	public static void main(String[] args) {
		if(args.length < 2)
			System.out.println("Zur Backtracking Loesung 2 als Paramter uebergeben\nZum intelligenten Loesen eine 3");
 
		ADSTool.resetTime();
		if(args.length > 1)
			for(int i=1; i<args.length; i++) {
				Sudoku feld = new Sudoku(9, args[0], args[i]);
				System.out.println(feld);
				ADSTool.showRTime();
				System.out.println();
			}
	}	
}
 
class Sudoku {
	// Konstante fuer die Anzahl an Blöcken(9er/12er Sudoku) und die Breite einer Box (3 oder 4) 
	public final int n, box_n;
 
	// Zaehlt die Anzahl der erprobten Platzierungen
	public int tries=0;
 
	// Sudoku Feld (noch nicht vorbelegt, da 9^12 moeglich sind)
	public byte[][] feld;
 
	/**
	 * Konstruktor
	 * args[0] = dateiname
	 * args[1] = smart
	 */
	public Sudoku(int n, String what, String filename) {
 
		this.n = n;
		this.box_n = (int)Math.sqrt(n);
		this.feld = new byte[n][n];
 
		//Datei einlesen
		read(filename);
 
		//und loesen
		if(what.equals("2")) {
			solveBacktrack(0,0);
 
		} else if(what.equals("3")) {
			smartSolve();
 
		} else if(what.equals("1")) {
//			belassen fuer einfache Ausgabe
		}
 
	}
 
	/**
	 * Liest ein Raetsel ein
	 */
	public void read(String filename) {
		int i=0, j=0;
 
		try {
			int[] file = ADSTool.readIntArray(filename);
 
			for(int digit : file) {
				if(j == n) {
					j = 0;
					i++;
				}
				feld[i][j] = (byte)digit; 
				j++;
			}
		} catch(Exception e) {
			System.out.println("Bitte mit dem korrekten Dateinamen als Konsolenparameter starten");
			System.exit(0);
		}
	}
 
	/**
	 * Loest das Raetsel durch Backtracking
	 */
	public boolean solveBacktrack(int i, int j) {		
		if(j == n) { 	/* Zeilenende erreicht, 
						 * fange wieder links an,
						 * gehe eine Zeile nach unten
						 * oder breche ab, wenn du ganz fertig bist
						 */
			i++;
			if(i == n)
				return true;
		    j = 0;
		}		
 
		if(feld[i][j] > 0)  // Das Feld ist erfolgreich gesetzt
							// Funktionsaufruf mit naechster Spalte
		    return solveBacktrack(i, j+1);
 
		for(byte a=1; a<n+1; a++) {
		    if(check(i, j, a) == false) {  
				feld[i][j] = a;       
				if(solveBacktrack(i, j+1))
				    return true;
		    }
		}
 
		feld[i][j] = 0; // Der Versuch war wohl nichts
		return false;
	}
 
 
	/**
	 * Prueft ob dieses Feld gesetzt werden kann (ruft dabei 3 Subfunktionen auf)
	 * @return-> Gibt true zurueck, wenn der Wert bereits existiert
	 */
	public boolean check(int i, int j, int value) {
		tries++;
 
//		Fuer die Ausgabe mit SudokuSmart
//		System.out.println(""+i+"/"+j);
 
		if(checkHorizontal(j, value))
			return true;
 
		if(checkVertical(i, value))
			return true;		
 
		if(checkBox(i, j, value))
			return true;
 
		return false;
	}
 
	/**
	 * Prueft ob der Wert bereits in der (horizontalen) SPALTE existiert
	 * @return-> Gibt true zurueck, wenn der Wert bereits existiert
	 */
	public boolean checkHorizontal(int j, int value) {
		for(int a=0; a<n; a++)
		    if(feld[a][j] == value)
		    	return true;
 
		return false;
	}
 
	/**
	 * Prueft ob der Wert bereits in der (vertikalen) REIHE existiert
	 * @return-> Gibt true zurueck, wenn der Wert bereits existiert
	 */
	public boolean checkVertical(int i, int value) {
		for(int a=0; a<n; a++)
		    if(feld[i][a] == value)
		    	return true;
 
		return false;
	}
 
	/**
	 * Prueft ob der Wert bereits in der BOX existiert
	 * @return-> Gibt true zurueck, wenn der Wert bereits existiert
	 */
	public boolean checkBox(int i, int j, int value) {
		// oberes, linkes Eck der Box herausfinden (2|8 zu 0|6)
		int i_start = (int)(i/box_n) * box_n;
		int j_start = (int)(j/box_n) * box_n;
 
		for(int a=i_start; a<i_start+box_n; a++)
		    for(int b=j_start; b<j_start+box_n; b++)
		    	if(feld[a][b] == value)
		    		return true;
 
		return false;
	}
 
	/**
	 * SMART: Loest das Raetsel intelligenter
	 */
	public boolean smartSolve() {
		int[] best = smartChoice();
		int i=best[0], j=best[1];
 
		if(i == -1 && j == -1) //Das Sudoku funktioniert - es gibt keine leeren Felder mehr
			return true;
 
		for(byte a=1; a<n+1; a++) {
//			System.out.print("pruefe wert "+a+" in ");
			if(check(i, j, a) == false) {
				feld[i][j] = a;
				if(smartSolve())
					return true;
			}
		}
 
		feld[i][j] = 0; // Der Versuch war wohl nichts
		return false;
	}
 
 
	/**
	 * Sucht die Position der besten Möglichkeit 
	 *  gibt es eine Anzahl von Moeglichkeiten oefter, dann 
	 * 	dann wird die letzte Zahl als beste Moeglichkeit gewaehlt, 
	 * 	um in einem späteren Schleifendurchläufen Performance zu sparen
	 * @return: Gibt die Koordinaten zurueck
	 */
	public int[] smartChoice()
	{
		int minCount=n, minI=-1, minJ=-1;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(feld[i][j] == 0) {
						int c = smartCount(i,j);
						if(c <= minCount) {
							minCount = c;
							minI = i;
							minJ= j;
						}
				}
			}
		}
		int[] results = {minI, minJ};
		return results;
	}
 
 
	/**
	 * SMART: Zaehlt die leeren Felder (die Anzahl an moeglichen Loesungen) 
	 */
	public int smartCount(int i, int j) {
		boolean[] list = new boolean[10];
 
		for(int a=0; a<n; a++) {
			if(feld[i][a] > 0) 
				list[feld[i][a]] = true; // Durch "true" schliessen wir die Felder mit Wert aus
			if(feld[a][j] > 0)
				list[feld[a][j]] = true;
		}
 
		//Box
		int i_start = (int)(i/box_n) * box_n;
		int j_start = (int)(j/box_n) * box_n;
		for(int a=i_start; a<i_start+box_n; a++)
			if(a != i)
				for(int b=j_start; b<j_start+box_n; b++)
			    	if(feld[a][b] > 0 && b != j) 
			    		// >0 schliesst mehr Felder aus, dadurch an Pos1 der Abfrage
			    		list[feld[a][b]] = true;
 
		// Jetzt zaehlen wir die Felder, die wir gefunden haben
		byte max=0, possible=0;
		for(byte a=1; a<=n; a++) {
			if(list[a] == false)
				max++;
			else
				possible = a;
		}
 
		if(max == 1) {
			feld[i][j] = possible;
		}
 
		return max;
	}
 
 
	/**
	 * Ueberschreibt die Ausgabefunktion
	 * Wir verwenden hier nur einen Zaehler
	 * n*n Stringerweiterungungen sind langsamer als StringBuffer 
	 */
	public String toString() {
		StringBuffer returns = new StringBuffer();
 
		for(int i=0; i<n*n; i++) {
 
			if(i%n == 0 && i > 0) {
				returns.append("\n");
				if(i%(box_n*n) == 0)
					returns.append("-----------------------\n");
			}
 
			if (i%box_n == 0 && i%n != 0)
				returns.append(" |");
 
			returns.append(feld[i/n][i%n] == 0 ? "  " : " "+feld[i/n][i%n]);
		}
		returns.append("\nEs wurden "+tries+" Platzierungen ausprobiert in ");
		return returns.toString();
	}
}