4
\$\begingroup\$

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;
}
\$\endgroup\$
3
\$\begingroup\$

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().

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ And for non-beginners: (Minor remark, advanced topic) As a micro-optimization, int *row, int *column could have been changed to int * restrict row, int * restrict column to clarify that these pointers won't alias and point at the same memory address. This might allow the compiler to produce ever so slightly faster code. \$\endgroup\$ – Lundin Jun 9 at 14:09

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.