Sudoku Solver

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.

A sudoku puzzle...

...and its solution numbers marked in red.

---------------------------- thinking --------------------------------
https://leetcode.com/discuss/21452/sharing-my-2ms-c-solution-with-comments-and-explanations

--------------------------- codes -------------------------------------
class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        bool hrz[9][9] = {false};
        bool vrt[9][9] = {false};
        bool dia[9][9] = {false};
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] != '.') {
                    int num = board[row][col] - '1';
                    int sub_row = row/3;
                    int sub_col = col/3;
                    int sub_id = sub_row * 3 + sub_col;                  
                    hrz[num][row] = true;
                    vrt[num][col] = true;
                    dia[num][sub_id] = true;
                }
            }
        }
        sudokuHelper(board, hrz, vrt, dia, 0);
    }
    bool sudokuHelper(vector<vector<char>> &board, bool hrz[][9], bool vrt[][9], bool dia[][9], int n) {
        if (n >= 81) {
            return true;
        }
        int row = n/9;
        int col = n%9;
        int sub_row = row/3;
        int sub_col = col/3;
        int sub_id = sub_row * 3 + sub_col;
        if (board[row][col] == '.') {
            for (int i = 1; i <= 9; i++) {
                if (hrz[i-1][row] || vrt[i-1][col] || dia[i-1][sub_id]) {
                    continue;
                } else {
                    hrz[i-1][row] = true;
                    vrt[i-1][col] = true;
                    dia[i-1][sub_id] = true;
                    board[row][col] = i + '0';
                    if (sudokuHelper(board, hrz, vrt, dia, n+1)) {
                        return true;
                    } else {
                        hrz[i-1][row] = false;
                        vrt[i-1][col] = false;
                        dia[i-1][sub_id] = false;
                        board[row][col] = '.';
                    }
                }
            }
            //bug here!!! if you don't return false, the DFS method will go wrong!!
            return false;
        } else {
            sudokuHelper(board, hrz, vrt, dia, n+1);          
        }
    }
};