Recursive backtracking Sudoku solver

Question

I'm currently learning C, mainly with examples from Project Euler. (<- check it out if you don't already know it!)

Out of some sources on the internet and some self write code, I made a C program which should solve 50 Sudokus. I've defined an array like [number of sudoku][row][column]. The following is the solving function.

int solve(int puzzles[50][9][9], int sudokuNumber, int row, int col){
int nextNum = 1;

if (row == 8){
    return 1;
}

if (puzzles[sudokuNumber][row][col]){
    if (col == 8){
        if (solve(puzzles, sudokuNumber, row+1, 0))
            return 1;
    }
    else {
        if (solve(puzzles, sudokuNumber, row, col+1))
            return 1;
    }
    return 0;
}

for (; nextNum <= 9; nextNum++){
    if (isValid(sudokuNumber, row, col, nextNum)){
        puzzles[sudokuNumber][row][col] = nextNum;
        if (col == 8){
            if (solve(puzzles, sudokuNumber, row+1, 0))
                return 1;
        }
        else {
            if (solve(puzzles, sudokuNumber, row, col+1))
                return 1;
        }
    }
}
}

Which unfortunately doesn't really output anything and at this point and is quite frustrating... Am I making an obvious dumb mistake? isValid returns 1 if valid, this function is correct.

Would really appreciate if someone would have a look at this.

why are you expecting output? there is nothing in your code that outputs anything — Chris Turner
This is Project Euler problem 96 which should be solved by your own efforts and research. BTW why do you load all 50 puzzles into a 3D array when they can be read and solved one at a time from the text file given? You'll need a solution stack, and loading all 50 at once makes it unnecessarily complicated. — Weather Vane
Try making a print sudoku function. This is really time consuming for us to understand and then point out an error. Be specific in terms of your problem. You can't go to a doc and say Hey somethings wrong with but I don't know what! Please check me up. — Pushan Gupta
if (row == 8){ return 1; } don't you think this is not enough? The last row won't be ever solved. — Ajay Brahmakshatriya
How does isValid work when it does not take the current state of the board (puzzles)? isValid(sudokuNumber, row, col, nextNum) — avmohan

avmohan avmohan · Accepted Answer · 2017-07-12T18:58:18

First of all, I think the function signatures need to be fixed. They should take one board and not a list of boards. Iterate on the list outside of the solve function (in fact there is no need to load all the boards into memory, you only need to sum the numbers formed by (0,0) (0,1), (0,2) position from all boards)
void solve(int board[][], int row, int col)-> Try solving starting at board[row][col]
bool is_valid(int board[][], int row, int col, int d) -> is it ok to fill board[row][col] with d

Second, the boundary condition seems to be not correct. Assuming row & col take on values 0 through 8, it should be row==9 and col==9 instead of 8.

Also, I think you'll have to skip the already filled cells. if(board[row][col] != 0) solve(board, row, col+1)

Also, depending on how is_valid is implemented, you'll have to make sure you're un-filling properly. In the problem, unfilled rows are represented as 0s. So before you backtrack after failing to fill board[row][col] with all numbers from 1 to 9, make sure to set board[row][col] back to 0.

Recursive backtracking Sudoku solver

1 Answers