logan shin logan shin - 15 days ago 4
C++ Question

solve sudoku with backtracking - C++

So I am trying to solve sudoku with backtracking

And with this example :
example_pic

I hard-coded some of the indexes in the two dimensional array with numbers on places given from webSudoku (picture above).
It definitely has solutions but, my code prints "solution doesn't exist

Here is my code :

#include <stdio.h>
int a[10][10]= {0,};

bool is_valid(int x, int y, int value){
if(a[x][y] != 0) return false;
//check_row and column
for(int r=1; r<=9; r++){
if(value == a[x][r]) return false;
}
for(int c=1; c<=9; c++){
if(value == a[c][x]) return false;
}
//check 3*3 box
int x_start = (x+2)/3;
int y_start = (y+2)/3;
for(int ch_x = x_start; ch_x<x_start+3; ch_x++){
for(int ch_y=y_start; ch_y<y_start+3; ch_y++){
if(ch_x!=x && ch_y!=y){
if(value==a[ch_x][ch_y]) return false;
}
}
}
return true;
}

bool find(int &r, int &c){
// check if valid cells are exists
for(r=1; r<=9; r++){
for(c=1; c<=9; c++){
if(a[r][c] == 0)
return true;
}
}
return false;
}

bool solve(){
int r,c;
//base::case
if(!find(r,c)) return true;
for(int cand = 1; cand <=9; cand++){
if(is_valid(r,c,cand)){
a[r][c] = cand;
if(solve()) return true;
a[r][c] = 0;
}
}
return false;
}

void print(){
//print the sudoku plate
for(int i=1;i<=9; i++){
for(int j=1; j<=9; j++){
printf("%2d",a[i][j]);
}
printf("\n");
}
return ;
}

int main(){
//Fill in some empty grid with the known values
for(int i=1; i<=9; i++){
for(int j=1; j<=9; j++){
scanf("%1d",&a[i][j]);
}
}
if (solve()) print();
else printf("No solution exists");
return 0;
}


I guess my 'solve function' or 'is_valid' function is not working right.

In 'is_valid' function, if there is problem it would be

int x_start = (x+2)/3;
int y_start = (y+2)/3;
for(int ch_x = x_start; ch_x<x_start+3; ch_x++){
for(int ch_y=y_start; ch_y<y_start+3; ch_y++){
if(ch_x!=x && ch_y!=y){
if(value==a[ch_x][ch_y]) return false;
}
}
}


But, I also hard-coded this part and in my scope it doesn't seem like have problem.

In 'solve function'

bool solve(){
int r,c;
//base::case
if(!find(r,c)) return true;

//backtracking
for(int cand = 1; cand <=9; cand++){
if(is_valid(r,c,cand)){
a[r][c] = cand;
if(solve()) return true;
a[r][c] = 0;
}
}
return false;
}


I cant figure out where i got it wrong. If you find any other mistakes in the solve() function - let me know. Because I am not sure I understand the "backtracking" thing completely...

p.s. : reference I read (https://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf)

Answer

There are a few mistakes

  • You are mixing up (x, y) and (row, col) addressing (row is y, not x). Choose a representation and stick to it
  • There is a typo in is_valid because the check on (c, x) should be on (c, y) (or (y, c) depending on convention but surely using y and not x again)
  • The 3x3 sub-block computation is wrong... a correct formula could be for example int start_x = (x-1)/3*3 + 1, start_y = (y-1)/3*3 + 1;

Fixing all that the code works on the given example

Comments