Java CSP Sudoku-Solver

Bild: Java
Eine Klasse zum lösen von Sudoku-Rätseln. Als Input wird ein zweidimensionales Array von 9x9 Feldern benötigt. Für alle noch freien Felder muss der Wert 0 eingetragen werden. Falls keine Lösung gefunden wurde wird null zurückgegeben.


public class Sudoku {
  public static int[][] backtrackingSearch(int[][] field){
    return recursiveBacktrackingSearch(field, 0);
  }
 
  private static int[][] recursiveBacktrackingSearch(int[][] field, int pos){
    if(pos == 9*9) return field;
    if(field[pos/9][pos%9] != 0) return recursiveBacktrackingSearch(field, pos+1);
    for(int i = 1; i <= 9; i++){
      if(isConsistent(field, pos, i)){
        field[pos/9][pos%9] = i;
        int[][] returnvalue = recursiveBacktrackingSearch(field, pos+1);
        if(returnvalue != null) return returnvalue;
        field[pos/9][pos%9] = 0;
      }
    }
    return null;
  }

  private static boolean isConsistent(int[][] field, int pos, int val){
    for(int i = 0; i < 9; i++){
      if(field[pos/9][i] == val) return false;
    }
    for(int i = 0; i < 9; i++){
      if(field[i][pos%9] == val) return false;
    }
    for(int i = 0; i < 3; i++){
      for(int j = 0; j < 3; j++){
        if(field[((pos/9)/3)*3+i][((pos%9)/3)*3+j] == val) return false;
      }
    }
  return true;
  } 
}
Das Ganze wird bsp. mit folgendem Code aufgerufen.
int[][] field = {{2, 0, 0, 0, 5, 6, 0, 0, 0},
                 {0, 0, 0, 1, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0, 0},
                 {1, 0, 0, 0, 0, 0, 0, 4, 0},
                 {0, 0, 2, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 7, 0, 0, 0},
                 {0, 0, 7, 0, 0, 0, 1, 0, 0},};
field = Sudoku.backtrackingSearch(field);
Bookmark and Share

0 Kommentare:

Kommentar veröffentlichen