37. Sudoku Solver

• Difficulty: Hard

• Topics: Hash Table, Backtracking

• Similar Questions:

  • Valid Sudoku

  • Unique Paths III

Problem:

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.

Solutions:

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        int n = 9;
        vector<vector<bool>> rows (n, vector<bool> (n, false));
        vector<vector<bool>> cols (n, vector<bool> (n, false));
        vector<vector<vector<bool>>> blocks (3, vector<vector<bool>>(3, vector<bool> (n, false)));

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == '.') continue;
                rows[i][board[i][j] - '1'] = true;
                cols[j][board[i][j] - '1'] = true;
                blocks[i/3][j/3][board[i][j] - '1'] = true;
            }
        }

        helper(board, n, 0, 0, rows, cols, blocks);
    }

    bool helper(vector<vector<char>>& board, int n, int row, int col, vector<vector<bool>>& rows, vector<vector<bool>>& cols, vector<vector<vector<bool>>>& blocks) {
        for (int i = row; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] != '.') continue;
                for (int val = 1; val <= 9; ++val) {
                    if (isValid(rows, cols, blocks, i, j, val)) {
                        board[i][j] = '0' + val;
                        rows[i][val-1] = true;
                        cols[j][val-1] = true;
                        blocks[i/3][j/3][val-1] = true;
                        if (helper(board, n, i, j, rows, cols, blocks))    return true;
                        blocks[i/3][j/3][val-1] = false;
                        cols[j][val-1] = false;
                        rows[i][val-1] = false;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }

    bool isValid(vector<vector<bool>>& rows, vector<vector<bool>>& cols, vector<vector<vector<bool>>>& blocks, int row, int col, int val) {
        return rows[row][val-1] == false && cols[col][val-1] == false && blocks[row/3][col/3][val-1] == false;
    } 
};