37. Sudoku Solver

Leetcode Hash Table Backtracking

题目

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 3x3 sub-boxes of the grid. Empty cells are indicated by the character ..

A sudoku puzzle...

...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 9x9.

思路

class Solution {
public:

    // 判断数独是否有效
    bool isValidSudoku(vector<vector<char>> &board)
    {
        int used1[9][9] = {0}, used2[9][9] = {0}, used3[9][9] = {0};

        for(int i = 0; i < board.size(); ++ i)
            for(int j = 0; j < board[i].size(); ++ j)
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3;
                    if(used1[i][num] || used2[j][num] || used3[k][num]){
                        return false;
                    }
                    used1[i][num] = used2[j][num] = used3[k][num] = 1;
                }
        return true;
    }


    // 判断Sudoku是否已经填满，如果不填满返回一个空缺位置
    vector<int> isfull(vector<vector<char>> &board){
        vector<int> h;
        int n = board.size();
        for (int i=0; i< n; i++){
            for (int j=0; j<n; j++){
                if (board[i][j]=='.'){
                    h.push_back(i);
                    h.push_back(j);
                    return h;
                }
            }
        }
        return h;

    }

    bool solveSudokuHelper(vector<vector<char>>& board){

        vector<int> h = isfull(board);
        if (!h.size()){
            // base case
            return true;
        } else{
            int column = h[1];
            int row = h[0];
            for (int i=1; i<10 ; i++){
                board[row][column] = i + '0';
                if (isValidSudoku(board)){
                    //choose and explore
                    bool solved = solveSudokuHelper(board);
                    if (solved){
                        // 只需要1个解即可
                        return true;
                    }

                    //unchoose
                    board[row][column] = '.';
                }
                else{
                    board[row][column] = '.';
                }
            }

        }

        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        solveSudokuHelper(board);
    }
};