My brute force code written in C got a hidden bug

Programs which generate, solve, and analyze Sudoku puzzles

My brute force code written in C got a hidden bug

Postby spk012 » Tue Nov 15, 2011 5:41 pm

I've written a sudoku solver using Brute Force Algorithm.
So, it could solve puzzles of certain level but not all. Take a look into this puzzle, which my code isn't able to solve.
Code: Select all
9 0 5 0 0 0 0 0 8
4 0 0 5 7 0 1 0 6
0 2 7 6 0 0 0 4 0
0 9 6 0 0 3 5 1 2
7 0 4 0 1 0 3 0 0
2 1 0 9 8 0 0 0 4
0 8 1 0 0 4 0 9 0
3 0 0 8 0 0 0 5 1
0 0 2 0 0 7 0 6 0


So, here is the brute force code I have written... could you please help me to catch the bug in it.

Code: Select all
# include <stdio.h>
# include "lib.h"

extern int sudoku[size][size];
extern int TempArr[size][size];
       int i, j, n;

int BruteForce (void)
{
    int val;
   
   for (i=0; i<size; i++)
   {
       for (j=0; j<size; j++)
       {
           if (sudoku[i][j]==0)
           {   
                               for (n=1; n<nmax; n++)
                               {               
                                   val = check(i,j,n);         
                                   if (val==1)
                                   {
                                              sudoku[i][j]=n;
                                            //  output();
                                              break;
                                   }                 
                                   else if (n==nmax-1 && val == 0)
                                           back();
                               }
           }
       }
   }
   
}

int back(void)
{
      int iback,jback,flag=0;
     
      sudoku[i][j]=0;
      for (iback=i; iback>=0; iback--)
      {
          for (jback=j; jback>=0; jback--)
          {                           
              if (!(iback==i && jback==j) && TempArr[iback][jback]==0)
              {                         
                           flag=0;                                   
                           if (sudoku[iback][jback]==nmax-1)
                                 sudoku[iback][jback]=0;
                           else
                           {
                                n=sudoku[iback][jback];
                                sudoku[iback][jback]=0;
                                i = iback; j = jback;
                                flag=1;
                                break;
                           }
              }
          }
          if (flag==1)
              break;
      }
     
}



Code description:

1. This code follows brute force algorithm as mentioned in wikipedia.
2. sudoku[][] is the input sudoku file, TempArr[][] is a copy of that which I use for reference.
3. check(i,j,n): If it returns 1 => n can be assigned to sudoku[i][j] or else if it returns 0, it can't be assigned.

code>>
First, the loop starts iterating from i=0, j=0.. if it finds an empty cell ( i.e, 0 ), it enters into another loop which starts iterating from 1 to 9 (nmax=10, so.. nmax-1=9). If check() return 1 for any value, it assigns and goes to another empty cell.

For a particular cell, if check() doesn't return 1 from n=1 to nmax-1 (9), it goes back to the previous empty cell and starts iterating from where it left and continues. This is where we need TempArr[][] to locate previous empty cell.

Please help me!
spk012
 
Posts: 6
Joined: 15 November 2011

Re: My brute force code written in C got a hidden bug

Postby dobrichev » Tue Nov 15, 2011 7:32 pm

Hi,

Use another solver to see whether your example puzzle has solution(s) at all.
Knowing the solution, use debugger and see at which point your code bypasses it.
What is the expected return value of the BruteForce function? What is the success/failure criteria?
Where are you initializing size, nmax, TempArr, sudoku?
Could check function change some of the global variables?

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: My brute force code written in C got a hidden bug

Postby spk012 » Wed Nov 16, 2011 12:40 pm

Those nmax is defined in lib.h and sudoku[][], TempArr[][] are defined in main() as global variables.
I'm still trying to debug it but I though someone on a forum would catch it easily.
spk012
 
Posts: 6
Joined: 15 November 2011

Re: My brute force code written in C got a hidden bug

Postby simes » Sun Dec 11, 2011 3:30 pm

The whole structure is wrong. Consider this scenario:
1. (1,2) is zero, so you go through the N loop, and find that, say, 1 is allowed. Put in into the cell, break the N loop, and move on to the next cell.
2. At some point further on, you reach an impasse, and so backtrack. How can you return to cell (1,2) so you can try the remaining 2...9? You can't because the I and J loops have moved on.

Brute force is often best handled with recursion, and then it becomes a fairly simple exercise. Something like:
Code: Select all
int SolveCell(x,y)
  if (x>Max || y>Max) {
    // we've found a solution
    Output();
    exit;
  }

  // get coords of next cell
  x2 = x+1;
  y2 = y;
  if(x2 > Max) {
    x2 = 1;
    y2 = y + 1;
  }

  if (Sudoku[x][y] == 0)  {
     for (int n=1; n<Max; n++) {
       if(Check(x,y,n) == 1) { // is this a valid move?
           Sudoku[x][y] = n;
           SolveCell(x2,y2);
           Sudoku[x][y] = 0; // for when we backtrack
        }
     }
  } else {
     SolveCell(x2,y2);
 }

(Forgive my pseudocode, I've not written C in a looong time.)

You can optimise this a bit - for example, instead of just finding the next cell, find the next empty cell.
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Re: My brute force code written in C got a hidden bug

Postby spk012 » Thu Dec 15, 2011 4:11 am

Actually, that's where back() comes in to play.

when we assign 1 at (1,2) and moved on to the next cell and found that all our choices are closed.. back() comes into picture.
back() takes us to the (1,2). As TempArr[][] is the copy of the original sudoku input. With the help of it, we can move.
spk012
 
Posts: 6
Joined: 15 November 2011

Re: My brute force code written in C got a hidden bug

Postby m_b_metcalf » Thu Dec 15, 2011 6:33 am

dobrichev wrote:Use another solver to see whether your example puzzle has solution(s) at all.

Code: Select all
singles found 1 solution
  9  6  5  4  2  1  7  3  8
  4  3  8  5  7  9  1  2  6
  1  2  7  6  3  8  9  4  5
  8  9  6  7  4  3  5  1  2
  7  5  4  2  1  6  3  8  9
  2  1  3  9  8  5  6  7  4
  6  8  1  3  5  4  2  9  7
  3  7  9  8  6  2  4  5  1
  5  4  2  1  9  7  8  6  3
  1 1  is redundant
  1 3  is redundant
  1 9  is redundant
  2 1  is redundant
  2 4  is redundant
  2 5  is redundant
  2 7  is redundant
  2 9  is redundant
  3 3  is redundant
  3 4  is redundant
  3 8  is redundant
  4 2  is redundant
  4 3  is redundant
  4 6  is redundant
  4 7  is redundant
  4 8  is redundant
  4 9  is redundant
  5 1  is redundant
  5 3  is redundant
  5 7  is redundant
  6 1  is redundant
  6 2  is redundant
  6 4  is redundant
  6 5  is redundant
  6 9  is redundant
  7 2  is redundant
  7 3  is redundant
  7 8  is redundant
  8 1  is redundant
  8 4  is redundant
  8 8  is redundant
  8 9  is redundant
  9 3  is redundant
  9 6  is redundant
  9 8  is redundant

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8416
Joined: 15 May 2006
Location: Berlin

Re: My brute force code written in C got a hidden bug

Postby daj95376 » Thu Dec 15, 2011 10:18 am

Code: Select all
int back(void)
{
      int iback,jback,flag=0;
     
      sudoku[i][j]=0;
      for (iback=i; iback>=0; iback--)
      {
          for (jback=j; jback>=0; jback--)
          {                           

When the inner loop reaches jback=(-1), then you return to the outer loop and decrement iback. So far so good.

Now you return to the inner loop and set jback=(j) instead of jback=(nmax-1). Not good!

Regards, Danny A. Jones
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: My brute force code written in C got a hidden bug

Postby eleven » Thu Dec 15, 2011 10:24 am

Ah, Danny was first :)

spk012,

look at your back() function. jback always goes down from j to 0, instead of from 9 to 0, when you go back to the previous row.
Better do something like this:
Code: Select all
      jback=j;
      for (iback=i; iback>=0; iback--)
        {
          while (--jback >= 0)
            {
              if (TempArr[iback][jback] != 0) continue;
              if (sudoku[iback][jback]==nmax-1)
                ...
            }
            if (flag==1)
              break;
            jback = size;
        }
eleven
 
Posts: 1578
Joined: 10 February 2008

Re: My brute force code written in C got a hidden bug

Postby spk012 » Thu Dec 15, 2011 5:18 pm

dobrichev wrote:Use another solver to see whether your example puzzle has solution(s) at all.


This particular puzzle is from my mobile.. It should have a solution
spk012
 
Posts: 6
Joined: 15 November 2011

Re: My brute force code written in C got a hidden bug

Postby spk012 » Thu Dec 15, 2011 5:24 pm

daj95376 wrote:When the inner loop reaches jback=(-1), then you return to the outer loop and decrement iback. So far so good.
Now you return to the inner loop and set jback=(j) instead of jback=(nmax-1). Not good!


Thanks.. a lot! That's the real bug. I got it. but I should check whether its working or not.
I will post ASAP..
spk012
 
Posts: 6
Joined: 15 November 2011

Re: My brute force code written in C got a hidden bug

Postby spk012 » Thu Dec 15, 2011 5:42 pm

Oh my goodness!

Its all working! Thanks you guys.. for catching this. I really went mad because of it. :D
spk012
 
Posts: 6
Joined: 15 November 2011


Return to Software

cron