The New Sudoku Players' Forum

[spk012]

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!

[dobrichev]

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

[spk012]

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.

[simes]

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.

[spk012]

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.

[m_b_metcalf]

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

[daj95376]

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

[eleven]

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;
        }


[spk012]

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]

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]

Oh my goodness!

Its all working! Thanks you guys.. for catching this. I really went mad because of it.