37. Sudoku Solver

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

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.

2. Each of the digits 1-9 must occur exactly once in each column.

3. 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.

bool isValid(vector<vector<char> >& board, int r, int c) {
    for (int i = 0; i < 9; ++i) {
        // row check
        if (i != c && board[r][i] == board[r][c]) return false;
        // col check
        if (i != r && board[i][c] == board[r][c]) return false;
        // 3x3 box check
        int boxRow = 3 * (r / 3) + (i / 3), boxCol = 3 * (c / 3) + (i % 3);
        if ((boxRow != r || boxCol != c) && board[boxRow][boxCol] == board[r][c]) return false;
    }
    return true;
}
bool helper(vector<vector<char> >& board, int i, int j) {
    if (i == 9) return true;
    if (j == 9) return helper(board, i + 1, 0);
    if (board[i][j] == '.') {
        for (char c = '1'; c <= '9'; ++c) {
            board[i][j] = c;
            if (isValid(board, i, j) && helper(board, i, j + 1)) return true;
            board[i][j] = '.';
        }
    } else {
        return helper(board, i, j + 1);
    }
    return false;
}
void solveSudoku(vector<vector<char>>& board) { // time: O(9^(# of empty slots)); space: O(# of empty slots)
    if (board.size() != 9 || board[0].size() != 9) return;
    helper(board, 0, 0);
}

bool isValid(vector<vector<char> >& board, int r, int c) {
    for (int i = 0; i < 9; ++i) {
        // row check
        if (i != c && board[r][i] == board[r][c]) return false;
        // col check
        if (i != r && board[i][c] == board[r][c]) return false;
        // 3x3 box check
        int boxRow = 3 * (r / 3) + (i / 3), boxCol = 3 * (c / 3) + (i % 3);
        if ((boxRow != r || boxCol != c) && board[boxRow][boxCol] == board[r][c]) return false;
    }
    return true;
}
bool helper(vector<vector<char> >& board) {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] != '.') continue;
            for (char k = '1'; k <= '9'; ++k) {
                board[i][j] = k;
                if (isValid(board, i, j) && helper(board)) return true;
                board[i][j] = '.';
            }
            return false;
        }
    }
    return true;
}
void solveSudoku(vector<vector<char>>& board) { // time: O(9^(# of empty slots)); space: O(# of empty slots)
    if (board.size() != 9 || board[0].size() != 9) return;
    helper(board);
}

void helper(vector<vector<char> >& board, vector<vector<bool> >& row, vector<vector<bool> >& col,
            vector<vector<bool> >& box, int r, int c, bool& flag) {
    if (r == 9) {
        flag = true;
        return;
    }
    if (board[r][c] == '.') {
        for (int i = 1; i <= 9; ++i) {
            if (row[r][i] || col[c][i] || box[3 * (r / 3) + (c / 3)][i]) continue;
            row[r][i] = col[c][i] = box[3 * (r / 3) + (c / 3)][i] = true;
            board[r][c] = i + '0';
            if (c == 8) {
                helper(board, row, col, box, r + 1, 0, flag);
            } else {
                helper(board, row, col, box, r, c + 1, flag);
            }
            if (flag == true) return;
            row[r][i] = col[c][i] = box[3 * (r / 3) + (c / 3)][i] = false;
            board[r][c] = '.';
        }
    } else {
        if (c == 8) {
            helper(board, row, col, box, r + 1, 0, flag);
        } else {
            helper(board, row, col, box, r, c + 1, flag);
        }
    }
}
void solveSudoku(vector<vector<char>>& board) {
    vector<vector<bool> > row(9, vector<bool>(10, false));
    vector<vector<bool> > col(9, vector<bool>(10, false));
    vector<vector<bool> > box(9, vector<bool>(10, false));
    // build cache tables first
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] != '.') {
                int temp = board[i][j] - '0';
                row[i][temp] = col[j][temp] = box[3 * (i / 3) + (j / 3)][temp] = true;
            }
        }
    }
    bool flag = false;
    // backtracking
    helper(board, row, col, box, 0, 0, flag);
}