# Sudoku Solver

This page explains Java solution to problem `Sudoku Solver` using `Backtracking`.

## Problem Statement

Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character `.`.

Example 1:

Input: A Sudoku Puzzle Output: It's Solution number marked in Red ## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class SudokuSolver {
public void solveSudoku(char[][] board) {
solve(board);
}

private boolean solve(char[][] board) {
for(int row = 0; row < 9; row++) {
for(int col = 0; col < 9; col++) {
if(board[row][col] == '.') {
for(char num = '1'; num <= '9'; num++) {
if(isValid(board, row, col, num)) {
board[row][col] = num;
if(solve(board)) return true;
else board[row][col] = '.';
}
}
return false;
}
}
}
return true;
}

private boolean isValid(char[][] board, int row, int col, char num) {
int blkRow = (row / 3) * 3, blkCol = (col / 3) * 3;
for(int i = 0; i < 9; i++) {
if(board[i][col] == num) return false;
if(board[row][i] == num) return false;
if(board[blkRow + i / 3][blkCol + i % 3] == num) return false;
}
return true;
}
}
``````

## Time Complexity

O(9!)9
For single Row there are 9 possibilities for first cell
8 possibilities for second cell
7 possibilities for third cell and so ....
So total there are 9! operations to fill in one row

There are 9 Rows in Sudoku, so total number of operations will be 9!9

## Space Complexity

O(9 * 9) For storing 9 * 9 Grid