'Sudoku Recursive Backtrack Aid in C

I am relatively new to coding and recursion has been a thorn in my side. I need help with implementing backtrack recursion.

Here is my sample code (Assume all helper functions work correctly [and they do])

void solve_sudoku(char sudoku[9][9])
{
    if (contains_empty_cell(sudoku) == 1)
    {
        for (int y = 0; y < 9; y++)
        {
            for (int x = 0; x < 9; x++)
            {
                if (sudoku[y][x] == 0)
                {
                    for (int i = 1; i <= 9; i++)
                    {
                        sudoku[y][x] = i;
                        if (is_valid_column(sudoku, y, x) == 1 &&
                            is_valid_row(sudoku, y, x) == 1 &&
                            is_valid_sub_box(sudoku, y, x) == 1)
                        {
                            solve_sudoku(sudoku);
                        }
                    }
                    if (sudoku[y][x] == 9)
                    {
                        sudoku[y][x] = 0;
                        return;
                    }
                }
            }
        }
    }
}
calgorithmrecursionbacktrackingsudoku


Solution 1:[1]

I think you are close. The main problem is how you are handling a solution. It seems you tried to handle it with if (sudoku[y][x] == 9). But that's not correct.

Option 1 is to exit once a solution is found. solve_sudoku() returns a value to indicate so. The solution will be the end result after the outermost call of solve_sudoku():

int solve_sudoku(char sudoku[9][9])
{
    if (contains_empty_cell(sudoku) != 0)
    {
        return 1; // sudoku completely filled in, i.e. solution found
    }

    for (int y = 0; y < 9; y++)
    {
        for (int x = 0; x < 9; x++)
        {
            if (sudoku[y][x] == 0)
            {
                for (int i = 1; i <= 9; i++)
                {
                    sudoku[y][x] = i;
                    if (is_valid_column(sudoku, y, x) == 1 &&
                        is_valid_row(sudoku, y, x) == 1 &&
                        is_valid_sub_box(sudoku, y, x) == 1)
                    {
                        if (solve_sudoku(sudoku) == 1)
                        {
                            return 1; // exit if solution found
                        }
                    }
                }
                // restore empty cell
                sudoku[y][x] = 0;
            }
        }
    }

    return 0;
}

A Sudoku can have multiple solutions. So option 2 is to print each found solution and then continue:

void solve_sudoku(char sudoku[9][9])
{
    if (contains_empty_cell(sudoku) == 0)
    {
        // Sudoku completely filled in, print solution
        print_solution(sudoku);
        return;
    }

    for (int y = 0; y < 9; y++)
    {
        for (int x = 0; x < 9; x++)
        {
            if (sudoku[y][x] == 0)
            {
                for (int i = 1; i <= 9; i++)
                {
                    sudoku[y][x] = i;
                    if (is_valid_column(sudoku, y, x) == 1 &&
                        is_valid_row(sudoku, y, x) == 1 &&
                        is_valid_sub_box(sudoku, y, x) == 1)
                    {
                        solve_sudoku(sudoku);
                    }
                    
                }

                // restore empty cell
                sudoku[y][x] = 0;
            }
        }
    }
}

I haven't tried it. So it might not be a complete solution.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Codo

Related Questions