sudoku bactracking help needed

Question

I am currently working on sudoku solver that utilizes backtracking in order to solve the sudoku. I am almost finished but it crashes and I have no idea why,I tried searching the problems here related to sudoku backtracking but not much light was shed, as far as I could narrow down the problem, i know it is in my solveBoard function but still not sure, I also tried searching throught different sites and got some help but not enough. any help? thanks in advance

#include <iostream>
using namespace std;

bool findBlankLocation(int board[9][9], int&, int&);
bool inColumn(int [9][9], int, int);
bool inRow(int [9][9], int, int);
bool inBox(int [9][9], int, int, int);
bool blankLocation(int[9][9], int, int, int);
void printBoard(int [9][9]);
bool solveBoard(int [9][9]);

int main()
{
    int board[9][9] =  {{3, 0, 6, 5, 0, 8, 4, 0, 0},
                        {5, 2, 0, 0, 0, 0, 0, 0, 0},
                        {0, 8, 7, 0, 0, 0, 0, 3, 1},
                        {0, 0, 3, 0, 1, 0, 0, 8, 0},
                        {9, 0, 0, 8, 6, 3, 0, 0, 5},
                        {0, 5, 0, 0, 9, 0, 6, 0, 0},
                        {1, 3, 0, 0, 0, 0, 2, 5, 0},
                        {0, 0, 0, 0, 0, 0, 0, 7, 4},
                        {0, 0, 5, 2, 0, 6, 3, 0, 0}};



    if(solveBoard(board) == true)
        printBoard(board);
    else
        cout << "\n\n>>>>No existe solucion...";


    return 0;
 }

bool findBlankLocation(int board[9][9], int &row, int &col)
{
    for(int row=0; row<9;row++)
        for(int col=0; col<9;col++)
            if(board[row][col] == 0)
               return true;
    return false;
}

bool inColumn(int board[9][9], int col, int number)
{
    for(int row=0; row<9; row++)
        if(number == board[row][col])
            return true;
    return false;
}

bool inRow(int board [9][9], int row, int number)
{
    for(int col=0; col<9; col++)
        if(number == board[row][col])
            return true;
    return false;
}

bool inBox(int board[9][9], int startRow, int startColumn, int num)
{
    for(int row = 0; row<3; row++)
        for(int col = 0; col<3; col++)
            if(board[row+startRow][col+startColumn] == num)
                return true;
    return false;
}

void printBoard(int board[9][9])
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
            cout << "  " << board[i][j];
        cout << endl;
    }
}

bool blankLocation(int board[9][9], int row, int col, int num)
{
return !inColumn(board, col, num) && !inRow(board, row, num) 
&& !inBox( board,  row-row%3, col-col%3, num);
}

bool solveBoard(int board[9][9])
{
    int row, col;

    if (!findBlankLocation(board, row, col))
        return true;

    for (int num = 1; num <= 9; num++)
    {

        if (blankLocation(board, row, col, num))
        {
            board[row][col] = num;

            if (solveBoard(board))
                return true;

            board[row][col] = 0;
        }
     }

    return false;
}

Are you reading your compiler warnings? Look at your `findLinkLocation`. See the ambiguous usage of `row` and `col`? You use them as parameters, then declare totally different `row` and `col` for your loops. So what are you trying to do there? — PaulMcKenzie, Mar 22 '17 at 17:01
Given the problem with `findLinkLocation`, the `row` and `col` values are garbage, uninitialized values, and you're using them as if they have good values. — PaulMcKenzie, Mar 22 '17 at 17:13
Since the answer is already posted, might I ask why you didn't make this as a class? board looks totally like a member variable and your functions totally like methods. Also, I'd recommend that you provide parameter names with your function declarations, since that is not clear from the signature alone. And by the way, you shouldn't write "almost finished" when you ran it the first time - debugging can take *longer* than writing it initially. — Aziuth, Mar 22 '17 at 17:35
You need to be a little cleverer, even for a brute force algorithm. This method will generate an exponential number of invalid boards. You need to build a list of allowed numbers for each location and only try those. — Malcolm McLean, Mar 22 '17 at 17:37
@MalcolmMcLean This looks like a university assignment teaching recursion (Based on the fact that it looks almost identical to an assignment out of one of my textbooks), which would likely mean performance isn't an issue. — Trevor, Mar 22 '17 at 18:00

score 0 · Accepted Answer · answered Mar 22 '17 at 17:51

In

bool findBlankLocation(int board[9][9], int &row, int &col)
{
    for(int row=0; row<9;row++)
        for(int col=0; col<9;col++)
            if(board[row][col] == 0)
               return true;
    return false;
}

for(int row=0; row<9;row++) defines a new local variable named row that exists only within the for loop and hides the int &row parameter. This loop-local row is updated and lost on loop exit, leaving the parameter row unchanged. The calling function then attempts to use the uninitialized variable it expected to be updated inside findBlankLocation and triggers undefined behaviour.

GCC warns of this:

..\src\main.cpp:34:6: warning: unused parameter 'row' [-Wunused-parameter] bool findBlankLocation(int board[9][9], int &row, int &col)

So does Visual Studio if you turn the warnings up to level 4.

1>d:\jobs\consoleapplication1\consoleapplication1\consoleapplication1.cpp(36): warning C4457: declaration of 'row' hides function parameter 1> d:\jobs\consoleapplication1\consoleapplication1\consoleapplication1.cpp(34): note: see declaration of 'row' 1>d:\jobs\consoleapplication1\consoleapplication1\consoleapplication1.cpp(34): warning C4100: 'row': unreferenced formal parameter

The warnings are there to help you. Turn them on and pay heed.

The same bug affects col.

Solution

bool findBlankLocation(int board[9][9], int &row, int &col)
{
    for (row = 0; row < 9; row++) // now uses row parameter
        for (col = 0; col < 9; col++) // now uses col parameter
            if (board[row][col] == 0)
                return true;
    return false;
}

score -1 · Answer 2 · edited May 23 '17 at 12:25

It may be due to the following block:

int row, col;

if (!findBlankLocation(board, row, col))
    return true;

So the value's of row and col are undefined (Not the same as being initialized to zero). See here as to why their values are undefined.

UPDATE:

After further investigation, it looks like you are expecting findBlankLocation(board,row,col) to return row and col by reference. However, it is not.

bool findBlankLocation(int board[9][9], int &row, int &col)
{
  for(int row=0; row<9;row++)
    for(int col=0; col<9;col++)
      if(board[row][col] == 0)
        return true;
  return false;
}

The code above is using your local declaration of row and col for if(board[row][col] == 0). So once it finds the row and column, it returns true without passing the values by reference in the row and col parameters. Later, you use row and col in the solveBoard function, assuming they are filled with valid data, when they actually will not be. In order for findBlankLocation pass row and col by reference, it should look like the following:

bool findBlankLocation(int board[9][9], int &row, int &col)
{
  for(row = 0; row < 9; ++row)
    for(col = 0; col < 9; ++col)
      if(board[row][col] == 0)
        return true;
  return false;
}

This way you are not redefining row and col, and row and col will actually contain valid data.

_Row and col have their default constructors being called_ This is wrong. `int` doesn't have a constructor. — Algirdas Preidžius, Mar 22 '17 at 17:34

sudoku bactracking help needed

2 Answers2

Solution