Sudoku Backtracking

T

thamaz

Mitglied
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

Java: 
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
 
T

thamaz

Mitglied
Hier die Lösung:

Bitte als GELÖST taggen

Java: 
package SudokuProg2;





 
public class BacktrackingSudokuSolver implements ISudokuSolver{
   
    private class Index{
        
        private int row;
        private int col;
        
        private Index(){
            row=0;
            col=0;
        }
        private void setNumbers(int r,int c){
            row=r;
            col=c;
        }
    }


    
    
        private Sudoku sudoku;


       
       
       
       
        @Override
        public boolean solveSudoku(ISudoku sudoku){
                this.sudoku=(Sudoku) sudoku;
                 return backtracking(new Index());
 
             
        }
                 
       
       private boolean backtracking(Index index){
 
               Index isFree=unusedField(index);
//              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!      
           
       
           if(isFree.row>=sudoku.getSize())
               return true;


           
           
            for (int num = 1; num <= 9; num++){// probiert Zahlen 1-9 aus
                if (isValid(isFree,num)){
                    sudoku.setNumber(isFree.row,isFree.col,num);
                    if(backtracking(isFree)){
                        return true;
                    }
                    else sudoku.setNumber(isFree.row,isFree.col,0);
                }
            }
            return false;
        }
 
       
       
       
       //Sucht nächste freie Zelle ausgehend von übergebenen Koordinaten und gibt diese als Index Objekt zurück.
       Index unusedField(Index index){
           Index isFree=new Index();
            for (int r = index.row; r < sudoku.getSize(); r++){
                for (int c =(r>index.row)?0:index.col; c < sudoku.getSize(); c++){
                    if (sudoku.getNumber(r, c) == 0){
                        isFree.setNumbers(r,c);
                        return isFree;
                    }
                }
            }
            isFree.setNumbers(sudoku.getSize(),sudoku.getSize());
            return isFree;


        }
       
       //Checkt ob Zahl in [row][col] einsetzbar ist, returnt false sonst.
       private boolean isValid(Index index,int number){
            return rowCheck(number,index.row)&&
                    columnCheck(number,index.col)&&
                    quadCheck(number,index.row,index.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 ;
                 
           
        }
       
       
       
       
 
 
 
 
}
 

Aktuelle Jobs

Neue Themen


Oben