Simple recursive Sudoku solver My Sudoku solver is fast enough and good with small data (4*4 and 9*9 Sudoku). But with a 16*16 board it takes too long and doesn't solve 25*25 Sudoku at all. How can I improve my program in order to solve giant Sudoku faster?

I use backtracking and recursion.

It should work with any size Sudoku by changing only the define of SIZE, so I can't make any specific bit fields or structs that only work for 9*9, for example.  

#include &lt;stdio.h&gt;
#include &lt;math.h&gt;

#define SIZE 16
#define EMPTY 0

int SQRT = sqrt(SIZE);

int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number);
int Solve(int sudoku[SIZE][SIZE], int row, int col);

int main() {
int sudoku[SIZE][SIZE] = {
{0,1,2,0,0,4,0,0,0,0,5,0,0,0,0,0},
{0,0,0,0,0,2,0,0,0,0,0,0,0,14,0,0},
{0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0},
{11,0,0,0,0,0,0,0,0,0,0,16,0,0,0,0},
{0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,16,0,0,0,0,0,0,2,0,0,0,0,0},
{0,0,0,0,0,0,0,0,11,0,0,0,0,0,0,0},
{0,0,14,0,0,0,0,0,0,4,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,16,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,14,0,0,13,0,0},
{0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,11,0,0,0,0,0,0,0,0,0,0,0,0,0},
{16,0,0,0,0,0,11,0,0,3,0,0,0,0,0,0},
};
/*
int sudoku[SIZE][SIZE] = {
{6,5,0,8,7,3,0,9,0},
{0,0,3,2,5,0,0,0,8},
{9,8,0,1,0,4,3,5,7},
{1,0,5,0,0,0,0,0,0},
{4,0,0,0,0,0,0,0,2},
{0,0,0,0,0,0,5,0,3},
{5,7,8,3,0,1,0,2,6},
{2,0,0,0,4,8,9,0,0},
{0,9,0,6,2,5,0,8,1}
};*/

    if (Solve (sudoku,0,0))
    {
        for (int i=0; i&lt;SIZE; i++)
        {
            for (int j=0; j&lt;SIZE; j++) {
                printf("%2d ", sudoku[i][j]);
            }
            printf ("\n");
        }
    }
    else
    {
        printf ("No solution \n");
    }
    return 0;
}

int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number)
{
    int prRow = SQRT*(row/SQRT);
    int prCol = SQRT*(col/SQRT);

    for (int i=0;i&lt;SIZE;i++){
        if (sudoku[i][col] == number) return 0;
        if (sudoku[row][i] == number) return 0;
        if (sudoku[prRow + i / SQRT][prCol + i % SQRT] == number) return 0;}
    return 1;
}

int Solve(int sudoku[SIZE][SIZE], int row, int col)
{
    if (SIZE == row) {
        return 1;
    }

    if (sudoku[row][col]) {
        if (col == SIZE-1) {
            if (Solve (sudoku, row+1, 0)) return 1;
        } else {
            if (Solve(sudoku, row, col+1)) return 1;
        }
        return 0;
    }

    for (int number = 1; number &lt;= SIZE; number ++)
    {
        if(IsValid(sudoku,row,col,number))
        {
            sudoku [row][col] = number;

            if (col == SIZE-1) {
                if (Solve(sudoku, row+1, 0)) return 1;
            } else {
                if (Solve(sudoku, row, col+1)) return 1;
            }

            sudoku [row][col] = EMPTY;
        }
    }
    return 0;
}
The first thing that will help is to switch this from a recursive algorithm to an iterative one. This will prevent the stack overflow that prevents you from solving 25x25, and will be a bit faster to boot.

However to speed this up more, you will probably need to use a smarter algorithm. If you track what numbers are possible in each square, you will find that much of the time, there is only 1 possibility. In this case, you know what number goes there. You then can update all of the other squares in the same row, col, or box as the one you just filled in. To implement this efficiently, you would want to define a set (either a bitset or hashset) for what is available in each square, and use a heap to track which squares have the fewest remaining possibilities.