You are using a version without Ads of this website. Please, consider donating:

### Backtracking sudoku solver

This works by backtracking. I've ran it a few times and it just gets stuck.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233`` `````` #include #include void print (int [][9]); bool checkvalidity (int [][9]); bool checkline (int [9]); int main () { //int sudoku_arr [9][9]; int sudoku_arr_copy [9][9]; //initialise all values to 0 //for (int a =0;a < 9; a++) // for (int b=0; b < 9; b++) // sudoku_arr [a][b] = 0; //entry of values int sudoku_arr [9][9] = {{0,0,2, 1,4,0 ,8,6,0}, {4,0,8, 2,5,0 ,0,0,0}, {1,7,0, 3,0,0 ,0,0,4}, {0,1,0, 0,0,0 ,0,7,6}, {6,0,5, 7,0,2 ,3,4,1}, {0,9,0, 0,0,0 ,0,2,8}, {5,2,0, 9,0,0 ,0,0,7}, {8,0,6, 5,7,0 ,0,0,0}, {0,0,7, 8,2,0 ,6,3,0}}; //copy sudoku box to copy for (int a =0;a < 9; a++) for (int b=0; b < 9; b++) sudoku_arr_copy [a][b] = sudoku_arr[a][b]; //BRUTE FORCE for (int pos =0; pos < 81; pos++ ) { if (sudoku_arr_copy [pos/9][pos%9] != 0) continue; bool deadend = false; while (!deadend) { if (sudoku_arr[pos/9][pos%9] == 9) { deadend = true; break; } sudoku_arr[pos/9][pos%9]++; if (!checkvalidity (sudoku_arr)) continue; if (checkvalidity (sudoku_arr)) break; } if (deadend) { //set value to zero sudoku_arr [pos/9][pos%9] = 0; //find immediately previous FILLABLE entry for (int backpos = pos - 1; backpos >=0 ; backpos--) { if ( sudoku_arr_copy [backpos/9][backpos%9] ==0) { pos = backpos; break; } } } } print (sudoku_arr); } //CHECK VALIDITY bool checkvalidity (int sudoku_arr[][9]) { int temp_arr [9]; //rows for (int a=0;a <9;a++) { for (int b=0;b <9; b++) temp_arr[b] = sudoku_arr[a][b]; if (!checkline (temp_arr)) return false; } //columns for (int a=0;a< 9;a++) { for (int b=0;b<9;b++) temp_arr [b] = sudoku_arr [b][a]; if (!checkline (temp_arr)) return false; } //mini_boxes int count =0; for (int d=0;d <9;d = d+3) { for (int a=0;a<9; a= a+3) { for (int c = d; c < (d+3);c++) { for (int b=a; b < (a +3);b++) { temp_arr [count] = sudoku_arr [c][b]; count++; } } //box gathered count =0; if (! checkline (temp_arr)) return false; } } //otherwise valid return true; } // bool checkline (int linearr_copy[9]) { std::sort (linearr_copy, linearr_copy + 9); for (int a=0; a<8;a++) { if (linearr_copy [a] == 0) continue; if (linearr_copy [a] == linearr_copy [a+1]) return false; } return true; } //PRINT void print (int sudoku_arr [][9]) { for (int a =0;a < 9; a++) { for (int b=0; b < 9; b++) { std::cout << sudoku_arr [a][b]; if (b ==2 || b== 5) std::cout << " "; } if (a ==2 || a== 5) std::cout <
Last edited on
It might not be that it's getting stuck... it might just be that it's taking forever to finish.

You have 42 empty spaces. That's ~942 permutations or ~10e39 permutations (that's a 1 with 39 zeros).

Even if you calculate 10 million permutations per millisecond (which you won't)... that means in a worst case scenario it will take 10e29 seconds or 3162315320758266140457 years to solve.

So yeah. Brute force isn't going to work.

EDIT:

My math isn't perfect here, you obviously will be short cutting a lot of permutations out by looking for early outs... but the point is it will take a long time.
Last edited on
Lol. I was reading wikipedia (http://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Brute-force_algorithm) and it said this was a 'practical method' of solving it.
I suppose I just wanted to know if it works in theory.
Well my math might be way off. =P

My numbers do assume a "dumb" brute force which will actually go through and plug all possible permutations into the puzzle (even those which will not solve it). Since you are only placing legal values I'm sure it'd be significantly faster... though I'd still imagine it'd be very slow.
I'm 99% sure it is genuinely getting stuck on the 2nd number as the value isn't changing. Can you see why?
Not immediately. But the easiest way to figure out where it's getting stuck is to step through with a debugger. Have you tried that yet?

I go over debugger basics here:

http://www.cplusplus.com/forum/beginner/75304/#msg403990
What you could do is modify your code so it can work with 2x2 of 2x2 squares of values in [1..4], instead of 3x3 of 3x3 squares of values in [1..9]. This should be easy enough to do if you replace your literals with constants

You will also need to tweak your output code to work with the modulus opertor rather than values.

That will make it easier to follow what's going on with the loop logic.

Andy
Last edited on
You could also give your code an almost completed puzzle (just one number left to find, two number, ...) and see it it can finish it off.

Or even a completed puzzle, to check the termination condition.

Andy
Last edited on
PS You should look at what happens after you set pos = backpos; on line 91

Either using a debugger, or by adding a bit of logging where the decisions are made.

Andy
Ah I hate debuggers!
rozick1 wrote:
Ah I hate debuggers debugging!

Fixed that for you.
Well, logging should be enough here.

But you need to get to know debuggers really well if you want to get into serious development!

Andy

PS

352 147 869
468 259 713
179 368 254

213 485 976
685 792 341
794 613 528

521 936 487
836 574 192
947 821 635

try count = 241
backtrack count = 3

cf

try count = 37652
backtrack count = 4157

for example here:

Sudoku
http://en.wikipedia.org/wiki/Sudoku

534 678 912
672 195 348
198 342 567

859 761 423
426 853 791
713 924 856

961 537 284
287 419 635
345 286 179

Last edited on
Topic archived. No new replies allowed.

You are using a version without Ads of this website. Please, consider donating: