## Introduction

In this article, we will discuss the **Sudoku Solver** problem with the help of various examples and explanations. The sudoku solver problem is considered a challenging problem and can be of two variations. One variation can be when we have been given unsolved sudoku, and we are required to solve it by filling the blank spaces with the correct number. The other variation is when we have been given unsolved sudoku, and we are supposed to check whether the given numbers are positioned correctly or not. We shall discuss the first variation in this article. The second variation can be found here:

Also see, Data Structures

Sudoku is a 9x9 puzzle where the board is divided into nine rows and nine columns. It is further divided into nine small grids of 3x3 size each. An element in sudoku is present exclusively in a row or a column, or a grid.

The solution code provided in this article uses the concepts of the Backtracking Algorithm. Readers without prior knowledge might refer to this article- Recursion and Backtracking Algorithm With Practice Problems - CN Blogs before proceeding forward.

Also see, Backtracking and Recursion

## Problem Statement

Write a program to solve the Sudoku puzzle by filling the empty cells on the given board.

Your sudoku solution must satisfy 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.

**Example and Explanation**

Let us use an example to understand better.

Let us consider an input sudoku board that is a vector of vectors of characters. The input is given as:

INPUT

{'3','.','6','5', '.', '8', '4', '.', '.'},

{'5','2','.','.', '.', '.', '.', '.', '.'},

{'.','8','7','.', '.', '.', '.', '3', '1'},

{'.','.','3','.', '1', '.', '.', '8', '.'},

{'9','.','.','8', '6', '3', '.', '.', '5'},

{'.','5','.','.', '9', '.', '6', '.', '.'},

{'1','3','.','.', '.', '.', '2', '5', '.'},

{'.','.','.','.', '.', '.', '.', '7', '4'},

{'.','.','5','2', '.', '6', '3', '.', '.'}

The sudoku formed will look like this:

(source: __Sudoku Solver Visualizer__)

The input is a 9x9 vector of vectors of characters where '.' denotes a blank box. Wherever we encounter a dot, we are supposed to fill a number such that it is unique in its row, column and grid.

On solving the above sudoku, our output must be-

OUTPUT

3 1 6 5 7 8 4 9 2

5 2 9 1 3 4 7 6 8

4 8 7 6 2 9 5 3 1

2 6 3 4 1 5 9 8 7

9 7 4 8 6 3 1 2 5

8 5 1 7 9 2 6 4 3

1 3 8 9 4 7 2 5 6

6 9 2 3 5 1 8 7 4

7 4 5 2 8 6 3 1 9

For better visualization, the output will look like this:

Recommended: Try the Problem Yourself Before Moving onto the Solution