I wrote a program for solving sudoku puzzle with brute force algorithm.
I'd check lots of times but couldn't catch the bug. Its really irritating.
If you are interested to look at my code and help me out of it.. please to reply to this post or drop a message. I'll send my code to you.
Thanks.
Hmm, too shy to post it? If it's too big attach it with a file.
EDIT: Sorry, but it's a lot harder, at least for me, to debug other people's code
Last edited by GReaper; 09-20-2011 at 02:13 AM.
Devoted my life to programming...
@GReaper: I'm not shy to post it.. I just wanted to give it to guys who are interested.
That's it.
Well, if you post it here for everyone to see, you'll probably get more answers.Originally Posted by suryak
Are you worried about someone "stealing" your algorithm? So what, is it that unique?
Devoted my life to programming...
There are only three things that have to be checked for accuracy --
1) the digit in each cell of each row, is unique to the row
2) the digit in each cell of each column, is unique to the column
and
3) the digit in each cell of the 9 cell "box", is unique to the box.
If working with the entire 81 cells is difficult for you, change the puzzle to just 1 row, or maybe 3 rows. Chances are, your bug will still be there, and much easier to find.
Think of it like this: the bug can't run and hide from you. Go put on your deer stalking cap and grab your pipe and Dr. Watson for a wingman, and get your brain into sleuthing mode!
If your Sherlock Holmes impression should meet it's Dr. Moriarty, and fail, then post your code up, and I'll take a look at it. This is a public forum, and doing stuff "sub rosa", goes against the whole purpose of the forum.
Last edited by Adak; 09-20-2011 at 03:17 AM.
I'd attached my code along with a "read me" file.. please take a look.
Thanks for you help.
It doesn't look bad at all.
I was hoping you'd take a bit longer than 16 minutes to try and debug it, however.
What are the "bk " variables, all about? It's wickedly late here, so I'll have to put off studying it more, for tonight.
What puzzle does it fail on? Just post up a string and I'll set it to load up from it:
123000456789...etc.
@Adak:
I TempArr[][] is the copy of input array. So, to go back to the previous location..
"bk" --> back.
That's the reason why I used "bki" & "bkj" in for loop. nothing special.
Actually, I'm not getting answer to the puzzle.. I think that.. there is problem in between lines (50 - 75) .. I feel all functions I defined work perfectly.
A few quick suggestions:
1) Make prototypes for all your functions except main(), and put them above the first line of main().
2) Take your block of code that prints the puzzle, out of the end of main(), and put it into it's own function. That way, it can be called from anywhere, to help debug.
3) Set up your logic, so if the initial board is all zero's, it should figure out the lowest possible solution:
123|456|789
456|789|123
789|123|456
---+---+---
etc.
When I do this now, I get one 1 in the upper left hand corner (first cell), and the rest of the cells stay 0.
@Adak: ... Exactly. this is what I'm facing. I used other puzzle but everything is turning down to 0..
I found the problem with checking for row, and column. I'm re-doing row, column and box checking, and I'll post that up when it's done.
What I want you to do is read up on the "Backtracking" algorithm. You'll need something like that, to make it a working solver.
Last edited by Adak; 09-21-2011 at 10:35 AM.
Note the problem with the if statements like:
Will ALWAYS print the * if i greater than 2, because the < 6 part of the statement is not evaluated. This is called a cut off, or short circuit of the test.Code:if(2 < i < 6) //for instance printf("* \n");
The way to do it is:
Doesn't have any backtracking yet, so it's ability to solve a puzzle is VERY limited:Code:if(2 < i && i < 6) //now both conditions are tested printf("* \n");
Just want to repeat that the above will NOT solve nearly any puzzles yet. Still needs backtracking logic added to it.Code:# include <stdio.h> //global declaration int sudoku[9][9]={ {0,0,0,0,0,0,0,0,0}, {4,5,6,7,8,9,0,0,0}, {7,8,9,0,0,0,0,0,0}, {0,0,4,3,6,5,8,9,7}, {0,6,5,8,9,7,2,0,4}, {8,9,7,2,0,4,0,6,5}, {5,3,0,6,4,0,9,7,8}, {0,0,0,9,7,8,0,0,0}, {0,0,0,0,0,0,0,0,0} }; int check (int, int, int); int check_box (int, int, int); int check_column(int, int, int); int check_row(int, int, int); void printIt(void); void printTest(char [][12]); int main(void) { //local declarations int TempArr[9][9]; int i,j,n; //int bki,bkj; //int walk_j=0,walk_n=1; //int flag1,flag2; char testGrid[11][12] = { {"123|456|789"}, {"456|789|123"}, {"789|123|456"}, {"---+---+---"}, {"214|365|897"}, {"365|897|214"}, {"897|214|365"}, {"---+---+---"}, {"531|642|978"}, {"642|978|531"}, {"978|531|642"} }; // Input //printf("Enter Sudoku\n"); for (i=0; i<9; i++) { for (j=0; j<9; j++) { //scanf("%d",&sudoku[i][j]); //copy to TempArr TempArr[i][j] = sudoku[i][j]; } } // brute force. for (i=0; i<9; i++) { //walk_j=0; for (j=0; j<9; j++) { if (sudoku[i][j]==0) { for (n=1;n<10;n++) { //flag1=0; if ( check(i,j,n) == 1) { sudoku[i][j]=n; //walk_n=1; break; } //else // flag1 = 1; } //for n }//if //flag2 = 0; /* if (flag1==1) { for (bki=i;bki>=0;bki--) { for (bkj=j-1;bkj>=0;bkj--) { if (TempArr[bki][bkj]==0) { sudoku[i][j]=0; sudoku[bki][bkj]=0; i = bki; walk_j = bkj; walk_n = n+1; flag2 = 1; break; } }// bkj if (flag2==1) break; }//bki }//flag1 */ }//for j }//for i printTest(testGrid); printIt(); return 0; }// main /* functions ---- */ int check (int i, int j, int n) { if (check_row(i,j,n) == 1) { if (check_column(i,j,n) == 1) { if (check_box(i,j,n) == 1) { return 1; } } } return 0; } int check_box (int i, int j, int n) { /* avoid <= and >=. Use < next highest number or > next lowest number. Consider speed which does not diminish clarity, to be a central part of the design of this program. */ int loci, locj; int lorow, hirow, locol, hicol; if (i < 3) //start of box 1, 2 & 3 { lorow = 0; hirow = 3; if(j < 3) { locol = 0; hicol = 3; } else if(2 < j && j < 6) { locol = 3; hicol = 6; }//box2 else { //j must be 6, 7, or 8 locol = 6; hicol = 9; } }//end of box 1, 2, & 3 else if (2 < i && i < 6) { //start of box 4, 5, & 6 lorow = 3; hirow = 6; if (j < 3) { locol = 0; hicol = 3; } else if (2 < j && j < 6) { locol = 3; hicol = 6; }//box5 else { //j must be 6, 7, or 8 locol = 6; hicol = 9; } }//end of box 4, 5, & 6 else if (5 < i && i < 9) { //start of box 7, 8, & 9 lorow = 6; hirow = 9; if (j < 3) { locol = 0; hicol = 3; } else if (2 < j && j < 6) { locol = 3; hicol = 6; } else { locol = 6; locol = 9; } }//end of boxes 7, 8 & 9 for (loci=lorow; loci<hirow; loci++) { for (locj=locol; locj<hicol; locj++) { //if (loci != i) //{ // if (locj != j) // { if (sudoku[loci][locj]==n) return 0; //} //} } } return 1; } int check_row(int i, int j, int n) { int walkj; //keep it clear, and minimize your variables and code, or your //solver will run very slowly. /* when testing rows, you only test the current digit, against the digits on it's left. So the checkrow variable decrements, not increments. And you only test in the one row, not in any other row. */ for (walkj=j;walkj>-1;walkj--) { if (sudoku[i][walkj]==n) //column varies, not the row { return 0; } } return 1; } int check_column(int i, int j, int n) { int walki; /* same idea as check row, above. Minimize everything, keep it clear, check ONLY the digits ABOVE this cell, in this one column. */ for (walki=i;walki>-1;walki--) { if (sudoku[walki][j]==n) //row varies, not the column { return 0; } } return 1; } void printIt(void) { int i, j; // output printf("\n+-----+-----+-----+\n"); for (i=0;i<9;i++) { printf("| "); for (j=0;j<9;j++) { printf("%d",sudoku[i][j]); if(j==2 || j==5 || j==8) printf(" | "); } printf("\n"); if(i==2 || i==5) printf("+-----+-----+-----+\n"); } printf("+-----+-----+-----+\n"); } void printTest(char testGrid[][12]) { int i; printf("\nThe Test Grid is:\n"); for(i=0;i<11;i++) printf("%s\n", testGrid[i]); printf("\n"); }
Last edited by Adak; 09-21-2011 at 10:38 AM.
Hi Adak.
Thanks for showing interest in my problem. Sorry for not replying for a while. Actually, I am working on it for some time without distractions.
I made some distinctive improvements in my code and this could able to solve medium level puzzles perfectly. The thing is according to brute force algorithm, if input is right, no matter how much difficult the puzzle may be, still you'll get your answer on the screen.
The thing is when I give some difficult puzzle as input, its not showing. I think there is some small bug which is hiding.. why don't you try to catch.
[ I made this puzzle flexible to solve 6X6 grid also. but I'd set this code for 9X9 for now. ]
Code:# include <stdio.h> # define size 9 //array size # define nmax 10 // max number in array [ 10 for 9x9, 7 for 6x6 ] //global declaration int sudoku[size][size]; int TempArr[size][size]; //prototypes int BruteForceAlgo (void); int check (int i, int j, int n); int check_box_6x6 (int i, int j, int n); int check_box_9x9 (int i, int j, int n); int check_row (int i, int j, int n); int check_column (int i, int j, int n); int output (void); int main(void) { int i,j; // Input printf("Enter Sudoku\n"); for (i=0; i<size; i++) { for (j=0; j<size; j++) { scanf("%d",&sudoku[i][j]); //copy to TempArr TempArr[i][j] = sudoku[i][j]; } } printf("Thanks for entering\n"); BruteForceAlgo(); output(); }// main /*----------------------------------functions --------------------------------- */ int check (int i, int j, int n) { if (check_row(i,j,n) == 1) { if (check_column(i,j,n) == 1) { if (check_box_9x9(i,j,n) == 1) { return 1; } else return 0; } else return 0; } else return 0; } // check(); int check_box_6x6 (int i, int j, int n) { int loci, locj; int i0, i1, j0, j1; int flag1; if (i>=0 && i<=1 && j>=0 && j<=2) { i0 = 0; i1 = 1; j0 = 0; j1 = 2; }//box1 else if (i>=0 && i<=1 && j>=3 && j<=5) { i0 = 0; i1 = 1; j0 = 3; j1 = 5; }//box2 else if (i>=2 && i<=3 && j>=0 && j<=2) { i0 = 2; i1 = 3; j0 = 0; j1 = 2; }//box3 else if (i>=2 && i<=3 && j>=3 && j<=5) { i0 = 2; i1 = 3; j0 = 3; j1 = 5; }//box4 else if (i>=4 && i<=5 && j>=0 && j<=2) { i0 = 4; i1 = 5; j0 = 0; j1 = 2; }//box5 else if (i>=4 && i<=5 && j>=3 && j<=5) { i0 = 4; i1 = 5; j0 = 3; j1 = 5; }//box6 for (loci=i0; loci<=i1; loci++) { for (locj=j0; locj<=j1; locj++) { if (loci != i || locj != j) { flag1 = 0; if (sudoku[loci][locj]==n) return 0; else flag1 = 1; } } } if (flag1==1) return 1; } // check_box_6x6() end. int check_box_9x9 (int i, int j, int n) { int loci, locj; int i0, i1, j0, j1; int flag1; //box1 if (i>=0 && i<=2 && j>=0 && j<=2) { i0 = 0; i1 = 2; j0 = 0; j1 = 2; } //box2 if (i>=0 && i<=2 && j>=3 && j<=5) { i0 = 0; i1 = 2; j0 = 3; j1 = 5; } //box3 if (i>=0 && i<=2 && j>=6 && j<=8) { i0 = 0; i1 = 2; j0 = 6; j1 = 8; } //box4 if (i>=3 && i<=5 && j>=0 && j<=2) { i0 = 3; i1 = 5; j0 = 0; j1 = 2; } //box5 if (i>=3 && i<=5 && j>=3 && j<=5) { i0 = 3; i1 = 5; j0 = 3; j1 = 5; } //box6 if (i>=3 && i<=5 && j>=6 && j<=8) { i0 = 3; i1 = 5; j0 = 6; j1 = 8; } //box7 if (i>=6 && i<=8 && j>=0 && j<=2) { i0 = 6; i1 = 8; j0 = 0; j1 = 2; } //box8 if (i>=6 && i<=8 && j>=3 && j<=5) { i0 = 6; i1 = 8; j0 = 3; j1 = 5; } //box9 if (i>=6 && i<=8 && j>=6 && j<=8) { i0 = 6; i1 = 8; j0 = 6; j1 = 8; } for (loci=i0; loci<=i1; loci++) { for (locj=j0; locj<=j1; locj++) { if (loci != i || locj != j) { flag1 = 0; if (sudoku[loci][locj]==n) return 0; else flag1 = 1; } } } if (flag1==1) return 1; } //check_box_9x9() int check_row(int i, int j, int n) { int walki; int flag1; for (walki=0;walki<size;walki++) { flag1 = 0; if (sudoku[walki][j]==n) { return 0; } else { flag1 = 1; } } if (flag1==1) return 1; } //check_row() int check_column(int i, int j, int n) { int walkj; int flag1; for (walkj=0;walkj<size;walkj++) { flag1 = 0; if (sudoku[i][walkj]==n) { return 0; } else { flag1 = 1; } } if (flag1==1) return 1; } //check_column() int output (void) { int i,j; printf("\n"); printf("-------------------------\n"); for (i=0;i<size;i++) { for (j=0;j<size;j++) { printf("%d ",sudoku[i][j]); } printf("\n"); } printf("--------------------------\n"); } //output(); /* ----------------- Brute Force, Code.-----------------------------*/ int BruteForceAlgo (void) { int i,j,n; int bki,bkj; int dyN=1; //dynamic: dy, number:N int flag1,flag2; // brute force. for (i=0; i<size; i++) { for (j=0; j<size; j++) { if (sudoku[i][j]==0) { for (n=dyN; n<nmax; n++) { flag1=0; if (check(i,j,n)==1) { sudoku[i][j]=n; dyN=1; break; } else flag1=1; } } if (flag1==1) { for (bki=i; bki>=0; bki--) { for (bkj=j-1; bkj>=0; bkj--) { if (TempArr[bki][bkj]==0) { flag2=0; if (sudoku[bki][bkj]==nmax-1) sudoku[bki][bkj]=0; else { dyN=sudoku[bki][bkj]+1; sudoku[bki][bkj]=0; i = bki; j = bkj-1; flag2=1; break; } } } if (flag2==1) break; } } } } }//BruteForceAlgo()
Backtracking isn't separate from a brute force solver, but should be part of it. Any way you do a brute force solver, it will ALWAYS solve a valid Sudoku problem grid, that you give it, if it's working correctly. ALWAYS!
The only question (especially for larger grids - like 12 X 12 or 16 X 16), is how long will it take to find the solution?
So, go read up on backtracking. As you work to implement it, you'll find any bugs you have, I'm sure.
Then go to the Sudoku Programming Forum at:
Sudoku Programmers :: Index
These guys have a great passion for this, and they have forgotten more about programming Sudoku, then sane folk will ever learn, I'm sure!
If you use the printIt() function I wrote for your program, you'll have a good looking display for any 9 X 9 grid on the forum. (Use code tags, of course).
