Hi Leute;
für meine Facharbeit habe ich ein Programm programmiert, dass Sudokus mit Hilfe von Backtracking löst. Das ganze hab ich jetzt dank guter Literatur endlich fertig, obwohl meine Kenntnisse eher sehr gering sind.
Um festzustellen, ob es möglich ist, eine Zahl an eine bestimmt Stelle einzusetzen, habe ich zuerst alle Zahlen einer Zeile/einer Spalte/ eines Blocks in BitSets gemerkt. Mit der Methode get() konnte ich dann kucken, ob die Zahl schon in der Zeile/Spalte/Block vorkommt. Hat alles super funktioniert.
Nun möchte ich das Programm noch verbessern, wie es in dem Buch von meinem Lehrer vorgeschlagen wird: "Ersetzen Sie die "do-while" - Schleife in füllen() durch eine Schleife, die für jedes freie Feld die Vereinigung der Mengen aus zeile[],spalte[],block[] bestimmt und die Position ausgibt, an der die Vereinigungsmenge die größte Anzahl von Elementen hat."
Vom Sinn her hab ich das verstanden, wenn in der Vereingungsmenge schon 8 Elemente sind, ist das Feld eindeutig, es gibt weniger Fehlversuche... Nur komm ich mit BitSet als Klasse offensichtlich nicht klar! Um die Vereinungsmenge zu bilden, habe ich or() genutzt und um die Anzahl der summe zu bekommen, size(). Schade, dass da dann immer nur 64 rauskommt , und nicht eine Zahl zwischen 0-9 :/.
Ich hab wirklich schon lange gewerkelt und gegoogelt, also wäre es nett, wenn ihr euch das mal anschaut. Euer Forum gefällt mir nämlich super :toll: Es darf auch wirklich gerne an meinem schlechten Stil und meinen groben Schnitzern genörgelt werden
für meine Facharbeit habe ich ein Programm programmiert, dass Sudokus mit Hilfe von Backtracking löst. Das ganze hab ich jetzt dank guter Literatur endlich fertig, obwohl meine Kenntnisse eher sehr gering sind.
Um festzustellen, ob es möglich ist, eine Zahl an eine bestimmt Stelle einzusetzen, habe ich zuerst alle Zahlen einer Zeile/einer Spalte/ eines Blocks in BitSets gemerkt. Mit der Methode get() konnte ich dann kucken, ob die Zahl schon in der Zeile/Spalte/Block vorkommt. Hat alles super funktioniert.
Nun möchte ich das Programm noch verbessern, wie es in dem Buch von meinem Lehrer vorgeschlagen wird: "Ersetzen Sie die "do-while" - Schleife in füllen() durch eine Schleife, die für jedes freie Feld die Vereinigung der Mengen aus zeile[],spalte[],block[] bestimmt und die Position ausgibt, an der die Vereinigungsmenge die größte Anzahl von Elementen hat."
Vom Sinn her hab ich das verstanden, wenn in der Vereingungsmenge schon 8 Elemente sind, ist das Feld eindeutig, es gibt weniger Fehlversuche... Nur komm ich mit BitSet als Klasse offensichtlich nicht klar! Um die Vereinungsmenge zu bilden, habe ich or() genutzt und um die Anzahl der summe zu bekommen, size(). Schade, dass da dann immer nur 64 rauskommt , und nicht eine Zahl zwischen 0-9 :/.
Ich hab wirklich schon lange gewerkelt und gegoogelt, also wäre es nett, wenn ihr euch das mal anschaut. Euer Forum gefällt mir nämlich super :toll: Es darf auch wirklich gerne an meinem schlechten Stil und meinen groben Schnitzern genörgelt werden
Java:
import java.io.*;
import java.util.*;
public class sudoku{
private static int[][] feld;
private static final int N = 3; // Konstante
private static final int DIM = N*N; // Konstante für die größe des Sudokus
private static BitSet zeile[];
private static BitSet spalte[];
private static BitSet[][] block;
private static int unmöglich=0;
private static int[][] möglichkeiten;
//Atribute der Klasse
sudoku(int[][] werte){ //Konstruktor
feld = werte;
this.zeile = new BitSet[DIM];
this.spalte = new BitSet[DIM];
for(int z = 0; z < DIM; z++){
this.zeile[z]= new BitSet();
this.spalte[z] = new BitSet();
}
this.block= new BitSet[N][N];
for(int z= 0 ;z<N;z++) {
for (int s=0;s<N; s++) {
block[z][s] = new BitSet();
} // end of for
} // end of for
for (int z= 0;z<DIM ;z++) {
for (int s=0;s<DIM ;s++) {
if (feld[z][s]!=0) {
zeile[z].set(feld[z][s]);
spalte[s].set(feld[z][s]);
block[z/N][s/N].set(feld[z][s]);
} // end of if
} // end of for
} // end of for
} //Konstruktor Ende
public static void main(String args[]){
int[][] werte = {
{0,0,0,9,0,0,7,2,8}, //z=0
{2,7,8,0,0,3,0,1,0}, //z=1
{0,9,0,0,0,0,6,4,0}, //..
{0,5,0,0,6,0,2,0,0},
{0,0,6,0,0,0,3,0,0},
{0,1,0,0,5,0,0,0,0},
{1,0,0,7,0,6,0,3,4},
{0,0,0,5,0,4,0,0,0},
{7,0,9,1,0,0,8,0,5}
};//s=0,s=1;..
new sudoku(werte);
ausgabe();
füllen(); // füllen(0, -1) für die erste Version
ausgabe();
}
public static void füllen(){ //int s, int z für die Erste Version
/*do {
s++;
if (s==DIM) { //Erste Version ;)
s=0;
z++;
if (z==DIM) { //Abbruchbedingung
ausgabe();
return; //Das Ende: alle Felder voll
} // end of if
} // end of if
} while (feld[z][s] !=0); //nächstes leeres Feld finden
*/
BitSet summe= new BitSet();
int z=0;
int s=0;
int Anzahl=0;
for (int a=0;a<DIM;a++) {
for (int t=0;t<DIM;t++) {
if (feld[a][t]==0) {
summe= zeile[a];
summe.or(spalte[t]);
summe.or(block[a/N][t/N]);
Anzahl=summe.size();
} // end of if
} // end of for
} // end of for
if (Anzahl==9) {
ausgabe();
return;
} // end of if
for (int wert=1;wert<=DIM; wert++) {
if (möglich(z,s,wert)) { //möglichen Wert finden
einsetzen(z,s,wert);
füllen(); //Rekursion:die nächsten Felder füllen
löschen(z,s); //falschen Wert löschen
} // end of if
} // end of for
unmöglich++;
}
public static void einsetzen(int z, int s, int wert){
feld[z][s]=wert;
zeile[z].set(wert);
spalte[s].set(wert);
block[z/N][s/N].set(wert);
}
public static void löschen(int z, int s){
zeile[z].clear(feld[z][s]);
spalte[s].clear(feld[z][s]);
block[z/N][s/N].clear(feld[z][s]);
feld[z][s]=0;
}
static boolean möglich(int z, int s, int wert){ //Sudokubedingung
if (!zeile[z].get(wert)
&& !spalte[s].get(wert)
&& !block[z/N][s/N].get(wert))
{
return true;
} // end of if
else{
return false;
}
}
public static void ausgabe(){
for (int z=0;z<DIM;z++) {
for (int s=0;s<DIM ;s++ ) {
System.out.print(feld[z][s]+" ");
} // end of for
System.out.print("\n");
} // end of for
System.out.print(unmöglich);
System.out.print("Fehlversuche\n");
}
}
