Dark Mode On/Off
LAST UPDATED: JUNE 5, 2023

# Solve Sudoku Puzzle in C++, JAVA

Technology #java#cpp

In this tutorial, we will see how to solve a sudoku puzzle. So let's get started.

Here, we are given a 9*9 2D array grid and our main task is to fill all the empty cells with digits from 1-9 such that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.

Below is the pictorial representation of the same.

The above problem can be solved in two ways:

• Naive Approach: In this approach, we will generate all possible configurations of numbers from 1 to 9 to fill the empty cells. Then we will try every configuration one by one until the correct configuration is found. Once all the unassigned positions are filled, we will check if the matrix is valid or not. If valid then we will print the matrix else repeat the same process for different cases.
• BackTracking Approach: In this approach, we will assign the numbers one by one to the empty cells but before assigning we will check whether it is valid or not. After checking we will assign the number, and recursively check whether this assignment leads to a solution or not. If the assignment leads to a solution then print the matrix and if it doesn’t lead to a solution, then try the next number for the current empty cell.

Let us look at the below examples to understand the implementation of the above approaches.

## Program for Sudoku Puzzle in C++ and JAVA

### C++ Program to Solve Sudoku Problem

In this program, we will see how to solve sudoku in C++ using a simple approach.

### Algorithm:

1. Start.
2. Declare a matrix of N*N size where N=9.
3. First, enter the values of the sudoku and enter 0 for the unassigned cells.
4. Print the matrix first before solving.
5. Declare a user-defined function of boolean type.
6. If the 8th row and 9th column (0 indexed matrices) are reached, then return true to avoid backtracking.
7. If the column value becomes 9, move to the next row and column, and now start from 0.
8. Return false, if the same number is found in a similar column.
9. If the current position contains a value >0, then iterate for the next column.
10. Use a for loop to enter the values in the assigned cells.
11. Call another user-defined function to check whether the entered number is valid or not.
12. Assume a number for a certain position in the matrix.
13. If the assumed number and position are correct, then return true.
14. If the assumption is wrong, then remove the assigned number and proceed with a different value for the next assumption.
15. Else return false.
16. Display the result according to the boolean value received.
17. If true, then print the solved sudoku puzzle.
18. Else print that no solution exists.
19. Stop.

Let us look at the below example for a better understanding of the above algorithm.

``````//C++ Program to Solve Sudoku Problem
#include <iostream>
using namespace std;
#define N 9        // N is the size of the matrix i.e., N*N
//Function to print the matrix
void print(int arr[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout << arr[i][j] << " ";
cout << endl;
}
}
//Checks whether it will be legal to assign number to the given row, col
bool isValid(int puzzle[N][N], int row,	int col, int number)
{
//Check if we find the same number in the similar row , we return false
for (int x = 0; x <= 8; x++)
if (puzzle[row][x] == number)
return false;
//Check if we find the same number in the similar column, we return false
for (int x = 0; x <= 8; x++)
if (puzzle[x][col] == number)
return false;
/*Check if we find the same number in
the particular 3*3 matrix,
we return false*/
int sRow = row - row % 3,
sCol = col - col % 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (puzzle[i + sRow][j +
sCol] == number)
return false;
return true;
}
//Function to Solve the sudoku puzzle
bool solution(int puzzle[N][N], int row, int col)
{
/* If the 8th row and 9th column (0 indexed matrix) is reached,
then return true to avoid backtracking*/
if (row == N - 1 && col == N)
return true;
/*If column value becomes 9, move to next row and column
Now start from 0*/
if (col == N) {
row++;
col = 0;
}
/*If the current position contains value >0, then iterate for next column*/
if (puzzle[row][col] > 0)
return solution(puzzle, row, col + 1);
for (int number = 1; number <= N; number++)
{
//Check whether a number (1-9) can be placed in the given row,col
if (isValid(puzzle, row, col, number))
{
/* Let the number is present in the current(row,col)
position of the puzzle and let the assigned
number in that position is correct*/
puzzle[row][col] = number;
// Checking for next possibility with next column
if (solution(puzzle, row, col + 1))
return true;
}
/* If assumption is wrong, then remove the assigned number
Proceed with a different value for next assumption*/
puzzle[row][col] = 0;
}
return false;
}
// Driver Code
int main()
{
// Here 0 means unassigned cells
int puzzle[N][N] = { { 0, 7, 0, 0, 0, 0, 0, 0, 9 },
{ 5, 1, 0, 4, 2, 0, 6, 0, 0 },
{ 0, 8, 0, 3, 0, 0, 7, 0, 0 },
{ 0, 0, 8, 0, 0, 1, 3, 7, 0 },
{ 0, 2, 3, 0, 8, 0, 0, 4, 0 },
{ 4, 0, 0, 9, 0, 0, 1, 0, 0 },
{ 9, 6, 2, 8, 0, 0, 0, 3, 0 },
{ 0, 0, 0, 0, 1, 0, 4, 0, 0 },
{ 7, 0, 0, 2, 0, 3, 0, 9, 6 } };
cout << "Before Solving " << endl;
print(puzzle);
cout << "" << endl;
cout << "After Solving " << endl;
if (solution(puzzle, 0, 0))
print(puzzle);
else
cout << "No solution exists " << endl;

return 0;
}``````

Before Solving
0 7 0 0 0 0 0 0 9
5 1 0 4 2 0 6 0 0
0 8 0 3 0 0 7 0 0
0 0 8 0 0 1 3 7 0
0 2 3 0 8 0 0 4 0
4 0 0 9 0 0 1 0 0
9 6 2 8 0 0 0 3 0
0 0 0 0 1 0 4 0 0
7 0 0 2 0 3 0 9 6

After Solving
3 7 4 1 6 8 2 5 9
5 1 9 4 2 7 6 8 3
2 8 6 3 9 5 7 1 4
6 9 8 5 4 1 3 7 2
1 2 3 7 8 6 9 4 5
4 5 7 9 3 2 1 6 8
9 6 2 8 7 4 5 3 1
8 3 5 6 1 9 4 2 7
7 4 1 2 5 3 8 9 6

### Java Program to Solve Sudoku Problem

In this program, we will see how to solve sudoku in Java using a backtracking approach.

### Algorithm:

1. Start.
2. Declare a matrix of N*N size where N=9.
3. First, enter the values of the sudoku and enter 0 for the unassigned cells.
4. Print the matrix first before solving.
5. Declare a user-defined function of boolean type.
6. Declare two variables rows and columns, and initialize them to -1.
7. Check after assigning the current index of the puzzle is valid or not.
8. If any number has a frequency greater than 1 return false else return true.
9. Now, check for the unassigned location.
10. If present then assigns a number from 1 to 9, check if assigning the number to the current index is valid or not.
11. If valid then recursively call the function for all valid cases from 0 to 9.
12. If any recursive call returns true, end the loop and return true.
13. If no recursive call returns true then return false.
14. If there is no unassigned location then return true.
15. Display the result according to the boolean value received.
16. If true, then print the solved sudoku puzzle.
17. Else print that no solution exists.
18. Stop.

Let us look at the below example for a better understanding of the above algorithm.

``````/*Java Program to solve Sudoku problem using Backtracking*/
public class Main
{
public static boolean isValid(int[][] puzzle,int row, int col,int number)
{
// Row has the unique
for (int d = 0; d < puzzle.length; d++)
{

/* If the number we are trying to
that row, then return false;*/
if (puzzle[row][d] == number) {
return false;
}
}
// Column has the unique numberbers
for (int r = 0; r < puzzle.length; r++)
{
/* If the number we are trying to
that column, then return false;*/
if (puzzle[r][col] == number)
{
return false;
}
}

//Corresponding square has unique number
int sqrt = (int)Math.sqrt(puzzle.length);
int bRow = row - row % sqrt;
int bCol = col - col % sqrt;
for (int r = bRow;
r < bRow + sqrt; r++)
{
for (int d = bCol;
d < bCol + sqrt; d++)
{
if (puzzle[r][d] == number)
{
return false;
}
}
}
// if there is no clash, it's safe
return true;
}
public static boolean solution(int[][] puzzle, int n)
{
int row = -1;
int col = -1;
boolean isEmpty = true;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (puzzle[i][j] == 0)
{
row = i;
col = j;
isEmpty = false;
break;
}
}
if (!isEmpty) {
break;
}
}
// No empty space left
if (isEmpty)
{
return true;
}
// Else backtrack for each-row
for (int number = 1; number <= n; number++)
{
if (isValid(puzzle, row, col, number))
{
puzzle[row][col] = number;
if (solution(puzzle, n))
{
// print(puzzle, n);
return true;
}
else
{
// replace it
puzzle[row][col] = 0;
}
}
}
return false;
}
//To Print the Sudoku
public static void printSudoku(int[][] puzzle, int N)
{
for (int r = 0; r < N; r++)
{
for (int d = 0; d < N; d++)
{
System.out.print(puzzle[r][d]);
System.out.print(" ");
}
System.out.print("\n");

if ((r + 1) % (int)Math.sqrt(N) == 0)
{
System.out.print("");
}
}
}

// Driver Code
public static void main(String args[])
{
//Here 0 represents the unassigned value
int[][] puzzle = new int[][] {
{ 3, 0, 5, 4, 0, 2, 0, 6, 0 },
{ 4, 9, 0, 7, 6, 0, 1, 0, 8 },
{ 6, 0, 0, 1, 0, 3, 2, 4, 5 },
{ 0, 0, 3, 9, 0, 0, 5, 8, 0 },
{ 9, 6, 0, 0, 5, 8, 7, 0, 3 },
{ 0, 8, 1, 3, 0, 4, 0, 9, 2 },
{ 0, 5, 0, 6, 0, 1, 4, 0, 0 },
{ 2, 0, 0, 5, 4, 9, 0, 7, 0 },
{ 1, 4, 9, 0, 0, 7, 3, 0, 6 }
};
int N = puzzle.length;
System.out.println("Before Solving");
printSudoku(puzzle, N);
System.out.println("");
System.out.println("After Solving");
if (solution(puzzle, N))
{
printSudoku(puzzle, N);
}
else
{
System.out.println("No solution exists");
}
}
}
``````

Before Solving
0 7 0 0 0 0 0 0 9
5 1 0 4 2 0 6 0 0
0 8 0 3 0 0 7 0 0
0 0 8 0 0 1 3 7 0
0 2 3 0 8 0 0 4 0
4 0 0 9 0 0 1 0 0
9 6 2 8 0 0 0 3 0
0 0 0 0 1 0 4 0 0
7 0 0 2 0 3 0 9 6

After Solving
3 7 4 1 6 8 2 5 9
5 1 9 4 2 7 6 8 3
2 8 6 3 9 5 7 1 4
6 9 8 5 4 1 3 7 2
1 2 3 7 8 6 9 4 5
4 5 7 9 3 2 1 6 8
9 6 2 8 7 4 5 3 1
8 3 5 6 1 9 4 2 7
7 4 1 2 5 3 8 9 6

### C++ Program to Solve Sudoku Problem

In this program, we will see how to solve sudoku in C++ using the Backtracking approach.

### Algorithm:

1. Start.
2. Declare a matrix of N*N size where N=9.
3. First, enter the values of the sudoku and enter 0 for the unassigned cells.
4. Print the matrix first before solving.
5. Declare a user-defined function of boolean type.
6. Declare two variables rows and columns.
7. Now search for a location.
8. If an unassigned entry is found, then set the reference parameters row, col to the location that is unassigned, and return true.
9. If no unassigned entries remain, false is returned.
10. Use a for loop to add numbers to the unassigned cells.
11. Check whether it is legal to add a number.
12. Assign the value temporarily.
13. If the value assigned is true, then return true.
14. Else try again with a different value.
15. Return false to trigger backtracking.
16. Display the result according to the boolean value received.
17. If true, then print the solved sudoku puzzle.
18. Else print that no solution exists.
19. Stop.

Let us look at the below example for a better understanding of the above algorithm.

``````/*C++ to solve Sudoku problem using BackTracking Approach*/
#include <bits/stdc++.h>
using namespace std;

#define UNASSIGNED 0
#define N 9  // N is the size of a Sudoku puzzle i.e., NxN

bool searchLocation(int puzzle[N][N], int& row, int& col);
bool isValid(int puzzle[N][N], int row, int col, int number);

bool SolveSudoku(int puzzle[N][N])
{
int row, col;
// If there is no unassigned location, then return true.
if (!searchLocation(puzzle, row, col))
return true;

for (int number = 1; number <= 9; number++)
{
// Check whether it is legal to add a number
if (isValid(puzzle, row, col, number))
{
//Assign the value temporarily
puzzle[row][col] = number;
// Return, if success
if (SolveSudoku(puzzle))
return true;
//If not success, then try again
puzzle[row][col] = UNASSIGNED;
}
}
// Trigger backtracking
return false;
}

/*If unassigned entry is found, then set the reference
parameters row, col to the location that is unassigned,
and return true.
If no unassigned entries remain, false is returned. */
bool searchLocation(int puzzle[N][N], int& row, int& col)
{
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (puzzle[row][col] == UNASSIGNED)
return true;
return false;
}

/* Return a boolean if the assigned value in
the specified row matches the given number. */
bool uRow(int puzzle[N][N], int row, int number)
{
for (int col = 0; col < N; col++)
if (puzzle[row][col] == number)
return true;
return false;
}

/* Return a boolean if the assigned value
in the specified column matches the given number.*/
bool uCol(int puzzle[N][N], int col, int number)
{
for (int row = 0; row < N; row++)
if (puzzle[row][col] == number)
return true;
return false;
}

/* Returns a boolean if the assigned value in the box
matches the given number. */
bool uBox(int puzzle[N][N], int bsRow,
int bsCol, int number)
{
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (puzzle[row + bsRow][col + bsCol] == number)
return true;
return false;
}

/* Returns a boolean if it is be legal
to assign a number to the given row, col location. */
bool isValid(int puzzle[N][N], int row, int col, int number)
{
/* Check if 'number' is not already placed in
current row, current column
and current 3x3 box */
return !uRow(puzzle, row, number)
&& !uCol(puzzle, col, number)
&& !uBox(puzzle, row - row % 3,
col - col % 3, number)
&& puzzle[row][col] == UNASSIGNED;
}

/* Function to print the Sudoku puzzle */
void printSudoku(int puzzle[N][N])
{
for (int row = 0; row < N; row++)
{
for (int col = 0; col < N; col++)
cout << puzzle[row][col] << " ";
cout << endl;
}
}

// Driver Code
int main()
{
// 0 means unassigned cells
int puzzle[N][N] = { { 1, 0, 6, 0, 0, 2, 3, 0, 0 },
{ 0, 5, 0, 0, 0, 6, 0, 9, 1 },
{ 0, 0, 9, 5, 0, 1, 4, 6, 2 },
{ 0, 3, 7, 9, 0, 5, 0, 0, 0 },
{ 5, 8, 1, 0, 2, 7, 9, 0, 0 },
{ 0, 0, 0, 4, 0, 8, 1, 5, 7 },
{ 0, 0, 0, 2, 6, 0, 5, 4, 0 },
{ 0, 0, 4, 1, 5, 0, 6, 0, 9 },
{ 9, 0, 0, 8, 7, 4, 2, 1, 0 } };
cout << "Before Solving " << endl;
printSudoku(puzzle);
cout << "" << endl;
cout << "After Solving " << endl;
if (SolveSudoku(puzzle) == true)
printSudoku(puzzle);
else
cout << "No solution exists";

return 0;
}``````

Before Solving
1 0 6 0 0 2 3 0 0
0 5 0 0 0 6 0 9 1
0 0 9 5 0 1 4 6 2
0 3 7 9 0 5 0 0 0
5 8 1 0 2 7 9 0 0
0 0 0 4 0 8 1 5 7
0 0 0 2 6 0 5 4 0
0 0 4 1 5 0 6 0 9
9 0 0 8 7 4 2 1 0

After Solving
1 4 6 7 9 2 3 8 5
2 5 8 3 4 6 7 9 1
3 7 9 5 8 1 4 6 2
4 3 7 9 1 5 8 2 6
5 8 1 6 2 7 9 3 4
6 9 2 4 3 8 1 5 7
7 1 3 2 6 9 5 4 8
8 2 4 1 5 3 6 7 9
9 6 5 8 7 4 2 1 3

## Conclusion:

Solving Sudoku puzzles using C++ or Java is a thrilling endeavor that combines programming skills with logical reasoning. With the algorithms and techniques explored in this article, you are now equipped to tackle even the most complex Sudoku grids programmatically.

From backtracking to constraint propagation, these approaches provide powerful tools for finding solutions efficiently. So, challenge yourself and put your programming prowess to the test by solving Sudoku puzzles in C++ or Java. As you master the art of Sudoku solving, you'll not only enhance your programming skills but also experience the joy of cracking puzzles with the help of code.

### 1. What is Sudoku?

Sudoku is a logic-based number placement puzzle consisting of a 9x9 grid divided into nine 3x3 sub-grids. The objective is to fill in the empty cells with numbers from 1 to 9, ensuring that each row, column, and sub-grid contains all the digits exactly once.

### 2. How can I solve Sudoku puzzles using C++ or Java?

Solving Sudoku puzzles programmatically involves implementing algorithms such as backtracking or constraint satisfaction. These algorithms recursively explore possible solutions, making logical deductions and backtracking when necessary.

### 3. What is backtracking in Sudoku solving?

Backtracking is a common technique used in Sudoku-solving algorithms. It involves systematically trying different possibilities, keeping track of the choices made, and undoing them if they lead to an inconsistent state. This allows the program to explore multiple paths until a valid solution is found.

### 4. Can I use existing libraries or frameworks to solve Sudoku puzzles?

Yes, both C++ and Java offer various libraries and frameworks that can assist in solving Sudoku puzzles. For example, in C++, you can utilize the "bitset" or "vector" data structures, while Java provides libraries such as "java.util.BitSet" or "javax.constraints".

### 5. Are there any optimization techniques for solving Sudoku puzzles faster?

Yes, there are several optimization techniques you can employ to speed up the Sudoku-solving process. These include constraint propagation, naked singles identification, hidden singles identification, and implementing heuristics like minimum remaining values or forward checking.

## You may also like:

Want to learn coding?
Try our new interactive courses.
Over 20,000+ students enrolled.
I am the founder of Studytonight & Fullstack developer (MERN). I like writing content about ReactJS, MERN, JavaScript, Docker, Linux, PHP, Go lang, Cloud, Web development, and general Tech related content. I have 10 years of diverse experience in software development.