HelloKenLee

Leetcode 37. Sudoku Solver 解题报告

Posted on By KenLee

题目信息

题目: 37. Sudoku Solver
难度: Hard
正确率: 29.4%
问题描述:

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

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

问题分析

  该题的意思是给你一个数独,让你填空,填满且满足数独的性质即可。他保证给出的数独有且只有唯一解。(数独的性质是 行, 列, 和九宫格内1~9的数字出现且仅出现一次。)

解题思路

  一个典型回溯搜索题目,朴素思路往空白的格子里面不停填1~9,填一个, check一下有没有冲突,如果没有冲突再填下一个,有冲突就往前回溯。

  我在数据结构上做了一点小小的优化,因为行,列,九宫格里面有且仅有9位,分别为1~9,因此我用了一个int来存储1行或者1列或者1个九宫格,这样我就能通过位运算判断是否冲突了。接着我就从左往右,从上往下搜素就可以了。结果出来还挺快的。

结果分析

  • 时间复杂度: $ O(9^N) $ 假设有N个空格,每个有9种可能,最坏的时间复杂度为$ O(9^N) $
  • 空间复杂度: $ O(1) $ 常数额外空间
  • 通过时间: 6 ms
  • 击败: 74.25%的提交

源代码

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        memset(rowHashTable, 0, 9 * sizeof(int));
        memset(colHashTable, 0, 9 * sizeof(int));
        memset(blockHashTable, 0, 9 * sizeof(int));
        solved = false;
        // 初始化哈系表
        for(int r = 0; r < 9; ++r){
            for(int c = 0; c < 9; ++c){
                int mask = 1 << (board[r][c] - '0');
                int b = (r / 3) * 3 + (c / 3);
                rowHashTable[r] |= mask;
                colHashTable[c] |= mask;
                blockHashTable[b] |=mask;
            }
        }
        search(0, 0, board);
        return;
    }
private:
    bool solved;
    int rowHashTable[9], colHashTable[9], blockHashTable[9];
    void search(int r, int c, vector<vector<char>>& board){
        if(solved)
            return;
        if(c >= 9){
            search(r+1, 0, board);
            return;
        }
        if(r >= 9){
            solved = true;
            return;
        }
        if(board[r][c] != '.'){
            search(r, c+1, board);
            return;
        }
        int b = (r / 3) * 3 + (c / 3);
        for(int i=1; i <= 9; ++i){
            int mask = 1 << i;
            if(!(mask & rowHashTable[r]) && !(mask & colHashTable[c]) && !(mask & blockHashTable[b])){
                //如果在board[r][c]放入i不会引起冲突
                board[r][c] = '0' + i;
                rowHashTable[r] |= mask;
                colHashTable[c] |= mask;
                blockHashTable[b] |=mask;
                search(r, c+1, board);
                if(solved){
                    return;
                }
                //复原,回溯
                rowHashTable[r] ^= mask;
                colHashTable[c] ^= mask;
                blockHashTable[b] ^=mask;
                board[r][c] = '.';
            }
        }
    }
};