|
| 1 | +//Solves Sudokus with the approach of backtracking |
| 2 | + |
| 3 | +public class SudokuSolver{ |
| 4 | + |
| 5 | + static int[][] grid; //= new int[9][9]; |
| 6 | + static int recursionDepth = 0; |
| 7 | + static int changes = 0; |
| 8 | + |
| 9 | + //Driver method |
| 10 | + public static void main(String[] args){ |
| 11 | + grid = new int[][] {{7, 0, 9, 3, 0, 0, 0, 0, 0}, |
| 12 | + {0, 1, 0, 5, 0, 0, 6, 0, 0}, |
| 13 | + {5, 0, 3, 0, 1, 0, 2, 4, 9}, |
| 14 | + |
| 15 | + {0, 3, 0, 9, 5, 0, 7, 0, 0}, |
| 16 | + {4, 0, 0, 1, 0, 0, 0, 0, 8}, |
| 17 | + {0, 0, 0, 0, 3, 8, 0, 6, 0}, |
| 18 | + |
| 19 | + {3, 0, 1, 0, 6, 0, 4, 0, 2}, |
| 20 | + {0, 0, 2, 0, 0, 1, 0, 7, 0}, |
| 21 | + {0, 0, 0, 0, 0, 3, 9, 0, 0}}; |
| 22 | + |
| 23 | + boolean[][] boolGrid = fillBoolGrid(grid); |
| 24 | + |
| 25 | + System.out.println("\nTo solve: \n"); |
| 26 | + draw(grid); |
| 27 | + |
| 28 | + //start at the top left |
| 29 | + int rowCurrent=0, columnCurrent=0, rowNext, columnNext, numberLast=0; |
| 30 | + |
| 31 | + if(boolGrid[0][0]){ |
| 32 | + rowNext = 0; |
| 33 | + columnNext = 0; |
| 34 | + } else{ |
| 35 | + int nextFieldReturn = nextField(boolGrid, rowCurrent, columnCurrent); |
| 36 | + rowNext = nextFieldReturn/10; |
| 37 | + columnNext = nextFieldReturn%10; |
| 38 | + } |
| 39 | + |
| 40 | + boolean solvable = false; |
| 41 | + |
| 42 | + try{ |
| 43 | + solvable = solve(grid, boolGrid, rowNext, columnNext); |
| 44 | + } catch(Exception e){ |
| 45 | + e.printStackTrace(); |
| 46 | + } |
| 47 | + |
| 48 | + if(solvable){ |
| 49 | + System.out.println("\n\nSolution: \n"); |
| 50 | + draw(grid); |
| 51 | + System.out.println("\nMaximum depth of recursion: " + recursionDepth); |
| 52 | + System.out.println("Number of changes: " + changes); |
| 53 | + } else { |
| 54 | + System.out.println("Not solvable!"); |
| 55 | + } |
| 56 | + } |
| 57 | + |
| 58 | + //checks if the number fits at the given position |
| 59 | + static boolean check(int[][] grid, int row, int column, int number){ |
| 60 | + |
| 61 | + for(int indexRow=0; indexRow<9; indexRow++){ |
| 62 | + if(number == grid[indexRow][column]){ |
| 63 | + return false; |
| 64 | + } |
| 65 | + } |
| 66 | + |
| 67 | + for(int indexColumn=0; indexColumn<9; indexColumn++){ |
| 68 | + if(number == grid[row][indexColumn]){ |
| 69 | + return false; |
| 70 | + } |
| 71 | + } |
| 72 | + |
| 73 | + int borderColumn = column/3*3; |
| 74 | + int borderRow = row/3*3; |
| 75 | + for(int indexBlockColumn = borderColumn; indexBlockColumn < borderColumn+3; indexBlockColumn++){ |
| 76 | + for(int indexBlockRow = borderRow; indexBlockRow < borderRow+3; indexBlockRow++){ |
| 77 | + if(number == grid[indexBlockRow][indexBlockColumn]){ |
| 78 | + return false; |
| 79 | + } |
| 80 | + } |
| 81 | + } |
| 82 | + return true; |
| 83 | + } |
| 84 | + |
| 85 | + |
| 86 | + //returns 10*nextRow + nextColumn so that nextRow = nextField/10 and nextColumn = nextField%10 |
| 87 | + static int nextField(boolean[][] boolGrid, int rowCurrent, int columnCurrent){ |
| 88 | + |
| 89 | + int rowNext, columnNext; |
| 90 | + //at the end of a row |
| 91 | + if(columnCurrent >= 8){ |
| 92 | + columnNext = 0; |
| 93 | + rowNext = rowCurrent+1; |
| 94 | + } else { |
| 95 | + columnNext = columnCurrent+1; |
| 96 | + rowNext = rowCurrent; |
| 97 | + } |
| 98 | + |
| 99 | + for(int row=rowNext; row<9; row++){ |
| 100 | + for(int column=columnNext; column<9; column++){ |
| 101 | + if(boolGrid[row][column]){ //true if the field is changeable |
| 102 | + return (int) 10*row + column; //for conersion back: row=return/10, column=return%10 |
| 103 | + } |
| 104 | + } |
| 105 | + columnNext = 0; |
| 106 | + } |
| 107 | + return -1; //if there are no more fields |
| 108 | + } |
| 109 | + |
| 110 | + //creates a boolean-grid to safe which field is changeable |
| 111 | + static boolean[][] fillBoolGrid(int[][] grid){ |
| 112 | + boolean[][] boolGrid = new boolean[9][9]; |
| 113 | + for(int row=0; row<9; row++){ |
| 114 | + for(int column=0; column<9; column++){ |
| 115 | + if(grid[row][column] == 0){ //erfüllt wenn wir ein bearbeitbares Feld kontrollieren |
| 116 | + boolGrid[row][column] = true; |
| 117 | + } |
| 118 | + } |
| 119 | + } |
| 120 | + return boolGrid; |
| 121 | + } |
| 122 | + |
| 123 | + //returns the previously changed Field encoded with 10*previousRow + previousColumn |
| 124 | + static int lastField(boolean[][] boolGrid, int rowCurrent, int columnCurrent){ |
| 125 | + |
| 126 | + int columnLast, rowLast; |
| 127 | + |
| 128 | + if(columnCurrent == 0){ |
| 129 | + columnLast = 8; |
| 130 | + rowLast = rowCurrent-1; |
| 131 | + } else { |
| 132 | + columnLast = columnCurrent-1; |
| 133 | + rowLast = rowCurrent; |
| 134 | + } |
| 135 | + |
| 136 | + for(int row=rowLast; row>=0; row--){ |
| 137 | + for(int column=columnLast; column>=0; column--){ |
| 138 | + if(boolGrid[row][column]){ |
| 139 | + return (int) 10*row + column; //for conversion back: row=return/10, column=return%10 |
| 140 | + } |
| 141 | + } |
| 142 | + columnLast = 8; |
| 143 | + } |
| 144 | + return -1; //if there is no previous field |
| 145 | + |
| 146 | + } |
| 147 | + |
| 148 | + //coordinated the process |
| 149 | + //returns true if a number was placed and false if no number has been placed |
| 150 | + static boolean solve(int[][] grid, boolean[][] boolGrid, int rowCurrent, int columnCurrent){ |
| 151 | + |
| 152 | + recursionDepth++; |
| 153 | + |
| 154 | + //System.out.println("recursionDepth Current: " + recursionDepth); |
| 155 | + |
| 156 | + int testnumber = 1; |
| 157 | + boolean alreadyChanged = false; |
| 158 | + |
| 159 | + do{ |
| 160 | + //System.out.println("testnumber " + testnumber); |
| 161 | + if(check(grid, rowCurrent, columnCurrent, testnumber)){ |
| 162 | + grid[rowCurrent][columnCurrent] = testnumber; |
| 163 | + |
| 164 | + alreadyChanged = true; //indicates if the number has already been changed |
| 165 | + |
| 166 | + int nextFieldReturn = nextField(boolGrid, rowCurrent, columnCurrent); |
| 167 | + |
| 168 | + if(nextFieldReturn == -1){ //if finished |
| 169 | + return true; |
| 170 | + } |
| 171 | + |
| 172 | + int rowNext = nextFieldReturn/10; |
| 173 | + int columnNext = nextFieldReturn%10; |
| 174 | + |
| 175 | + if(solve(grid, boolGrid, rowNext, columnNext)){ |
| 176 | + return true; //if no changes are necessary |
| 177 | + } else { |
| 178 | + grid[rowCurrent][columnCurrent] = 0; //step backwards |
| 179 | + alreadyChanged = false; |
| 180 | + changes++; |
| 181 | + } |
| 182 | + |
| 183 | + } |
| 184 | + testnumber++; |
| 185 | + |
| 186 | + }while(testnumber<10); |
| 187 | + |
| 188 | + if(!alreadyChanged){ //if no number has been changed |
| 189 | + grid[rowCurrent][columnCurrent] = 0; |
| 190 | + recursionDepth--; |
| 191 | + return false; |
| 192 | + } |
| 193 | + return false; |
| 194 | + } |
| 195 | + |
| 196 | + //draws the grid |
| 197 | + static void draw(int[][] feld){ |
| 198 | + for(int a = 0; a < feld[1].length; a++){ |
| 199 | + String row = ""; |
| 200 | + |
| 201 | + if (a % 3 == 0) { |
| 202 | + for (int i = 0; i < feld.length; i++) { |
| 203 | + row += "--"; |
| 204 | + } |
| 205 | + row += "-----\n"; |
| 206 | + } |
| 207 | + |
| 208 | + row += "|"; |
| 209 | + |
| 210 | + for(int b = 0; b < feld.length; b++){ |
| 211 | + row = row + feld[a][b] + ((b+1) % 3 == 0 && b < feld.length - 1 ? " | " : "|"); |
| 212 | + } |
| 213 | + |
| 214 | + row += "\n"; |
| 215 | + |
| 216 | + System.out.print(row); |
| 217 | + } |
| 218 | + } |
| 219 | + |
| 220 | +} |
0 commit comments