Java-Algorithmus zur Lösung von Sudokus
BearbeitenLaufzeit 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");
}
}