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

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

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：
5 Easy Ways On How To Build An Authority Website
How to Protect Your WordPress Site From Hackers
Top 10 Relationship Blogs With the Best Pieces of Advice in 2020
How to Construct Binary Search Tree from Preorder Traversal in P
Dynamic Programming Algorithm to Compute the Block Sum in a Matr
Smallest Multiple Algorithm using Bruteforce or GCD/LCM
How many different ways can £2 be made using any number of coins
Compute Factorial Digit Sum: Find the sum of the digits in the n
Compute the Maximum Integer Right Triangles Solutions
Power Digit Sum: What is the sum of the digits of the number 2^1

Comment list

Comment add: Name：　Check：