# Leetcode 37 Solution

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);
}
};
``````