Hi ,
I tried solving the sudoku solver using backtracking but while backtracking its updating current index not previous index .
https://ide.codingblocks.com/#/s/12273
Than after that i watched the tutorial in coding blocks and followed that than also i am facing the same issue .
Could you please let me know where i am missing something .
Hy vikash,
public class Main {
public static void main(String[] args) {
int [] [] sudokuBoard = {{5,3,0,0,7,0,0,0,0},
{6,0,0,1,9,5,0,0,0},
{0,9,8,0,0,0,0,6,0},
{8,0,0,0,6,0,0,0,3},
{4,0,0,8,0,3,0,0,1},
{7,0,0,0,2,0,0,0,6},
{0,6,0,0,0,0,2,8,0},
{0,0,0,4,1,9,0,0,5},
{0,0,0,0,8,0,0,7,9}};
sudokuSolverMachine(sudokuBoard , 0 , 0);
}
private static boolean sudokuSolverMachine(int[][] sudokuBoard, int y, int x) {
// TODO Auto-generated method stub
if (y == sudokuBoard.length) {
printSudokuBoard(sudokuBoard);
return true;
}
if(x >= sudokuBoard[0].length) {
return sudokuSolverMachine(sudokuBoard, y+1, x);
}
if(sudokuBoard[y][x] != 0) {
return sudokuSolverMachine(sudokuBoard, y, x+1);
}
for(int i = 1 ; i <= 9 ; i++) {
if(canPlace(sudokuBoard,y,x,i)) {
sudokuBoard[y][x] = i;
boolean placedSuccessfully = sudokuSolverMachine(sudokuBoard, y, x+1);
if(placedSuccessfully) {
return true;
}
}
}
//backtracking
//Here its not backtracking to the previous index but current index is getting updated as 0 which is already zero
sudokuBoard[y][x] = 0;
return false;
}
private static void printSudokuBoard(int[][] sudokuBoard) {
// TODO Auto-generated method stub
for (int i = 0; i < sudokuBoard.length; i++) {
for (int j = 0; j < sudokuBoard[0].length; j++) {
System.out.print(sudokuBoard[i][j] +" | ");
}
System.out.println();
}
}
private static boolean canPlace(int[][] sudokuBoard, int y, int x, int i) {
// TODO Auto-generated method stub
int ySubArrIndex = (x/3)*3;
int xSubArrIndex = (y/3)*3;
for (int j = xSubArrIndex; j < xSubArrIndex+3; j++) {
for (int k = ySubArrIndex; k < ySubArrIndex+3; k++) {
if(sudokuBoard[j][k] == i) return false;
}
}
for(int num = 0 ; num < 9 ; num++) {
if(sudokuBoard[num][x] == i || sudokuBoard[y][num] == i) {
return false;
}
}
return true;
}
}
The following is the updated code you were having a small issue in the loop also the input you were trying is not solvable by this algorithm i guess, well i have checked the code for other inputs its working fine i will check the issue with your input and get back to you soon
Hi Sanket ,
Thanks bro for your response . When i am trying to execute your code its not solving the complete sudoku .
Please , find the link below .
5 | 3 | 1 | 2 | 7 | 6 | 4 | 9 | 8 |
6 | 0 | 0 | 1 | 9 | 5 | 0 | 0 | 0 |
0 | 9 | 8 | 0 | 0 | 0 | 0 | 6 | 0 |
8 | 0 | 0 | 0 | 6 | 0 | 0 | 0 | 3 |
4 | 0 | 0 | 8 | 0 | 3 | 0 | 0 | 1 |
7 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 6 |
0 | 6 | 0 | 0 | 0 | 0 | 2 | 8 | 0 |
0 | 0 | 0 | 4 | 1 | 9 | 0 | 0 | 5 |
0 | 0 | 0 | 0 | 8 | 0 | 0 | 7 | 9 |
https://ide.codingblocks.com/#/s/12281
As i have checked further on my code i found three issue .
1 ) I was running loop from 0 to > 9 (that was corrected by you)
2) I was not updating x to 0 when i was moving to next row
if(x >= sudokuBoard[0].length) {
return sudokuSolverMachine(sudokuBoard, y+1, x);// here x should be zero
}
3) The sudoku that i was trying as an input . I don’t think there can be output for that not sure (I believe it should be on first as per priority because of this i was not able to find another bug in code)
working code link https://ide.codingblocks.com/#/s/12285