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

  • 时间：2020-09-07 12:13:31
  • 分类：网络文摘
  • 阅读：119 次

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 Depth First Search (Backtracking) Algorithm to Solve a Sudoku Game algorithms c / c++ DFS

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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) —

推荐阅读：
Learn to Achieve Your Goals with 5 Secrets of Great Bloggers　 What is Cornerstone Content And Why It’s Important　 How to Attract Female Readership For Your Blog　 Double your traffic with White Hat SEO techniques　 Blogging As Therapy: True Life Stories Of Victims And How They C　 3 Reasons to Geek Out on Your Blog　 The Terminal Software Engineer Level　 Facebook Interview Tips and Guidance　 Book Review: Python for Kids, for Dummies　 Find the Least Number Sums of Perfect Squares　
评论列表
添加评论