Sudoku Puzzle Solutions in C


I don't usually have much interst in working these kinds of puzzles but I do like to write compact programs that solve them. Here are solutions for 9x9 and 16x16 Sudoku. They can be downloaded here. The 9x9 program is below and is followed by the execution result. You can compile them in linux with "gcc -o sudoku9 sudoku9.c" and "gcc -o sudoku16 sudoku16.c", and probably in windows with Cygwin.

They use a recursive backtracking algorithm which tend to be code efficient but computationally inefficient.


#include <stdlib.h>
#include <stdio.h>

int solve_sudoku(int i);
int check_sudoku(int r, int c);
void print_sudoku();

#if 0
int sudoku[9][9] = {{0,0,0,8,5,0,0,0,2},
                    {0,0,0,0,0,2,1,4,0},
                    {8,9,0,0,0,4,0,0,0},
                    {0,4,6,0,0,0,0,3,0},
                    {0,0,0,7,0,5,0,0,0},
                    {0,1,0,0,0,0,5,9,0},
                    {0,0,0,4,0,0,0,1,9},
                    {0,7,4,2,0,0,0,0,0},
                    {1,0,0,0,3,8,0,0,0}};
#else
int sudoku[9][9] = {{5,3,0,0,0,0,0,0,0},
                    {0,0,9,0,7,0,0,1,6},
                    {0,0,0,0,0,0,0,0,0},
                    {0,0,6,0,0,5,0,7,0},
                    {7,0,0,0,6,0,2,0,1},
                    {0,0,8,2,0,0,0,0,0},
                    {0,8,5,0,0,0,7,9,0},
                    {4,0,0,0,1,0,3,0,0},
                    {0,2,0,0,0,0,0,0,0}};
#endif

int n = 0;

int main()
{
  print_sudoku();

  if (solve_sudoku(0))
  {
    printf("Solution found after %d moves\n\n", n);
    print_sudoku();
  }
  else
    printf("No solution found after %d moves\n", n);
}

int solve_sudoku(int i)
{
  int r, c;

  if (i<0) return 0;
  else if (i>=81) return -1;

  r = i/9; c = i%9;
  if (sudoku[r][c])
    return check_sudoku(r, c) && solve_sudoku(i+1);
  else
    for (sudoku[r][c]=9; sudoku[r][c]>0; sudoku[r][c]--)
      if (solve_sudoku(i)) return -1;

  return 0;
}

int check_sudoku(int r, int c)
{
  int i;
  int rr, cc;

  n++;
  //print_sudoku();
  for (i=0; i<9; i++)
  {
    if (i!=c && sudoku[r][i]==sudoku[r][c]) return 0;
    if (i!=r && sudoku[i][c]==sudoku[r][c]) return 0;
    rr = r/3*3+i/3; cc = c/3*3+i%3;
    if ((rr!=r || cc!=c) && sudoku[rr][cc]==sudoku[r][c]) return 0;
  }
  return -1;
}

void print_sudoku()
{
  int i, j;

  for (i=0; i<9; i++)
  {
    for (j=0; j<9; j++)
      printf(" %d", sudoku[i][j]);
    printf("\n");
  }
  printf("\n");
}

matt@duffy:~$ gcc -o sudoku9 sudoku9.c
matt@duffy:~$ ./sudoku9
 5 3 0 0 0 0 0 0 0
 0 0 9 0 7 0 0 1 6
 0 0 0 0 0 0 0 0 0
 0 0 6 0 0 5 0 7 0
 7 0 0 0 6 0 2 0 1
 0 0 8 2 0 0 0 0 0
 0 8 5 0 0 0 7 9 0
 4 0 0 0 1 0 3 0 0
 0 2 0 0 0 0 0 0 0

Solution found after 492401 moves

 5 3 1 4 9 6 8 2 7
 8 4 9 3 7 2 5 1 6
 6 7 2 8 5 1 9 4 3
 2 9 6 1 3 5 4 7 8
 7 5 4 9 6 8 2 3 1
 3 1 8 2 4 7 6 5 9
 1 8 5 6 2 3 7 9 4
 4 6 7 5 1 9 3 8 2
 9 2 3 7 8 4 1 6 5

matt@duffy:~$

Return to Matt's World

Free Web Hosting