help me out with my sudoku program

This is a discussion on help me out with my sudoku program within the C Programming forums, part of the General Programming Boards category; I wrote a program for solving sudoku puzzle with brute force algorithm. I'd check lots of times but couldn't catch ...

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    113

    help me out with my sudoku program

    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.

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,625
    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...

  3. #3
    Registered User
    Join Date
    Jan 2011
    Posts
    113
    @GReaper: I'm not shy to post it.. I just wanted to give it to guys who are interested.
    That's it.

  4. #4
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,625
    Quote Originally Posted by suryak View Post
    @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.

    Are you worried about someone "stealing" your algorithm? So what, is it that unique?
    Devoted my life to programming...

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  6. #6
    Registered User
    Join Date
    Jan 2011
    Posts
    113

    take a look at my code.

    I'd attached my code along with a "read me" file.. please take a look.

    Thanks for you help.
    Attached Files Attached Files

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  8. #8
    Registered User
    Join Date
    Jan 2011
    Posts
    113
    @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.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  10. #10
    Registered User
    Join Date
    Jan 2011
    Posts
    113
    @Adak: ... Exactly. this is what I'm facing. I used other puzzle but everything is turning down to 0..

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Note the problem with the if statements like:

    Code:
    if(2 < i < 6)  //for instance
       printf("* \n");
    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.

    The way to do it is:
    Code:
    if(2 < i && i < 6) //now both conditions are tested
       printf("* \n");
    Doesn't have any backtracking yet, so it's ability to solve a puzzle is VERY limited:

    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");
    }
    Just want to repeat that the above will NOT solve nearly any puzzles yet. Still needs backtracking logic added to it.
    Last edited by Adak; 09-21-2011 at 10:38 AM.

  13. #13
    Registered User
    Join Date
    Jan 2011
    Posts
    113

    With Improvements..

    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()

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with a Sudoku verifying program
    By Skeeter in forum C Programming
    Replies: 3
    Last Post: 10-30-2009, 08:15 PM
  2. Replies: 9
    Last Post: 10-24-2009, 08:39 AM
  3. sudoku program
    By ElemenT.usha in forum C Programming
    Replies: 1
    Last Post: 02-12-2008, 11:51 AM
  4. Newbie with a Sudoku Solver program
    By TylerBill in forum C Programming
    Replies: 13
    Last Post: 03-08-2006, 06:27 PM
  5. Sudoku program
    By Feite in forum C++ Programming
    Replies: 4
    Last Post: 11-26-2005, 01:50 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21