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

• Countingstuff: This look great, to me. How can it be more efficient? Sudoku solving is a well studied area, one observation is that you can implement 'Algorithm X' en.wikipedia.org/wiki/Knuth%27s_Algorithm_X which applies to Sudoku rafal.io/posts/solving-sudoku-with-dancing-links.html and this will be faster on average. I imagine though that there are faster more bespoke algorithms you could find and implement. Personally I think the nicest thing to do is not any faster, which is to rephrase Sudokus as extending a graph colouring, and instead write an algorithm which extends graph colourings.
• user3629249: There seems to be a key problem with the code. 1) the board is declared as a 2 dimensional array of ints 2) the grid is defined as a single array of 9 pointers to int. Therefore, IMO: there is a serious problem with the code logic
• Shechner: @user3629249 grid is a pointer to an array of GRID_SIZE integers. notice the parentheses. a pointer to an array is a 2d array.

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.

• Shechner: Thank you for you comment! and, I better #define SUBGRID_SIZE as sqrt(GRID_SIZE), don't I? then I don't have to change 2 constants, just one. ("It is set on a board with NxN squares where N is a number with a whole-number square root (4x4, 9x9, etc.)")
• S.S. Anne: @Shechner I have a better solution where SUBGRID_SIZE is a constant; see my edit.
• Shechner: I like it, but don't you think sqrting is better since it is dynamic?
• S.S. Anne: @Shechner sqrt gives a double result which will cause a conversion to double on every iteration. double conversion takes time, and a decent amount of it, too. A static constant will almost always be faster, and will leave even less room for errors if you have that #if there. For example, if GRID_SIZE is 10 and SUBGRID_SIZE is sqrt(GRID_SIZE) vs. GRID_SIZE is 10 and SUBGRID_SIZE is 3; the error in the latter will be caught but the error in the former will not.