Sudoku solver using backtracting and depth-first-search

Question

I've recently finished my first ever C program. I implemented a Sudoku solver that uses backtracking.

Does my code look like a proper C-program? Are there any recommendations for improving my code?

#include <stdio.h>

int valid(int[][9], int, int, int);
int solve(int[][9]);
int find_empty_cell(int[][9], int *, int *);

int main() {
  int puzzle[9][9] = {{1, 7, 4, 0, 9, 0, 6, 0, 0},
                      {0, 0, 0, 0, 3, 8, 1, 5, 7},
                      {5, 3, 0, 7, 0, 1, 0, 0, 4},
                      {0, 0, 7, 3, 4, 9, 8, 0, 0},
                      {8, 4, 0, 5, 0, 0, 3, 6, 0},
                      {3, 0, 5, 0, 0, 6, 4, 7, 0},
                      {2, 8, 6, 9, 0, 0, 0, 0, 1},
                      {0, 0, 0, 6, 2, 7, 0, 3, 8},
                      {0, 5, 3, 0, 8, 0, 0, 9, 6}};
  int row = 0;
  int column = 0;

  if (solve(puzzle)) {
    printf("\n+-----+-----+-----+\n");
    for (int x = 0; x < 9; ++x) {
      for (int y = 0; y < 9; ++y) printf("|%d", puzzle[x][y]);
      printf("|\n");
      if (x % 3 == 2) printf("\n+-----+-----+-----+\n");
    }
  }
  else {
    printf("\n\nNO SOLUTION FOUND\n\n");
  }

  return 0;
}

int valid(int puzzle[][9], int row, int column, int guess) {
  int corner_x = row / 3 * 3;
  int corner_y = column / 3 * 3;

  for (int x = 0; x < 9; ++x) {
    if (puzzle[row][x] == guess) return 0;
    if (puzzle[x][column] == guess) return 0;
    if (puzzle[corner_x + (x % 3)][corner_y + (x / 3)] == guess) return 0;
  }
  return 1;
}

int find_empty_cell(int puzzle[][9], int *row, int *column) {
  for (int x = 0; x < 9; x++) {
    for (int y = 0; y < 9; y++) {
      if (!puzzle[x][y]) {
        *row = x;
        *column = y;

        return 1;
      }
    }
  }
  return 0;
}

int solve(int puzzle[][9]) {
  int row;
  int column;

  if(!find_empty_cell(puzzle, &row, &column)) return 1;

  for (int guess = 1; guess < 10; guess++) {
    if (valid(puzzle, row, column, guess)) {
      puzzle[row][column] = guess;

      if(solve(puzzle)) return 1;
      puzzle[row][column] = 0;
    }
  }
  return 0;
}

Answer 1

Overall it looks fine for a beginner-level program, you keep the functions small and separate different parts of the logic between them, which is good.

• int valid(int[][9], int, int, int); You should make a habit of naming your parameters even during function declaration. Ideally the function definition is a copy/paste of the declaration.
• (Minor remark) It would be clearer to write int puzzle[9][9] in the parameter list, even though it makes no practical difference. It gives self-documenting code, however.
• But you should entirely avoid "magic numbers" like 9 in your code. You should have #define SUDOKU_SIZE 9 or such instead. This goes for all the divide by 3 statements too, it's not clear to the reader where the "magic number" 3 came from. This is where you would need to place a comment, since the code doesn't speak for itself.

• (Major issue) Your indention style is exotic and therefore wouldn't be tolerated in a professional setting. For example the line following an if or for etc should be placed on a line of its own, and also indented (2 or 4 spaces are ok):

  for (int y = 0; y < 9; ++y)
    printf("|%d", puzzle[x][y]);
  

  For mission-critical programs, this style isn't tolerated either, but you need to always use { } compound statements even if there is just a single line.

• (Minor remark) int puzzle[9][9] This could perhaps have been declared const, so you have one read-only table of the original data, and place the solution in a different matrix. You could then also have implemented const correctness for functions that do not modify this matrix.

• (Minor remark) Coding style preference - avoid using the ! for operands that aren't boolean. Instead of !puzzle[x][y], I'd write puzzle[x][y]==0 since the purpose is to check if something is 0, not false.

• Instead of returning 1/0 type int, you should be using true/false and bool from stdbool.h.

• (Minor remark) This int main() is obsolete style in C. You should be using int main(void) instead. (C and C++ are different here)

• (Minor remark) Your functions are pretty short so I'd say it is ok to return from multiple places inside them. For more complex functions, multiple returns from a function is sometimes frowned upon and it's preferred to only have a single return at the end. This is no black/white rule though. I say avoid multiple return statements unless it actually makes the code more readable. In your current program it's fine.

• The matrix print could be made a function of its own, to be called from main().