36. Valid Sudoku

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

逐个判断，复杂度$$O(n^2)$$

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row = board.size();
        int col = board[0].size();

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(board[i][j] == '.')
                    continue;

                //所在行
                for(int k= 0; k < col; k++){
                    if(k != j && board[i][k] == board[i][j])
                        return false;
                }

                //所在列
                for(int m = 0; m < row; m++){
                    if(m != i && board[i][j] == board[m][j])
                        return false;
                }

                //所在正方形
                for(int m = i/3 * 3 ; m < (i/3 + 1)*3; m++){
                    for(int n = j/3 *3;  n< (j/3 + 1)*3; n++){
                        if(m != i && n != j && board[m][n] == board[i][j])
                            return false;
                    }
                }

            }
        }
        return true;
    }
};

用hash做

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //used1[m][n]表示在m行中数字(n+1)已经使用
        int used1[9][9] = {0};
        //used2[m][n]表示在m列中数字(n + 1)已经使用
        int used2[9][9] = {0};
        ////used[m][n]表示所在小正方形是否有n+1
        int used3[9][9] = {0};

        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){

                    int num = board[i][j] - '0' - 1;
                    int 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;
    }
};

37. Sudoku Solver

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.