Recursive Sudoku Solver- Segmentation Fault (C++)

Question

I'm attempting to make a sudoku solver for the sake of learning to use recursion. I seem to have gotten most of the code to work well together, but when I run the program, I get a windows error telling me that the program has stopped working. A debug indicates a segmentation fault, and I saw elsewhere that this can be caused by too many recursions. I know this is a brute-force method, but again, I'm more worried about getting it to work than speed. What can I do to fix this to a working level?

struct Playing_grid {
    //Value of cell
    int number;
    //wether the number was a clue or not
    bool fixed;
}
grid[9][9];

    void recursiveTest(int row, int column, int testing)
    {
    //first, check to make sure it's not fixed
        if(grid[row][column].fixed == false)
        {
            if((checkRow(testing, row) | checkColumn(testing, column) | checkBox(testing,boxNumber(row,column)) | (testing > 9)) == 0)
            {
                grid[row][column].number = testing;
                moveForward(row,column,testing);
                recursiveTest(row, column, testing);
            }
            else if(testing < 9)
            {
                testing ++;
                recursiveTest(row, column, testing);
            }
            else if(testing == 9)
            {
                while(testing == 9)
               {
                moveBack(row,column,testing);
                while(grid[row][column].fixed == true)
                {
                    {
                        moveBack(row,column,test);
                    }
                }
                testing = grid[row][column].number;
                recursiveTest(row,column,testing);
               }
            }
        }
        else
        {
            moveForward(row,column,testing);
            recursiveTest(row,column,testing);
        }
    }



     void moveForward(int& row, int& column, int& test)
{
    if(column < 8)
    {
        column ++;
    }
    else if((column == 8) & (row != 8))
    {
        column = 0;
        row ++;
    }
    else if((column == 8) & (row == 8))
    {
        finishProgram();
    }
    test = 1;
}

    void moveBack(int& row, int& column, int& test)
    {
        grid[row][column].number = 0;
        if(column > 0)
            {
                column --;
            }
        else if((column == 0) & (row > -1))
            {
                column = 8;
                row --;
            }
        else
        {
            cout << "This puzzle is unsolveable!" << endl;
        }
        test++;
    }

I tried to include all the relevant pieces. I essentially create a 9x9 matrix, and by this point it is filled with 81 values, where empty slots are written as 0. After confirming the test value is valid in the row, column and box, it fills in that value and moves onto the next space. Whenever it runs to 9 and has no possible values, it returns to the previous value and runs through values for that one.

So as to not overwrite known values, the recursive function checks each time that the value of the grid[row][column].fixed is false.

I'd appreciate any insight as to cleaning this up, condensing it, etc. Thanks in advance!

Edit: To exit the recursive loop, when the function is called to move forward, if it has reached the last cell, it completes (saves + outputs) the solution. The code has been adjusted to reflect this.

What did your debugger tell you about your segmentation fault? — Neil
I'm not familiar with C (which I assume this is), but quickly glancing over this as pseudocode your algorithm seems flawed. I can't see a way through recursiveTest that doesn't itself call recursiveTest, which means it will recurse infinitely. You need to let some of the calls finish so they can come off the stack. As a general rule, I'd expect moveBack only to be called directly after a cell to recursiveTest; not repeatedly in a while loop. — Braiba
All I get about the segmentation fault is a "Program received signal SIGSEGV, Segmentation fault" message. I don't know how to get more information about the message. I forgot to implement one part into the moveForward loop- when it reaches the last space in the grid (8,8) and it's valid, I have it save and output the completed puzzle. Also, the while loop checks the previous cell for a fixed value, and continues to check until it reaches a value that is unknown. — Benjamin Goodberry

Braiba Braiba · Accepted Answer · 2012-07-25T00:18:21

I'd normally try to fix your code, but I think in this case it's fundamentally flawed and you need to go back to the drawing board.

As a general rule, the pseudocode for a recursive function like this would be

For each possible (immediate) move
  Perform that move
  Check for win state, if so store/output it and return true.
  Call this function. If it returns true then a win state has been found so return true 
  Otherwise unperform the move
Having tried every move without finding a win state, return false.

Recursive Sudoku Solver- Segmentation Fault (C++)

1 Answers