3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Countingstuff Mar 15 at 16:04
  • \$\begingroup\$ 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 \$\endgroup\$ – user3629249 Mar 16 at 7:34
  • \$\begingroup\$ @user3629249 grid is a pointer to an array of GRID_SIZE integers. notice the parentheses. a pointer to an array is a 2d array. \$\endgroup\$ – Shechner Mar 16 at 12:06
2
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.