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

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

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

推荐阅读：
7 Online Marketing Tools You Need to Master in 2016　 How to Compute the Min Cost of Climbing Stairs via Dynamic Progr　 The Algorithm to Make Words Bold in HTML　 The O(N) Increasing Triplet Subsequence Algorithm　 How to Compute the Greatest Common Divisor of Strings?　 How to Design a Tic-Tac-Toe Game?　 The Facebook Initial Coding Interview Experience　 Facebook Onsite Interview Preparation Part 2: Coding Questions　 The Process Killing Algorithms using Depth First Search or Bread　 Breadth-First Search Algorithm to Solve Puzzle (Rotting Oranges)　
评论列表
添加评论