Horje
Sudoku in C

Sudoku is a popular puzzle game where the goal is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids contain all of the digits from 1 to 9. In this article, we will learn how we can solve Sudoku puzzles using C programming language.

Example:

Input:
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 } };

Output:
5 3 4 6 7 8 9 1 2 
6 7 2 1 9 5 3 4 8 
1 9 8 3 4 2 5 6 7 
8 5 9 7 6 1 4 2 3 
4 2 6 8 5 3 7 9 1 
7 1 3 9 2 4 8 5 6 
9 6 1 5 3 7 2 8 4 
2 8 7 4 1 9 6 3 5 
3 4 5 2 8 6 1 7 9

Table of Content

Sudoku Solver using Naive Approach

In the Naive Approach, we try all possible numbers from 1 to 9 in empty cells until a valid solution is found. It’s straightforward but computationally expensive.

Approach

  • First, initialize the Sudoku Grid
  • Iterate through each cell and for each empty cell (cell with value 0), try placing numbers from 1 to 9.
  • Check if placing the number is valid according to Sudoku rules (no repeated numbers in the same row, column, or subgrid).
  • If placing a number leads to an invalid state, backtrack by removing the number and trying the next one.
  • Continue this process until the entire grid is filled or until all possibilities are exhausted.

Below is the implementation of above approach:

C 
// C program to solve sudoku using naive approach

#include <stdio.h>
#include <stdlib.h>

// N is the size of the 2D matrix N*N
#define N 9

/* A utility function to print grid */
void print(int arr[N][N])
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf("%d ", arr[i][j]);
        printf("\n");
    }
}

// Checks whether it will be legal
// to assign num to the
// given row, col
int isSafe(int grid[N][N], int row, int col, int num)
{

    // Check if we find the same num
    // in the similar row , we return 0
    for (int x = 0; x <= 8; x++)
        if (grid[row][x] == num)
            return 0;

    // Check if we find the same num in the
    // similar column , we return 0
    for (int x = 0; x <= 8; x++)
        if (grid[x][col] == num)
            return 0;

    // Check if we find the same num in the
    // particular 3*3 matrix, we return 0
    int startRow = row - row % 3, startCol = col - col % 3;

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (grid[i + startRow][j + startCol] == num)
                return 0;

    return 1;
}

/* Takes a partially filled-in grid and attempts
to assign values to all unassigned locations in
such a way to meet the requirements for
Sudoku solution (non-duplication across rows,
columns, and boxes) */
int solveSudoku(int grid[N][N], int row, int col)
{

    // Check if we have reached the 8th row
    // and 9th column (0
    // indexed matrix) , we are
    // returning true to avoid
    // further backtracking
    if (row == N - 1 && col == N)
        return 1;

    // Check if column value becomes 9 ,
    // we move to next row and
    // column start from 0
    if (col == N) {
        row++;
        col = 0;
    }

    // Check if the current position
    // of the grid already contains
    // value >0, we iterate for next column
    if (grid[row][col] > 0)
        return solveSudoku(grid, row, col + 1);

    for (int num = 1; num <= N; num++) {

        // Check if it is safe to place
        // the num (1-9) in the
        // given row ,col ->we move to next column
        if (isSafe(grid, row, col, num) == 1) {
            /* assigning the num in the
            current (row,col)
            position of the grid
            and assuming our assigned num
            in the position
            is correct     */
            grid[row][col] = num;

            // Checking for next possibility with next
            // column
            if (solveSudoku(grid, row, col + 1) == 1)
                return 1;
        }

        // Removing the assigned num ,
        // since our assumption
        // was wrong , and we go for next
        // assumption with
        // diff num value
        grid[row][col] = 0;
    }
    return 0;
}

int main()
{
    // 0 means unassigned cells
    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 } };

    if (solveSudoku(grid, 0, 0) == 1)
        print(grid);
    else
        printf("No solution exists");

    return 0;
}

Output
5 3 4 6 7 8 9 1 2 
6 7 2 1 9 5 3 4 8 
1 9 8 3 4 2 5 6 7 
8 5 9 7 6 1 4 2 3 
4 2 6 8 5 3 7 9 1 
7 1 3 9 2 4 8 5 6 
9 6 1 5 3 7 2 8 4 
2 8 7 4 1 9 6 3 5 
3 4 5 2 8 6 1 7 9

Time complexity: O(9(N*N)), For every unassigned index, there are 9 possible options so the time complexity is O(9^(n*n)).
Space Complexity: O(N*N), To store the output array a matrix is needed.

Sudoku Solver using Backtracking

Backtracking is a more efficient approach and can be used to solve sudoku by assigning numbers one by one to empty cells. Before assigning a number, check whether it is safe to assign. 

Approach

  • Find the first empty cell (cell with value 0).
  • Then, try numbers from 1 to 9 in the empty cell.
  • Check if the number is valid in the current position (no conflicts with the same row, column, or subgrid).
  • If valid, recursively attempt to solve the rest of the Sudoku puzzle.
  • If no number is valid, backtrack by undoing the current cell assignment and trying the next number.
  • Repeat the above steps, until the entire grid is filled or until all possibilities are exhausted.

Below is the implementation of above approach:

C 
// C program to solve sudoku using backtracking
#include <stdio.h>

// UNASSIGNED is used for empty
// cells in sudoku grid
#define UNASSIGNED 0

// N is used for the size of Sudoku grid.
// Size will be NxN
#define N 9

// Function declarations
int FindUnassignedLocation(int grid[N][N], int* row,
                           int* col);
int isSafe(int grid[N][N], int row, int col, int num);
int SolveSudoku(int grid[N][N]);
void printGrid(int grid[N][N]);
int UsedInRow(int grid[N][N], int row, int num);
int UsedInCol(int grid[N][N], int col, int num);
int UsedInBox(int grid[N][N], int boxStartRow,
              int boxStartCol, int num);

/* Takes a partially filled-in grid and attempts
to assign values to all unassigned locations in
such a way to meet the requirements for
Sudoku solution (non-duplication across rows,
columns, and boxes) */
int SolveSudoku(int grid[N][N])
{
    int row, col;

    // If there is no unassigned location,
    // we are done
    if (!FindUnassignedLocation(grid, &row, &col))
        // success!
        return 1;

    // Consider digits 1 to 9
    for (int num = 1; num <= 9; num++) {
        // Check if looks promising
        if (isSafe(grid, row, col, num)) {
            // Make tentative assignment
            grid[row][col] = num;

            // Return, if success
            if (SolveSudoku(grid))
                return 1;

            // Failure, unmake & try again
            grid[row][col] = UNASSIGNED;
        }
    }

    // This triggers backtracking
    return 0;
}

/* Searches the grid to find an entry that is
still unassigned. If found, the reference
parameters row, col will be set the location
that is unassigned, and true is returned.
If no unassigned entries remain, false is returned. */
int FindUnassignedLocation(int grid[N][N], int* row,
                           int* col)
{
    for (*row = 0; *row < N; (*row)++) {
        for (*col = 0; *col < N; (*col)++) {
            if (grid[*row][*col] == UNASSIGNED) {
                return 1;
            }
        }
    }
    return 0;
}

/* Returns a boolean which indicates whether
an assigned entry in the specified row matches
the given number. */
int UsedInRow(int grid[N][N], int row, int num)
{
    for (int col = 0; col < N; col++) {
        if (grid[row][col] == num) {
            return 1;
        }
    }
    return 0;
}

/* Returns a boolean which indicates whether
an assigned entry in the specified column
matches the given number. */
int UsedInCol(int grid[N][N], int col, int num)
{
    for (int row = 0; row < N; row++) {
        if (grid[row][col] == num) {
            return 1;
        }
    }
    return 0;
}

/* Returns a boolean which indicates whether
an assigned entry within the specified 3x3 box
matches the given number. */
int UsedInBox(int grid[N][N], int boxStartRow,
              int boxStartCol, int num)
{
    for (int row = 0; row < 3; row++) {
        for (int col = 0; col < 3; col++) {
            if (grid[row + boxStartRow][col + boxStartCol]
                == num) {
                return 1;
            }
        }
    }
    return 0;
}

/* Returns a boolean which indicates whether
it will be legal to assign num to the given
row, col location. */
int isSafe(int grid[N][N], int row, int col, int num)
{
    /* Check if 'num' is not already placed in
    current row, current column
    and current 3x3 box */
    return !UsedInRow(grid, row, num)
           && !UsedInCol(grid, col, num)
           && !UsedInBox(grid, row - row % 3, col - col % 3,
                         num)
           && grid[row][col] == UNASSIGNED;
}

/* A utility function to print grid */
void printGrid(int grid[N][N])
{
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            printf("%d ", grid[row][col]);
        }
        printf("\n");
    }
}

// Driver Code
int main()
{
    // 0 means unassigned cells
    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 } };

    if (SolveSudoku(grid))
        printGrid(grid);
    else
        printf("No solution exists");

    return 0;
}

Output
5 3 4 6 7 8 9 1 2 
6 7 2 1 9 5 3 4 8 
1 9 8 3 4 2 5 6 7 
8 5 9 7 6 1 4 2 3 
4 2 6 8 5 3 7 9 1 
7 1 3 9 2 4 8 5 6 
9 6 1 5 3 7 2 8 4 
2 8 7 4 1 9 6 3 5 
3 4 5 2 8 6 1 7 9

Time complexity: O(9(N*N)), For every unassigned index, there are 9 possible options so the time complexity is O(9^(n*n)). The time complexity remains the same but there will be some early pruning so the time taken will be much less than the naive algorithm but the upper bound time complexity remains the same.
Space Complexity: O(N*N), To store the output array a matrix is needed.

Sudoku Solver using Bit Masks

Bit masking is a technique where we use bits to represent the availability of numbers in rows, columns, and subgrids, for optimizing the checking process. Here, for each row/column/box we will create a bitmask and for each element in the grid set the bit at position ‘value’ to 1 in the corresponding bitmasks.

Approach

  • Use bit masks to track available numbers for each row, column, and subgrid.
  • For each empty cell, determine possible numbers using bit operations.
  • Update bit masks and check if placing a number is valid.
  • If valid, recursively attempt to solve the rest of the Sudoku puzzle.
  • If no number is valid, backtrack by undoing the current cell assignment and trying the next number.
  • Repeat the above steps until the entire grid is filled or until all possibilities are exhausted.

Below is the implementation of above approach:

C 
// C program to solve sudoku using bit masking

#include <stdio.h>

#define N 9

// Bitmasks for each row/column/box
int row[N], col[N], box[N];
int seted = 0;

// Utility function to find the box index
// of an element at position [i][j] in the grid
int getBox(int i, int j) { return i / 3 * 3 + j / 3; }

// Utility function to check if a number
// is present in the corresponding row/column/box
int isSafe(int i, int j, int number)
{
    return !(row[i] & (1 << number))
           && !(col[j] & (1 << number))
           && !(box[getBox(i, j)] & (1 << number));
}

// Utility function to set the initial values of a Sudoku
// board (map the values in the bitmasks)
void setInitialValues(int grid[N][N])
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j]) {
                row[i] |= 1 << grid[i][j];
                col[j] |= 1 << grid[i][j];
                box[getBox(i, j)] |= 1 << grid[i][j];
            }
        }
    }
}

/* Takes a partially filled-in grid and attempts
to assign values to all unassigned locations in
such a way to meet the requirements for
Sudoku solution (non-duplication across rows,
columns, and boxes) */
int SolveSudoku(int grid[N][N], int i, int j)
{
    // Set the initial values
    if (!seted)
        seted = 1, setInitialValues(grid);

    if (i == N - 1 && j == N)
        return 1;
    if (j == N)
        j = 0, i++;

    if (grid[i][j])
        return SolveSudoku(grid, i, j + 1);

    for (int nr = 1; nr <= N; nr++) {
        if (isSafe(i, j, nr)) {
            /* Assign nr in the
                    current (i, j)
                    position and
                    add nr to each bitmask
            */
            grid[i][j] = nr;
            row[i] |= 1 << nr;
            col[j] |= 1 << nr;
            box[getBox(i, j)] |= 1 << nr;

            if (SolveSudoku(grid, i, j + 1))
                return 1;

            // Remove nr from each bitmask
            // and search for another possibility
            row[i] &= ~(1 << nr);
            col[j] &= ~(1 << nr);
            box[getBox(i, j)] &= ~(1 << nr);
        }

        grid[i][j] = 0;
    }

    return 0;
}

// Utility function to print the solved grid
void print(int grid[N][N])
{
    for (int i = 0; i < N; i++, printf("\n")) {
        for (int j = 0; j < N; j++) {
            printf("%d ", grid[i][j]);
        }
    }
}

// Driver Code
int main()
{
    // 0 means unassigned cells
    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 } };

    if (SolveSudoku(grid, 0, 0))
        print(grid);
    else
        printf("No solution exists\n");

    return 0;
}

Output
5 3 4 6 7 8 9 1 2 
6 7 2 1 9 5 3 4 8 
1 9 8 3 4 2 5 6 7 
8 5 9 7 6 1 4 2 3 
4 2 6 8 5 3 7 9 1 
7 1 3 9 2 4 8 5 6 
9 6 1 5 3 7 2 8 4 
2 8 7 4 1 9 6 3 5 
3 4 5 2 8 6 1 7 9

Time complexity: O(9(N*N)). For every unassigned index, there are 9 possible options so the time complexity is O(9^(n*n)). The time complexity remains the same but checking if a number is safe to use is much faster, O(1).
Space Complexity: O(N*N). To store the output array a matrix is needed, and 3 extra arrays of size n are needed for the bitmasks.

Sudoku Solver using Cross-Hatching with Backtracking

Cross-hatching method is an optimization of above method. It starts with identifying the row and column where the element should be placed. Picking the almost-filled elements first will give better pruning.

Approach

  • Identify cells where numbers can only fit into one row or column within a subgrid.
  • Apply backtracking to fill these cells.
  • Verify if the number is valid using backtracking rules.
  • If valid, recursively attempt to solve the rest of the Sudoku puzzle.
  • If no number is valid, backtrack by undoing the current cell assignment and trying the next number.
  • Repeat the above steps, until the entire grid is filled or until all possibilities are exhausted.

Below is the implementation of above approach:

C 
// C program to solve suoku using Cross-Hatching with
// backtracking

#include <stdio.h>

#define N 9

// Input matrix
int arr[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 } };

// Position of the input elements in the arr
int pos[10][9][2]; // Assuming maximum 9 positions for each
                   // number (1-9)
int rem[10]; // Count of remaining occurrences for each
             // number (1-9)

// Graph defining tentative positions of the elements to be
// filled
int graph[10][9][9]; // 3D array to represent graph

// Print the matrix array
void printMatrix()
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
}

// Method to check if the inserted element is safe
int is_safe(int x, int y)
{
    int key = arr[x][y];
    for (int i = 0; i < N; i++) {
        if (i != y && arr[x][i] == key) {
            return 0;
        }
        if (i != x && arr[i][y] == key) {
            return 0;
        }
    }

    int r_start = (x / 3) * 3;
    int r_end = r_start + 3;

    int c_start = (y / 3) * 3;
    int c_end = c_start + 3;

    for (int i = r_start; i < r_end; i++) {
        for (int j = c_start; j < c_end; j++) {
            if (i != x && j != y && arr[i][j] == key) {
                return 0;
            }
        }
    }
    return 1;
}

// method to fill the matrix
int fill_matrix(int k, int keys[], int r, int rows[],
                int num_rows)
{
    int c = 0;
    arr[rows[r]][c] = keys[k];
    if (is_safe(rows[r], c)) {
        if (r < num_rows - 1) {
            if (fill_matrix(k, keys, r + 1, rows,
                            num_rows)) {
                return 1;
            }
            else {
                arr[rows[r]][c] = 0;
            }
        }
        else {
            if (k < N - 1) {
                if (fill_matrix(k + 1, keys, 0, rows,
                                num_rows)) {
                    return 1;
                }
                else {
                    arr[rows[r]][c] = 0;
                }
            }
            return 1;
        }
    }
    arr[rows[r]][c] = 0;
    return 0;
}

// Fill the pos and rem arrays. It will be used to build the
// graph
void build_pos_and_rem()
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int key = arr[i][j];
            if (key > 0) {
                int found = 0;
                for (int p = 0; p < 9; p++) {
                    if (pos[key][p][0] == -1) {
                        pos[key][p][0] = i;
                        pos[key][p][1] = j;
                        found = 1;
                        break;
                    }
                }
                if (!found) {
                    rem[key]--;
                }
            }
        }
    }

    // Fill the elements not present in input matrix
    for (int i = 1; i <= 9; i++) {
        if (rem[i] == 0) {
            for (int p = 0; p < 9; p++) {
                pos[i][p][0] = -1;
                pos[i][p][1] = -1;
            }
        }
    }
}

int main()
{
    printMatrix();
    return 0;
}

Output
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

Time complexity: O(9^(n*n)).  Due to the element that needs to fit in a cell will come earlier as we are filling almost filled elements first, it will help in less number of recursive calls. So the time taken will be much less than the naive approaches but the upper bound time complexity remains the same.
Auxiliary Space: O(n*n).  A graph of the remaining positions to be filled for the respected elements is created.


 


Reffered: https://www.geeksforgeeks.org

C Language

Related
Edit Distance in C Edit Distance in C
Largest Sum Contiguous Subarray in C Largest Sum Contiguous Subarray in C
C Program to Implement Circular Linked List C Program to Implement Circular Linked List
Queue using Linked List in C Queue using Linked List in C
Tarjan’s Algorithm in C Language Tarjan’s Algorithm in C Language

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 16



 

Horje