Solve Sudoku using Backtracking

[spsrijan]

I'm trying to write a program that solve a given sudoku puzzle after pressing enter. But the program terminated after pressing enter without doing anything. I think there may be an error in line 119 in function void sudokuSolver(int board[9][9]). Can someone help me out, please?

  #include <iostream>
using namespace std;

void Pause()
{
    cout<<"Press Enter to solve...";
    cin.get();
}

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

void printBoard(int board[9][9])
{
    cout<<"Given Problem:\n\n";
    cout<<" =========================\n";
    for (int row=0; row<9; row++)
    {
        if(row==3 || row==6)
            cout<<" -------------------------\n";

        for (int col=0; col<9; col++)
        {
            if (col==0)
                cout<<"|";
            cout<<" "<<(board[row][col]);


            if(col==2 || col==5 || col==8)
                cout<<" | ";
        }

        cout<<endl;
    }
    cout<<" =========================\n\n\n";
}

int * possibleEntries(int board[9][9], int i, int j)
{
    int possibilityArray[9] = {0};

    for (int col=0; col<9; col++)
    {
        if (board[i][col] != 0)
            possibilityArray[board[i][col]] = 1;
    }

    for (int row=0; row<9; row++)
    {
        if (board[row][j]!=0)
            possibilityArray[board[row][j]] = 1;
    }

    int k=0;
    int l=0;
    if (i>=0 && i<=2)
        k=0;
    else if
    (i>=3 && i<=5)
        k=3;
    else
        k=6;

    if (j>=0 && j<=2)
        l=0;
    else if
    (j>=3 && j<=5)
        l=3;
    else
        l=6;

    for (int row=k; row<k+3; row++)
            for (int col=l; col<l+3; col++)
                if (board[row][col] != 0)
                    possibilityArray[board[row][col]] = 1;

    for (int i=0; i<10; i++)
        if (possibilityArray[i] == 0)
            possibilityArray[i] = i;
        else
            possibilityArray[i] = 0;

    return possibilityArray;
}


void sudokuSolver(int board[9][9]) {

    int i=0;
    int j=0;

    int *possiblities;
    if (isFull(board)){
        printBoard(board);
        cout<< "Sudoku Solved Successfully!";
        return;
    }
    else
    {
        for (int row=0; row<9; row++) {
            for (int col=0; col<9; col++) {
                if (board[row][col] == 0) {
                    i = row;
                    j = col;
                    break;
                } }

        }
    possiblities = possibleEntries(board, i, j);

        for (int x=0; x<10; x++)
            if (possiblities[x] != 0)
                board[i][j] = possiblities[x];
                sudokuSolver(board);
        board[i][j] = 0;
}
}

int main()
{
    int SudokuBoard[9][9] = {0};
    SudokuBoard[0][4] = 9;
    SudokuBoard[0][6] = 3;
    SudokuBoard[1][1] = 2;
    SudokuBoard[1][3] = 6;
    SudokuBoard[1][5] = 1;
    SudokuBoard[1][6] = 5;
    SudokuBoard[1][7] = 9;
    SudokuBoard[2][0] = 3;
    SudokuBoard[2][3] = 5;
    SudokuBoard[2][5] = 8;
    SudokuBoard[2][7] = 2;
    SudokuBoard[2][8] = 4;
    SudokuBoard[3][1] = 9;
    SudokuBoard[3][6] = 4;
    SudokuBoard[3][7] = 8;
    SudokuBoard[4][0] = 6;
    SudokuBoard[4][3] = 2;
    SudokuBoard[4][5] = 9;
    SudokuBoard[4][8] = 1;
    SudokuBoard[5][1] = 5;
    SudokuBoard[5][2] = 2;
    SudokuBoard[5][7] = 3;
    SudokuBoard[6][0] = 9;
    SudokuBoard[6][1] = 7;
    SudokuBoard[6][3] = 1;
    SudokuBoard[6][3] = 1;
    SudokuBoard[6][5] = 5;
    SudokuBoard[6][8] = 3;
    SudokuBoard[7][1] = 3;
    SudokuBoard[7][2] = 8;
    SudokuBoard[7][3] = 7;
    SudokuBoard[7][5] = 4;
    SudokuBoard[7][7] = 1;
    SudokuBoard[8][2] = 5;
    SudokuBoard[8][4] = 8;
    printBoard(SudokuBoard);
    Pause();
    sudokuSolver(SudokuBoard);
}

[andywestken]

I think there may be an error in line 119 ...

The problem here is that you are returning the address of a temporary variable. In the code below I fixed with the hack of making possibilityArray a static, but the right solution is to pass the address of a buffer for you values or switch to a vector.

What compiler are you using? GCC picked up the problem with:
warning: address of local variable 'possibilityArray' returned [-Wreturn-local-addr]

It also picked up:
warning: control reaches end of non-void function [-Wreturn-type]

As you are returning true too early in isFull(), if I read the intention of your code corrrectly.

And I tweaked the nested for-loop starting at line 110 so it uses goto to jump out of both loops, rather than just the inner loop. (I assumed you wanted to find the first empty cell, going by the setting of i and j. Was I right?)

And added some debug (trace) output.

Andy

PS You need to be vary wary of functions like bool isFull(int board[9][9]) as the compiler ignores the first array index, so this looks like bool isFull(int board[][9]) to the compiler and will accept any N x 9 array.

#include <iostream>
#include <algorithm> // for fill_n
using namespace std;

#define TRACE

void Pause()
{
    cout<<"Press Enter to solve...";
    cin.get();
}

bool isFull(int board[9][9])
{
#ifdef TRACE
    cout << "isFull()\n";
#endif
    for(int row=0; row<9; row++)
    {
        for (int col=0; col<9; col++)
        {
            if (board[row][col] == 0)
            {
#ifdef TRACE
                cout << "- returns false;\n";
#endif
                return false;
            }
        }
        // warning: control reaches end of non-void function [-Wreturn-type]
        //return true;
    }
#ifdef TRACE
    cout << "- returns true;\n";
#endif
    return true;
}

void printBoard(int board[9][9])
{
    cout<<"Given Problem:\n\n";
    cout<<" =========================\n";
    for (int row=0; row<9; row++)
    {
        if(row==3 || row==6)
            cout<<" -------------------------\n";

        for (int col=0; col<9; col++)
        {
            if (col==0)
                cout<<"|";
            cout<<" "<<(board[row][col]);


            if(col==2 || col==5 || col==8)
                cout<<" | ";
        }

        cout<<endl;
    }
    cout<<" =========================\n\n\n";
}

int * possibleEntries(int board[9][9], int i, int j)
{
#ifdef TRACE
    cout << "possibleEntries()\n";
#endif
    // warning: address of local variable 'possibilityArray' returned [-Wreturn-local-addr]
    //int possibilityArray[9] = {0};
    // made static (needs to be zeroed each time possibleEntries called)
    static int possibilityArray[9] = {0};
    fill_n(possibilityArray, 9, 0);

    for (int col=0; col<9; col++)
    {
        if (board[i][col] != 0)
            possibilityArray[board[i][col]] = 1;
    }

    for (int row=0; row<9; row++)
    {
        if (board[row][j]!=0)
            possibilityArray[board[row][j]] = 1;
    }

    int k=0;
    int l=0;
    if (i>=0 && i<=2)
        k=0;
    else if
    (i>=3 && i<=5)
        k=3;
    else
        k=6;

    if (j>=0 && j<=2)
        l=0;
    else if
    (j>=3 && j<=5)
        l=3;
    else
        l=6;

    for (int row=k; row<k+3; row++)
            for (int col=l; col<l+3; col++)
                if (board[row][col] != 0)
                    possibilityArray[board[row][col]] = 1;

    for (int i=0; i<10; i++)
        if (possibilityArray[i] == 0)
            possibilityArray[i] = i;
        else
            possibilityArray[i] = 0;

#ifdef TRACE
    cout << "- returns possibilityArray[] = {";
    for (int i=0; i<9; i++)
    {
        cout << ((0 == i) ? "" : ", ") << possibilityArray[i];
    }
    cout << "}\n";
#endif
    return possibilityArray;
}


void sudokuSolver(int board[9][9]) {
#ifdef TRACE
    cout << "sudokuSolver()\n";
#endif

    int i=0;
    int j=0;

    int *possiblities;
    if (isFull(board)){
        printBoard(board);
        cout<< "Sudoku Solved Successfully!";
        return;
    }
    else
    {
        for (int row=0; row<9; row++) {
            for (int col=0; col<9; col++) {
                if (board[row][col] == 0) {
                    i = row;
                    j = col;
                    //changed to goto to jump out of both loops
                    //break;
                    goto label_break_from_loop;
                }
            }
        }

label_break_from_loop:
        possiblities = possibleEntries(board, i, j);

        for (int x=0; x<10; x++)
            if (possiblities[x] != 0)
                board[i][j] = possiblities[x];
                sudokuSolver(board);
        board[i][j] = 0;
    }
}

int main()
{
    int SudokuBoard[9][9] = {0};
    SudokuBoard[0][4] = 9;
    SudokuBoard[0][6] = 3;
    SudokuBoard[1][1] = 2;
    SudokuBoard[1][3] = 6;
    SudokuBoard[1][5] = 1;
    SudokuBoard[1][6] = 5;
    SudokuBoard[1][7] = 9;
    SudokuBoard[2][0] = 3;
    SudokuBoard[2][3] = 5;
    SudokuBoard[2][5] = 8;
    SudokuBoard[2][7] = 2;
    SudokuBoard[2][8] = 4;
    SudokuBoard[3][1] = 9;
    SudokuBoard[3][6] = 4;
    SudokuBoard[3][7] = 8;
    SudokuBoard[4][0] = 6;
    SudokuBoard[4][3] = 2;
    SudokuBoard[4][5] = 9;
    SudokuBoard[4][8] = 1;
    SudokuBoard[5][1] = 5;
    SudokuBoard[5][2] = 2;
    SudokuBoard[5][7] = 3;
    SudokuBoard[6][0] = 9;
    SudokuBoard[6][1] = 7;
    SudokuBoard[6][3] = 1;
    SudokuBoard[6][3] = 1;
    SudokuBoard[6][5] = 5;
    SudokuBoard[6][8] = 3;
    SudokuBoard[7][1] = 3;
    SudokuBoard[7][2] = 8;
    SudokuBoard[7][3] = 7;
    SudokuBoard[7][5] = 4;
    SudokuBoard[7][7] = 1;
    SudokuBoard[8][2] = 5;
    SudokuBoard[8][4] = 8;
    printBoard(SudokuBoard);
    //kill pause so can use app in console with >>
    //Pause();
    sudokuSolver(SudokuBoard);
}

Running app in console using

C:\Test>test >> temp.txt

I got a 62642 line text file

Given Problem:

 =========================
| 0 0 0 |  0 9 0 |  3 0 0 | 
| 0 2 0 |  6 0 1 |  5 9 0 | 
| 3 0 0 |  5 0 8 |  0 2 4 | 
 -------------------------
| 0 9 0 |  0 0 0 |  4 8 0 | 
| 6 0 0 |  2 0 9 |  0 0 1 | 
| 0 5 2 |  0 0 0 |  0 3 0 | 
 -------------------------
| 9 7 0 |  1 0 5 |  0 0 3 | 
| 0 3 8 |  7 0 4 |  0 1 0 | 
| 0 0 5 |  0 8 0 |  0 0 0 | 
 =========================


sudokuSolver()
isFull()
- returns false;
possibleEntries()
- returns possibilityArray[] = {0, 1, 0, 0, 4, 5, 0, 7, 8}
sudokuSolver()
isFull()
- returns false;
possibleEntries()
- returns possibilityArray[] = {0, 1, 0, 0, 4, 0, 6, 0, 0}
sudokuSolver()
isFull()
- returns false;
possibleEntries()
- returns possibilityArray[] = {0, 1, 0, 0, 4, 0, 0, 7, 0}
sudokuSolver()
isFull()
- returns false;
possibleEntries()
- returns possibilityArray[] = {0, 0, 0, 0, 4, 0, 0, 0, 0}
sudokuSolver()
isFull()
- returns false;
possibleEntries()
- returns possibilityArray[] = {0, 0, 2, 0, 0, 0, 0, 0, 0}
sudokuSolver()
isFull()
- returns false;
possibleEntries()
- returns possibilityArray[] = {0, 0, 0, 0, 0, 0, 0, 0, 0}
sudokuSolver()
isFull()
- returns false;
<snip>

Lots of lines later!

<snip>
sudokuSolver()
isFull()
- returns false;
possibleEntries()
- returns possibilityArray[] = {0, 0, 0, 0, 0, 0, 0, 0, 0}
sudokuSolver()
isFull()
- returns false;
possibleEntries()
- returns possibilityArray[] = {0, 0, 0, 0, 0, 0, 0, 0, 0}
sudokuSolver()
isFull()
- returns false;
possibleEntries()
- returns possibilityArray[] = {

The truncated output line makes me thing the stack blew up at this point.