Leetcode 37 Solution

This article provides solution to leetcode question 37 (sudoku-solver)
Categories:
Tags:
Access this page by simply typing in "lcs 37" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/sudoku-solver

Thinking Process

This is a graph search problem. We are going to use our position and our board as our state (i, j, board). We start from (0, 0, original_board), and walk our ways from top left to the right bottom.

For each state (i, j, curr_board), we are going to check what number we can place on this position. Use each possible number to fill up the current position, and go to the next state (next_i, next_j, next_board). As long as we go get to the last position, we solve the sudoku. Otherwise, there is no solution.

Time & Space Complexity

Assuming the size of the board is N x N:

  • Time complexity: O(9^(N * N))
  • Space complexity: O(M * N)

Solution

class Solution {
public:
    bool isSudoku(vector<vector<char>>& board, int i, int j)
    {
        for (int k = 0; k < 9; k++)
        {
            if (board[i][j] == board[i][k] && j != k)
                return false;

            if (board[i][j] == board[k][j] && i != k)
                return false;
        }

        for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++)
        {
            for (int col = j / 3 * 3; col < j / 3 * 3 + 3; col++)
            {
                if (row == i && col == j)
                    continue;

                if (board[row][col] == board[i][j])
                    return false;
            }
        }

        return true;
    }

    bool solveSudoku(vector<vector<char>>& board, int i, int j) {
        if (i == 9)
            return true;
        else if (j == 9)
            return solveSudoku(board, i + 1, 0);
        else if (board[i][j] == '.')
        {
            for (int k = 1; k <= 9; k++)
            {
                board[i][j] = k + '0';
                if (isSudoku(board, i, j) && solveSudoku(board, i, j + 1))
                    return true;
            }
            board[i][j] = '.';
        }
        else
            return solveSudoku(board, i, j + 1);

        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        solveSudoku(board, 0, 0);
    }
};