Depth First Search (Backtracking) Algorithm to Solve a Sudoku Ga

Time：2020-09-07 12:13:31
Class：Weblog
Read：20

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3×3 sub-boxes of the grid.
Empty cells are indicated by the character ‘.’.

sudoku-solver

…and its solution numbers marked in red.

Note:
The given board contain only digits 1-9 and the character ‘.’.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9×9.

Sudoku Solver using Backtracking Algorithm in DFS

The Sudoku can be solved by pure bruteforce algorithm (the complexity is $tex_1ccc4b757f39ae215055692cad987c4c Depth First Search (Backtracking) Algorithm to Solve a Sudoku Game algorithms c / c++ DFS$ ) . However, the complexity is enormous and can’t be solved practically.

By using the 3 rules to abandon search branches and backtracking when solution is invalid – this reduce the complexity to roughly $tex_67ceddd3e325fbaf138d8112e7e65607 Depth First Search (Backtracking) Algorithm to Solve a Sudoku Game algorithms c / c++ DFS$ for a standard backtracking algorithm (There are 9! possibilities for 9×9 box and there are 9 of them in permutation).

We can use three sets – rows, columns, and boxes to remember the digits that have been placed in 9 rows, 9 columns and 9 boxes.

For Depth First Search Algorithm, we try to place next valid number and recursively into next position, and we need to reset to its previous state.

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        for (int r = 0; r < 9; ++ r) {
            for (int c = 0; c < 9; ++ c) {
                if (board[r][c] != '.') {
                    int x = board[r][c] - '0';
                    cols[c].insert(x);
                    rows[r].insert(x);
                    box[r/3][c/3].insert(x);
                }
            }
        }
        dfs(board, 0, 0);
    }
    
private:
    unordered_set<int> cols[9];
    unordered_set<int> rows[9];
    unordered_set<int> box[3][3];
    
    bool dfs(vector<vector<char>>& board, int r, int c) {
        if (c == 9) {
            r ++;
            c = 0;
        }
        if (r == 9) {
            return true;
        }       
        if (board[r][c] != '.') {
            return dfs(board, r, c + 1);
        }
        for (int i = 1; i <= 9; ++ i) {
            if (check(i, r, c)) {
                board[r][c] = (char)(48 + i);
                cols[c].insert(i);
                rows[r].insert(i);
                box[r/3][c/3].insert(i);
                if (dfs(board, r, c + 1)) {                  
                    return true;
                }
                board[r][c] = '.';
                cols[c].erase(i);
                rows[r].erase(i);       
                box[r/3][c/3].erase(i);
            }
        }
        return false;
    }
    
    bool check(int x, int r, int c) {
        return (cols[c].count(x) == 0) && (rows[r].count(x) == 0) 
            && (box[r/3][c/3].count(x) == 0);
    }
};

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        for (int r = 0; r < 9; ++ r) {
            for (int c = 0; c < 9; ++ c) {
                if (board[r][c] != '.') {
                    int x = board[r][c] - '0';
                    cols[c].insert(x);
                    rows[r].insert(x);
                    box[r/3][c/3].insert(x);
                }
            }
        }
        dfs(board, 0, 0);
    }
    
private:
    unordered_set<int> cols[9];
    unordered_set<int> rows[9];
    unordered_set<int> box[3][3];
    
    bool dfs(vector<vector<char>>& board, int r, int c) {
        if (c == 9) {
            r ++;
            c = 0;
        }
        if (r == 9) {
            return true;
        }       
        if (board[r][c] != '.') {
            return dfs(board, r, c + 1);
        }
        for (int i = 1; i <= 9; ++ i) {
            if (check(i, r, c)) {
                board[r][c] = (char)(48 + i);
                cols[c].insert(i);
                rows[r].insert(i);
                box[r/3][c/3].insert(i);
                if (dfs(board, r, c + 1)) {                  
                    return true;
                }
                board[r][c] = '.';
                cols[c].erase(i);
                rows[r].erase(i);       
                box[r/3][c/3].erase(i);
            }
        }
        return false;
    }
    
    bool check(int x, int r, int c) {
        return (cols[c].count(x) == 0) && (rows[r].count(x) == 0) 
            && (box[r/3][c/3].count(x) == 0);
    }
};

To check if a Sudoku is valid, we can use this: How to Check Valid Sudoku in C/C++?

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
Two Rectangles Overlap Detection Algorithm in C++
C++ Coding Reference: next_permutation() and prev_permutation()
C++ Coding Reference: count and count_if
How to Reorder Data in Log Files using the Custom Sorting Algori
C++ Coding Reference: std::accumulate() and examples
C++ Coding Reference: sort() and stable_sort()
The C++ Function using STL to Check Duplicate Elements/Character
How to Find Positive Integer Solution for a Given Equation using
How to Implement the instanceof in Javascript?
Azerbaijani Blogger, Mehman Huseynov Sentenced To Prison For All

Comment list

Comment add: Name：　Check：