lundi 20 avril 2015
Sudoku Backtracking
Posted on 03:49 by verona
Hallo Leute,
meine Hausaufgabe ist es einen Backtracking Algorithmus zum lösen von Sudokus zu schreiben.
Leider sieht mein Output aus irgendeinem Grund so aus :bahnhof::
1 2 3 4 5 6 7 8 9
4 5 6 1 2 3 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
Hier der Code
(hier noch die sudoku klasse und die main)
Wäre dankbar für jede Hilfe
Liebe Grüße
thamaz
meine Hausaufgabe ist es einen Backtracking Algorithmus zum lösen von Sudokus zu schreiben.
Leider sieht mein Output aus irgendeinem Grund so aus :bahnhof::
1 2 3 4 5 6 7 8 9
4 5 6 1 2 3 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
Hier der Code
Java Code:
-
-
package SudokuProg2;
-
-
-
-
-
-
-
public class BacktrackingSudokuSolver implements ISudokuSolver{
-
-
-
-
private Sudoku sudoku;
-
private int row=0,col=0;
-
-
-
-
@Override
-
public boolean solveSudoku(ISudoku sudoku){
-
this.sudoku=(Sudoku) sudoku;
-
return backtracking();
-
-
-
-
}
-
-
-
private boolean backtracking(){
-
-
-
-
// Funktion FindeLoesung (Stufe, Vektor)
-
// 1. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
-
// a) wähle einen neuen Teil-Lösungsschritt;
-
// b) falls Wahl gültig ist:
-
// I) erweitere Vektor um Wahl;
-
// II) falls Vektor vollständig ist, return true; // Lösung gefunden!
-
// sonst:
-
// falls (FindeLoesung(Stufe+1, Vektor)) return true; // Lösung!
-
// sonst mache Wahl rückgängig; // Sackgasse (Backtracking)!
-
// 2. Da es keinen neuen Teil-Lösungsschritt gibt: return false // Keine Lösung!
-
-
//TODO ---------------
-
-
if (!UnusedField())//Beendet Rekursion wenn alle Felder != 0 sind
-
return true;
-
-
for (int num = 1; num <= 9; num++){// probiert Zahlen 1-9 aus
-
if (isValid(num,row, col)){
-
sudoku.setNumber(row,col,num);
-
if (backtracking())
-
return true;
-
sudoku.setNumber(row,col,0);
-
}
-
}
-
return false;
-
}
-
-
-
-
-
//Durchläuft Spielfeld und setzt Variablen row,col auf den Index des nächsten freien Feldes, returnt false sonst.
-
boolean UnusedField(){
-
for (row = 0; row < sudoku.getSize(); row++)
-
for (col = 0; col < sudoku.getSize(); col++)
-
if (sudoku.getNumber(row, col) == 0)
-
return true;
-
return false;
-
}
-
-
//Checkt ob Zahl in [row][col] einsetzbar ist, returnt false sonst.
-
private boolean isValid(int number,int row,int col){
-
return rowCheck(number,row)&&
-
columnCheck(number,col)&&
-
quadCheck(number,row,col);
-
}
-
-
-
private boolean columnCheck(int number,int col){
-
for(int row=0;row<sudoku.getSize()-1;row++){
-
if(sudoku.getNumber(row,col)==number){
-
return false;
-
}
-
}
-
return true;
-
}
-
-
-
private boolean rowCheck(int number,int row){
-
for(int col=0;col<sudoku.getSize()-1;col++){
-
if(sudoku.getNumber(row,col)==number){
-
return false;
-
}
-
}
-
return true;
-
-
}
-
-
private boolean quadCheck(int number,int row,int col){
-
-
-
row = 3*(row/3);
-
col = 3*(col/3);
-
for( int r = 0; r < 3; r++ ){
-
for( int c = 0; c < 3; c++ ){
-
if( sudoku.getNumber(row+r,col+c) == number )
-
return false ;
-
}
-
}
-
return true ;
-
-
-
}
-
-
-
-
}
(hier noch die sudoku klasse und die main)
Wäre dankbar für jede Hilfe
Liebe Grüße
thamaz
Sudoku Backtracking
Categories: Sudoku Backtracking
Inscription à :
Publier les commentaires (Atom)
0 commentaires:
Enregistrer un commentaire