37: Sudoku Solver

Problem

Problem ID: 37

Title: Sudoku Solver

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The ‘.’ character indicates empty cells.

Thoughts

This is your typical dfs + backtracking question. It could be further improved by using AC-3 which is typically taught in Artificial Intelligence classes.

Solution

Explanation

Utilise call stack to perform backtracking. If the current assignment is invalid, remove the current grid from the set of values in the row, col and block.

Implementation

class Solution {
public:
    int get_block_id(int i, int j) {
        int block_row = i/3;
        int block_col = j/3;
        return block_row*3 + block_col;
    }
    pair<int,int> next_grid(int i, int j) {
        if (j != 8) return {i, j+1};
        
        return {i+1, 0};
    }
    
    bool dfs_solve(int i, int j, vector<vector<char>>& board,  vector<unordered_set<int>>& rows_set, vector<unordered_set<int>>& cols_set, vector<unordered_set<int>>& blocks_set) {
        const auto& [v_i, v_j] = next_grid(i,j);
        if (i >= 9 || j >= 9) return true;
        if (board[i][j] != '.') {
            return dfs_solve(v_i, v_j, board, rows_set, cols_set, blocks_set);
        }
        int block_id = get_block_id(i,j);
        for (int num = 1; num <= 9; num++) {
            if (rows_set[i].count(num)) continue;
            if (cols_set[j].count(num)) continue;
            if (blocks_set[block_id].count(num)) continue;
            board[i][j] = num+'0';
            rows_set[i].insert(num);
            cols_set[j].insert(num);
            blocks_set[block_id].insert(num);
            if (i == 8 && j == 8) return true;
            if (dfs_solve(v_i, v_j, board, rows_set, cols_set, blocks_set)) return true;
            board[i][j] = '.';
            rows_set[i].erase( rows_set[i].find(num));
            cols_set[j].erase(cols_set[j].find(num));
            blocks_set[block_id].erase(blocks_set[block_id].find(num));
        }    
        return false;
    }
    
    void solveSudoku(vector<vector<char>>& board) {
        vector<unordered_set<int>> rows_set(9);
        vector<unordered_set<int>> cols_set(9);
        vector<unordered_set<int>> blocks_set(9);
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                rows_set[i].insert(board[i][j] - '0');
                cols_set[j].insert(board[i][j] - '0');
                blocks_set[get_block_id(i,j)].insert(board[i][j] - '0');
            }
        }
        dfs_solve(0,0,board,rows_set,cols_set,blocks_set);
    }
};