logan shin - 1 year ago 96

C++ Question

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)

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**