Solve Sudoku Puzzle in C++, JAVA

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
			 place is already present in
			 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
			 place is already present in
			 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.

Frequently Asked Questions(FAQs)

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:

• How to convert ZonedDateTime to Date in Java?

• HashMap Performance Improvements in JAVA 8 using TREEIFY_THRESHOLD

• Finding Next Greater Element for every Element in an Array

• Program to Reverse a Linked List in C++