Hi Forum !
Habe ein Sudoku geschrieben welches mittels backtracking eine Lösung finden soll.
Er gibt schon ein neues Sudokufeld aus aber halt
111
222
333...
Das Problem liegt denke ich hier.
Ich weis nicht so recht was ich in diese Methode reinschreiben soll.
Hab einiges versucht aber Ausgabe war leider immernoch falsch.
-1 steht für ein leeres Feld
Es wäre super wenn es sich wer anschaut : )
Flo
Das Ganze Programm
Habe ein Sudoku geschrieben welches mittels backtracking eine Lösung finden soll.
Er gibt schon ein neues Sudokufeld aus aber halt
111
222
333...
Das Problem liegt denke ich hier.
Ich weis nicht so recht was ich in diese Methode reinschreiben soll.
Hab einiges versucht aber Ausgabe war leider immernoch falsch.
-1 steht für ein leeres Feld
Es wäre super wenn es sich wer anschaut : )
Flo
Java:
public void zahlanders(int zeile, int spalte){
}Das Ganze Programm
Java:
mport AlgoTools.IO;
public class Sudoku {
public static final int LEERES_FELD=-1;
/* zeile[z][x] wird true wenn in Zeile z die Zahl x gesetzt ist
*/
private boolean [][]zeile= new boolean[9][10];
/* spalte[s][x] wird true wenn in Spate s die Zahl x gesetzt wird
*/
private boolean[][]spalte=new boolean[9][10];
/*
* box[][] ist true genau dann, wenn in der 3x3 Box die Zahl x gesetzt ist
* Eine Zelle (z,s) ist in Box mit Index 3*(z /3 ) + (s / 3 )
*/
private boolean[][]box=new boolean[9][10];
/* SPIELFELD
*/
private int[][] sudokufeld=new int[9][9];
/* Vorgegebene Zahlen als Teilloesung
*/
private int[][]teilloesung;
/*
*Sudoku mit Teilloesung erzeugen
*/public Sudoku(int[][]teilloesung)
{
this.teilloesung=teilloesung;
initialisieren();
}
/* Methode initialisieren,Teillösung wird generiert
*/
private void initialisieren(){
for(int boxnummer=0;boxnummer<9;boxnummer++)
{
for(int zahl =1;zahl<10;zahl++)
{
this.box[boxnummer][zahl] = false;
}
}
for(int zeile=0;zeile<9;zeile++)
{
for(int spalte=0;spalte<9;spalte++){
this.zeile[zeile][spalte+1]=false;
this.spalte[zeile][spalte+1]=false;
this.sudokufeld[zeile][spalte] = LEERES_FELD;
if(!isLeeresFeld(teilloesung[zeile][spalte])){
/*Fall hier ein bestimmter Wert hingehört
*wird dies in den entsprechenden Datenstrukturen eingetagen
*/
this.sudokufeld[zeile][spalte]=teilloesung[zeile][spalte];
this.zeile[zeile][teilloesung[zeile][spalte]]=true;
this.spalte[spalte][teilloesung[zeile][spalte]]=true;
this.box[getBoxNummer(zeile,spalte)][teilloesung[zeile][spalte]]=true;
}
}
}
}
/* Erzeugung isLeeresFeld
*/
private boolean isLeeresFeld(int zahl){
return zahl<=0 || zahl >9;
}
/* Spielfeld ausgeben
*/
public void print(){
for (int zeile=0;zeile <9; zeile++){
for (int spalte=0;spalte<9; spalte++){
System.out.print(sudokufeld[zeile][spalte]);
}
System.out.println();
}
}
/*Backtracking rekursiv suchen nach Lösung
*zaehler gibt die Anzahl belegter Zeilen an
*Wenn ene Lösung gefunden wurde return true
*/
public boolean sucheLoesung(int zaehler) {
int zeile = zaehler /9;
int spalte = zaehler %9;
for (int zahl =1; zahl < 10; zahl++){
if (istOkay(zeile,spalte,zahl)){
boolean z=this.zeile[zeile][zahl];
boolean s=this.spalte[spalte][zahl];
boolean b=this.box[getBoxNummer(zeile,spalte)][zahl];
this.sudokufeld[zeile][spalte] = zahl;
this.zeile[zeile][spalte] = true;
this.spalte[zeile][spalte] = true;
this.box[getBoxNummer(zeile,spalte)][zahl] = true;
zahlanders(zeile,spalte);
if (zaehler<80) {
if (sucheLoesung(zaehler +1)) {
return true;
} else {
this.sudokufeld[zeile][spalte]= teilloesung[zeile][spalte];
this.zeile[zeile][zahl] = z;
this.spalte[spalte][zahl] =s;
this.box[getBoxNummer(zeile,spalte)][zahl] =b;
zahlanders(zeile,spalte);
}
}
else
{
return true;
}
}
}
return false;
}
private int getBoxNummer(int zeile,int spalte){
return 3*(zeile/3) + (spalte /3 );
}
/**
* Sudoku zufällig erzeugen
*/
public void erzeugeSudoku(int anzahlVorgaben) {
do {
for (int zeile = 0; zeile < teilloesung.length; zeile++) {
for (int spalte = 0; spalte < teilloesung[zeile].length; spalte++) {
teilloesung[zeile][spalte] = LEERES_FELD;
}
}
initialisieren();
for (int i = 0; i < anzahlVorgaben; i++) {
int zeile = (int) (Math.random() * 9);
int spalte = (int) (Math.random() * 9);
int zahl = 1 + (int) (Math.random() * 9);
if (istOkay(zeile, spalte, zahl)) {
this.sudokufeld[zeile][spalte] = zahl;
this.zeile[zeile][zahl] = true;
this.spalte[spalte][zahl] = true;
this.box[getBoxNummer(zeile, spalte)][zahl] = true;
teilloesung[zeile][spalte] = zahl;
}
}
print();
System.out.println();
initialisieren();
}
while ( ! sucheLoesung(0));
print();
initialisieren();
}
/**
* Gibt true zurück, wenn die gegebene zahl noch nicht in
* der gegeben spalte, zeile oder zugehörigen 3 x 3 Box vorkommt
*/
private boolean istOkay(int zeile, int spalte, int zahl) {
return (teilloesung[zeile][spalte] == zahl || isLeeresFeld(teilloesung[zeile][spalte])
&& ! this.zeile[zeile][zahl]
&& ! this.spalte[spalte][zahl]
&& ! this.box[getBoxNummer(zeile, spalte)][zahl]);
}
public void zahlanders(int zeile, int spalte){
//hier//////////////////////////////////////////////////
////////////////////////////////////////////////////////
}
public int getZahl(int zeile, int spalte) {
return this.sudokufeld[zeile][spalte]; }
public int [] [] getTeilloesung() {
return teilloesung;
}
public void printBoxNummern() {
for (int zeile = 0; zeile < 9; zeile++) {
for (int spalte = 0; spalte < 9; spalte++) {
System.out.print(getBoxNummer(zeile, spalte));
}
System.out.println();
}
}
public static void main(String argv[]) {
Sudoku sudoku = new Sudoku(new int[][] {
{ 9, -1, 3, -1, 1, -1, 7, -1, -1},
{-1, 6, -1, -1, -1, 8, 5, -1, -1},
{-1, 5, -1, -1, -1, -1, -1, 9, 6},
{-1, -1, -1, -1, 3, -1, 6, -1, 4},
{-1, 4, -1, 9, -1, 1, 3, 7, 2},
{-1, -1, -1, 8, 7, 4, -1, 1, -1},
{-1, -1, 5, -1, -1, 3, 2, -1, 1},
{ 6, 8, 7, -1, -1, -1, -1, -1, -1},
{ 3, -1, -1, -1, -1, -1, -1, 5, -1}
});
sudoku.printBoxNummern();
if ( sudoku.sucheLoesung(0) ) {
System.out.println("Lösung gefunden");
sudoku.print();
} else {
System.out.println("Keine Lösung gefunden");
}
}
}
