Sudoku Solver in C programming
Introduction
Sudoku is probably one of the most well-known logic games that have reached their peak of fame in recent years. It is done with the help of a nine by nine board, where each number from 1 to 9 should be placed only once not only within the row, but also within the column and the 3 by 3 subsquares. Sudoku is often started along with some of the cells being already filled and the main goal is to fill in the remaining cells by using the Sudoku rules. The rules of Sudoku are very easy to comprehend, yet playing it is actually very difficult, especially for a professional. Sudoku puzzles can be solved in many ways, different strategies or algorithms have been invented in the recent years by researchers and people who consider Sudoku as their passion. These algorithms use various approaches; for example, back tracking, constraint propagation, dancing link, etc. , in order to solve a particular puzzle. Thus, currently, there is no clearly defined effective algorithm to solve Sudoku problem. In this blog we are going to discuss and implement the use of backtracking algorithm in solving Sudoku puzzles. Backtracking can be described as a subconscious systematic process of trial and error in searching through all the possible states of a given search space, gradually adding a solution to it while discarding any state that leads to an invalid configuration at any given time. This makes it an effective technique in solving Sudoku puzzles particularly where the constraints are closely intertwined in such a way that any placement has to be decided with a lot of caution. It will be important for us to have a closer look at the backtracking algorithm, including how this algorithm was implemented using C language and why C language is used to solve this type of Sudoku puzzles. By undertaking a detailed description and illustration of the backtracking algorithm and its application in Sudoku, the authors intend to equip the readers with a variety of skills that enable them to implement and employ the backtracking algorithm to solve Sudoku puzzles effectively.
Methodology
In our proposed approach, we utilize four types of algorithms to solve Sudoku puzzles:
- Backtracking
- Backtracking + Hashmap
- Constraint Propagation Algorithm
- Dancing Links/Algorithm X
(1) Backtracking
The backtracking method uses for solving a Sudoku by directly checking each empty cell of the puzzle and then examining each candidate digit. A candidate is placed in the cell if it obeys the Sudoku rules without any infractions of the model. The next empty cell is then taken into consideration, thus if it finds a suitable candidate that satisfies the above formulated Sudoku rules, then it is inserted in that cell. In case none is found, the backtracking approach moves up to the previous cells and find the candidate which has to be in a cell in order to adhere to the Sudoku standards. The backtracking method is certain to develop a solution for each and every credible Sudoku problem but is slightly longer as compared to other techniques.
(2) Backtracking + Hashmap
A refinement to the backtracking technique is via the use of a hashmap that increases the rate of searching. First and foremost, each value of the array is placed into the hashmap, taking into account the array’s given index. Therefore, when the backtracking + hashmap optimization technique is being utilized if for some reason the algorithm tries to insert a sequence of strings that already exists in the hashmap it signifies an inconsistent environment. In such cases what it does is the algorithm backtracks to the last consistent state and attempts to proceed with another path in the search space.
(3) Constraint Propagation Algorithm
Constraint propagation is one of the processes in which the constraints of the problem to be solved are applied in order to remove some of the candidate values of variables. In Sudoku this means applying propagation of constraints and applying the rules of the puzzle to remove candidate values. For example, if a certain cell of the given area has the set value equal to 5, the other cells locating in the same row, column and 3×3 square cannot have the set value equal to 5. Engaging these constraints many times and deleting candidate values with them can help subject the search space to simplify the process of reaching the solution of the puzzle. This technique can be used together with what is known as backtracking technique to solve Sudoku puzzles effectively.
(4) Dancing Links/Algorithm X
Dancing Links is an effective and employed algorithm associated with solving of exact cover issues, for example, Sudoku. Dancing links was announced by Donald Knuth in his paper known as ‘Dancing Links’ in the year 2000. The roles of the data structure used in the algorithm, the doubly linked circular list: The matrix of the exact cover problem. The list associated with a matrix contains the node for each rows and columns; any cell containing 1 in the matrix has a node in the associated row and column lists. The basic step of the algorithm goes on with the choice of a column having a minimum number of ones in it, which is then pivoted to cover the header node. Next, if the value for that row in the i-th column is a 1, then the algorithm proceeds to cover all other values in the other columns which were set to 1 in the current row. Thus, the process persists until all columns are placed on each row, which will indicate that the problem has been solved, or if it is impossible to place all the gas columns on the row and no solution is found. If at any point it gets stuck, the algorithm returns to the prior decision point and goes in a different direction. This is done by “exposing/revoking” the concealed columns/rows and proceeding with the next best possible column selection. Despite, Dancing Links works efficiently, and in the worst-case scenario, it can provide all the solutions to a certain problem immediately.
The Algorithm
According to the specifics of the analyzing procedure it is assumed that its result should provide the basic understanding of all the procedures currently in progress and emphasize the elements of the system under design. To describe the process flow of this study with a major focus on backtracking algorithm. The circle nodes depict the data flow, while the rectangles illustrates the steps of the existent algorithm that can be implemented. They depict the actual working of the backtracking algorithm right from the beginning to until the final step making it easy to understand. The backtracking algorithm’s diagram is depicted in figure below.
Coding In C
I will code these algorithms in C programming to demonstrate how they work and obtain the results.
1. Defining Constants and Hashmaps
We define N as 9 for the 9x9 grid and declare three hashmaps to track used numbers in rows, columns, and sub-grids.
#define N 9
bool rows[N][N+1];
bool cols[N][N+1];
bool boxes[N][N+1];2. Function to Print the Sudoku Grid
This function prints the grid in a readable format.
void printGrid(int grid[N][N]) {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
printf(“%2d”, grid[row][col]);}
printf(“\n”);}}3. Function to Initialize Hashmaps
This function initializes the hashmaps based on the initial grid configuration.
void initializeHashmaps(int grid[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N+1; j++) {
rows[i][j] = false;
cols[i][j] = false;
boxes[i][j] = false;}}
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (grid[row][col] != 0) {
int num = grid[row][col];
rows[row][num] = true;
cols[col][num] = true;
boxes[(row/3)*3 + col/3][num] = true;}}}}4. Function to Check if a Number is Safe to Place
This function checks if placing a number in a specific cell is valid by consulting the hashmaps.
bool isSafe(int row, int col, int num) {
return !rows[row][num] && !cols[col][num] && !boxes[(row/3)*3 + col/3][num];}5. Function to Find an Empty Location
This function finds the next empty cell in the grid.
bool findEmptyLocation(int grid[N][N], int *row, int *col) {
for (*row = 0; *row < N; (*row)++) {
for (*col = 0; *col < N; (*col)++) {
if (grid[*row][*col] == 0) {
return true;}}}
return false;}6. Function to Solve the Sudoku Using Optimized Backtracking
This is the core function that implements the optimized backtracking algorithm.
bool solveSudoku(int grid[N][N]) {
int row, col;
if (!findEmptyLocation(grid, &row, &col)) {
return true;}
for (int num = 1; num <= 9; num++) {
if (isSafe(row, col, num)) {
grid[row][col] = num;
rows[row][num] = true;
cols[col][num] = true;
boxes[(row/3)*3 + col/3][num] = true;
if (solveSudoku(grid)) {
return true;}
grid[row][col] = 0;
rows[row][num] = false;
cols[col][num] = false;
boxes[(row/3)*3 + col/3][num] = false;}}
return false;}7. Main Function to Test the Sudoku Solver
In the main function, we initialize a sample Sudoku grid, call the necessary functions, and print the result.
int main() {
int grid[N][N] = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
initializeHashmaps(grid);
if (solveSudoku(grid)) {
printGrid(grid);} else {
printf("No solution exists");}
return 0;}The implementation of the optimized Sudoku solver in C is designed to use the backtracking algorithm with rows, cols, and box hashmaps to indicate used numbers in rows, cols, and 3x3 sub-grids, which limits the number of checks need for placements; these hashmaps are set to False initially and updated by numbers in the initial grid, therefore before placing a number, the algorithm can know if the placement is safe by using the hash
References:
1. Wikipedia. (2021). Sudoku solving algorithms.
2. Hira, S., Bhagwatkar, N., Agrawal, K., & Loya, N. (2023). Sudoku Solver: A Comparative Study of Different Algorithms and Image Processing Techniques.
3. Herimanto, D., Sitorus, P., & Zamzami, E. M. (2020). An Implementation of Backtracking Algorithm for Solving a Sudoku-Puzzle Based on Android.
4. Singh, V., Sharma, V., & Bachchas, V. (2023). Sudoku Solving Using Quantum Computer
