recursion - C programming - Sodoku solution (backtracking)

Question

the Question is: to get from the user sodoku board and if there is a solution to print it, if not to print no solution! the solution of the soduko: two identical numbers mmust not appear on the same line; two identical numbers must not appear in the same colum. I worte a program that works perfectly when I put the soduko board and the size (global parametes-as shown un my code) but when I tried to receive from the user it took so much time to run the solution and sometimes it didn't retun anything. I would like to understand why?!

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

#define SIZE 5


int matrix[5][5] = {
    {4,2,0,0,5},
    {2,0,0,1,3},
    {5,0,1,2,0},
    {0,0,3,0,2},
    {0,0,0,0,0},
};


void print_sudoku()
{
    int i,j;
    for(i=0;i<SIZE;i++)
    {
        for(j=0;j<SIZE;j++)
        {
            printf("%d ",matrix[i][j]);
        }
        printf("
");
    }
}


int number_unassigned(int *row, int *col)
{
    int num_unassign = 0;
    int i,j;
    for(i=0;i<SIZE;i++)
    {
        for(j=0;j<SIZE;j++)
        {
            if(matrix[i][j] == 0)
            {
                *row = i;
                *col = j;
                num_unassign = 1;
                return num_unassign;
            }
        }
    }
    return num_unassign;
}


int is_safe(int n, int r, int c)
{
    int i;

    for(i=0;i<SIZE;i++)
    {
        if(matrix[r][i] == n)
            return 0;
    }
    for(i=0;i<SIZE;i++)
    {
        if(matrix[i][c] == n)
            return 0;
    }
    return 1;
}


int solve_sudoku()
{
    int row;
    int col;
 
    if(number_unassigned(&row, &col) == 0)
        return 1;

    int i;

    for(i=1;i<=SIZE;i++)
    {
  
        if(is_safe(i, row, col))
        {
            matrix[row][col] = i;

            if(solve_sudoku())
                return 1;

            matrix[row][col]=0;
        }
    }
    return 0;
}


int main()
{
    if (solve_sudoku())
        print_sudoku();
    else
        printf("No solution!
");
    return 0;
}

and this is whe code that I used to ask the user to enter a sodoku board:

int** ReadSoduko(int n) {
    int** matrix = (int**) malloc((sizeof(int*)) * n);
    for(int i = 0; i < n; ++i) {
        matrix[i] = malloc(sizeof(int) * n);
    }
    printf("
Enter your soduko board:
");
    for(int i = 0; i < n; ++i) {
          printf("Enter row [%d]: ", i);
        for(int j = 0; j < n; ++j) {
            scanf("%d", &matrix[i][j]);
        }
    }
    return matrix;
}

question from:https://stackoverflow.com/questions/65646630/c-programming-sodoku-solution-backtracking

Answer 1

I suspect your problem is related to one thing: #define SIZE that you are probably forgetting to update when reading dynamically. Since you use SIZE in your loops, if that is not the real size of your matrix, then it probably won't work. I've changed 2 lines and added 3 other (the lines with comments at the end). Try it now.

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

int SIZE; //changed here

int** matrix; //changed here

void print_sudoku()
{
    int i, j;
    for (i = 0; i < SIZE; i++)
    {
        for (j = 0; j < SIZE; j++)
        {
            printf("%d ", matrix[i][j]);
        }
        printf("
");
    }
}


int number_unassigned(int* row, int* col)
{
    int num_unassign = 0;
    int i, j;
    for (i = 0; i < SIZE; i++)
    {
        for (j = 0; j < SIZE; j++)
        {
            if (matrix[i][j] == 0)
            {
                *row = i;
                *col = j;
                num_unassign = 1;
                return num_unassign;
            }
        }
    }
    return num_unassign;
}


int is_safe(int n, int r, int c)
{
    int i;

    for (i = 0; i < SIZE; i++)
    {
        if (matrix[r][i] == n)
            return 0;
    }
    for (i = 0; i < SIZE; i++)
    {
        if (matrix[i][c] == n)
            return 0;
    }
    return 1;
}


int solve_sudoku()
{
    int row;
    int col;


    if (number_unassigned(&row, &col) == 0)
        return 1;

    int i;

    for (i = 1; i <= SIZE; i++)
    {

        if (is_safe(i, row, col))
        {
            matrix[row][col] = i;

            if (solve_sudoku())
                return 1;

            matrix[row][col] = 0;
        }
    }
    return 0;
}


int** ReadSoduko(int n) {
    int** matrix = (int**)malloc((sizeof(int*)) * n);
    for (int i = 0; i < n; ++i) {
        matrix[i] = (int*) malloc(sizeof(int) * n);
    }
    printf("
Enter your soduko board:
");
    for (int i = 0; i < n; ++i) {
        printf("Enter row [%d]: ", i);
        for (int j = 0; j < n; ++j) {
            scanf("%d", &matrix[i][j]);
        }
    }
    return matrix;
}

int main()
{
    printf("Size of matrix: "); //added this
    scanf("%d", &SIZE); //added this
    matrix = ReadSoduko(SIZE); //added this
    if (solve_sudoku())
        print_sudoku();
    else
        printf("No solution!
");
    return 0;
}

And don't forget that the matrix that you have declared statically doesn't have a solution! I have tested the same matrix, just replacing the 2 in first line by a 0 and it worked here.