Benutzer:Rat/Sudoku

Java-Algorithmus zur Lösung von Sudokus

Laufzeit dieser Version: 2,0 s für 9999 Durchläufe

public class SudokuRek {
	static String beispiel[] = {
   // von http://www.sudokumeister.com/download/pod.html am 2.4.2006 kopiert
        "---5--7-----82-43-----7--6123--9--8--8-----1--6--5--7261--3-----23-19-----4--7---",
        "54739821-83-4-2---2--------------578153987462782--------------3---8-9-25-75623189",
	"124-68-97-86-37-2157329148-74-98-23-36-125-74-59-74-18-3784215981-65-74-49-71-862" };

	int[] feld;
	int sp[],ze[],sg[];
	int spalte[], zeile[], subgroup[];

	public SudokuRek(String raetsel) {
		feld = new int[81];
		spalte = new int[9];
		zeile = new int[9];
		subgroup = new int[9];
		sp = new int[81];ze=new int[81]; sg=new int[81];
		for (int n = 0; n < 81; n++) {
			// Vorausberechnung der Spalten, Zeilen und Subgruppen
			sp[n] = n%9;
			ze[n] = n/9;
			sg[n]= ((n % 9) / 3)*3 + (n / 27);
			// Vorbesetzung aus der Vorgabe
			if (raetsel.charAt(n) != '-') {
				byte ziffer = (byte) (raetsel.charAt(n) - '0');
				feld[n] = ziffer;
				spalte[sp[n]] |= (1 << ziffer);
				zeile[ze[n]] |= (1 << ziffer);
				subgroup[sg[n]] |= (1 << ziffer);
			}
		}
	}

	public String toString() {
		String s = "";
		for (int y = 0; y < 9; y++) {
			for (int x = 0; x < 9; x++) {
				s += " " + feld[y * 9 + x];
				;
			}
			s += "\n";
		}
		return s;
	}

	void trial(int n) {
		if (n == 81) {
			// System.out.println(this);
		} else if (feld[n] > 0) {  // da stand schon was
			trial(n + 1);
		} else {
			int spn=sp[n];
			int zen=ze[n];
			int sgn=sg[n];
			for (int t = 1; t <= 9; t++) {
				int bit = (1 << t);
				if ((spalte[spn] & bit) == 0 
						&& (zeile[zen] & bit) == 0
						&& (subgroup[sgn] & bit) == 0) {
					spalte[spn] |= bit;
					zeile[zen] |= bit;
					subgroup[sgn] |= bit;
					feld[n] = t;
					trial(n + 1);
					feld[n] = 0;
					spalte[spn] &= ~bit;
					zeile[zen] &= ~bit;
					subgroup[sgn] &= ~bit;
				}
			}
		}
	}

	public static void main(String[] args) {

		long start = System.nanoTime();
		for (int i = 0; i < 9999; i++) {
			SudokuRek org = new SudokuRek(beispiel[i % 3]);
			org.trial(0);
		}
		long duration = System.nanoTime() - start;
		System.out.println(duration / 1000 + " Mikrosekunden\n");
	}

}