# C backtracking Sudoku solver

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

• 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. Mar 15 '20 at 16:04
• 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 Mar 16 '20 at 7:34
• @user3629249 grid is a pointer to an array of GRID_SIZE integers. notice the parentheses. a pointer to an array is a 2d array. Mar 16 '20 at 12:06

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.

• 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.)") Mar 15 '20 at 17:04
• @Shechner I have a better solution where SUBGRID_SIZE is a constant; see my edit. Mar 15 '20 at 17:13
• I like it, but don't you think sqrting is better since it is dynamic? Mar 15 '20 at 17:18
• @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. Mar 15 '20 at 17:20