8000 Merge pull request #42 from SMN321/all-contributors/add-SMN321 · sonwanigaurav/Java-Algorithms@aef6661 · GitHub
[go: up one dir, main page]
Skip to content

Commit aef6661

Browse files
darpanjboradarpanjbora
authored
Merge pull request darpanjbora#42 from SMN321/all-contributors/add-SMN321
added backtracking for Sudoku
2 parents ae02a3c + 246d79d commit aef6661

File tree

1 file changed

+220
-0
lines changed

1 file changed

+220
-0
lines changed

‎Backtracking/SudokuSolver.java

Lines changed: 220 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,220 @@
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+
10000 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

Comments
 (0)
0