C backtracking Sudoku solver

Question

I wrote this program in C to solve a given Sudoku puzzle (represented as 2D array) using backtracking algorithm. How can I make it more efficient, maybe faster and more C-onic?

This is my first post here, all suggestions are welcome! (be pedantic with me!)

#include <stdio.h>

#define GRID_SIZE 9

typedef int (*grid)[GRID_SIZE];
typedef struct { int x, y; } v2;

void dump(const grid board)
{
    int i, j;

    for (i = 0; i < GRID_SIZE; ++i)
    {
        for (j = 0; j < GRID_SIZE; ++j)
            printf("%d ", board[i][j]);
        puts("");
    }
}

int possible(const grid board, const v2 pos, const int v)
{
    int i, j, x0, y0;

    for (i = 0; i < GRID_SIZE; ++i)
        if (board[pos.y][i] == v)
            return 0;
    for (i = 0; i < GRID_SIZE; ++i)
        if (board[i][pos.x] == v)
            return 0;

    x0 = (pos.x / 3) * 3;
    y0 = (pos.y / 3) * 3;

    for (i = 0; i < 3; ++i)
        for (j = 0; j < 3; ++j)
            if (board[i + y0][j + x0] == v)
                return 0;

    return 1;
}

void solve(grid board)
{
    int y, x, v;

    for (y = 0; y < GRID_SIZE; ++y)
        for (x = 0; x < GRID_SIZE; ++x)
            if (board[y][x] == 0)
            {
                for (v = 1; v < 10; ++v)
                {
                    const v2 pos = {x, y};
                    if (possible(board, pos, v))
                    {
                        board[y][x] = v;
                        solve(board);
                        board[y][x] = 0;
                    }
                }
                return;
            }

    dump(board);
}

int main(void)
{
    /* 0 represents an empty cell */
    int board[GRID_SIZE][GRID_SIZE] =
    {
        {7, 0, 0, 0, 0, 1, 0, 0, 3},
        {0, 0, 3, 0, 0, 2, 6, 0, 0},
        {0, 2, 0, 7, 0, 8, 0, 0, 5},
        {0, 6, 0, 0, 1, 0, 3, 7, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 5, 0, 7, 0, 0, 6, 0},
        {3, 0, 0, 2, 0, 4, 0, 5, 0},
        {0, 0, 8, 5, 0, 0, 7, 0, 0},
        {5, 0, 0, 1, 0, 0, 0, 0, 9},
    };

    solve(board);

    return 0;
}

Answer 1

I would tag your struct in addition to, if not instead of, using a typedef:

struct v2
{
    int x, y;
};
// typedef struct v2 v2;

Then you can use struct v2 wherever you are using v2. This makes it clear that v2 is a structure.

I think you should create a symbolic SUBGRID_SIZE instead of using 3 here:

x0 = (pos.x / 3) * 3;
y0 = (pos.y / 3) * 3;

for (i = 0; i < 3; ++i)
    for (j = 0; j < 3; ++j)
        if (board[i + y0][j + x0] == v)
            return 0;

This would make it more obvious about what you're dealing with. I would put GRID_SIZE and SUBGRID_SIZE next to each other, and then use an #if to check if they're valid:

#define GRID_SIZE 9
#define SUBGRID_SIZE 3

#if SUBGRID_SIZE * SUBGRID_SIZE != GRID_SIZE
# error grid size and subgrid size dont match
#endif

You might use printf("\n"); or putchar('\n'); instead of puts("");. The compiler is likely to optimize the former into puts(""); anyway, and the second may be faster.

I like that you've used const everywhere that you're not going to modify a variable. This eliminates chances to make mistakes.

Your formatting is very good. It is consistent, too.

Your code is also well-commented. The only thing that was slightly non-obvious you've commented:

/* 0 represents an empty cell */

Being pedantic with you, your code has zero warnings with -Wall -Wextra -std=c99 -pedantic.