/* sudoku.c */
#include <stdio.h>

int feld[9][9] = {         /* Das zu loesende Sudoku */
  {5,3,0, 0,7,0, 0,0,0},
  {6,0,0, 1,9,5, 0,0,0},
  {0,9,8, 0,0,0, 0,6,0},

  {8,0,0, 0,6,0, 0,0,3},
  {4,0,0, 8,0,3, 0,0,1},
  {7,0,0, 0,2,0, 0,0,6},

  {0,6,0, 0,0,0, 2,8,0},
  {0,0,0, 4,1,9, 0,0,5},
  {0,0,0, 0,8,0, 0,7,9},
};

void output() {
  int i,j;
  printf("-------------------\n");
  for ( i = 0; i < 9; i++ ) {
    for ( j = 0; j < 9; j++ ) {
      printf("%d ",feld[i][j]);
      if ( j % 3 == 2) printf(" ");
    }
    printf("\n");
    if ( i % 3 == 2 ) printf("\n");
  }
}

/*  Es wird u>0 vorausgesetzt.  Rueckgabe von 1, falls u bei Position
(a,b) moeglich, sonst Rueckgabe von 0. */

int check(int a, int b, int u) {
  int i,j;
  if (feld[a][b])        return 0;
  for (i = 0; i < 9; i++) {
    if (u == feld[a][i]) return 0;
    if (u == feld[i][b]) return 0;
  }
  for (i = a - a%3 ; i < a - a%3 + 3; i++)
    for (j = b - b%3 ; j < b - b%3 + 3; j++)
      if (u == feld[i][j])
        return 0;
  return 1;
}

int versuche(int k) {  /* k --> k/9 k%9 */
  int i, q;
  while ( k<=80 && feld[k/9][k%9] ) k++; /* naechstes freies Feld  */
  if ( k == 81 ) return 1;               /* alles belegt, fertig   */
  for ( q=0, i=1 ; q == 0 && i <= 9 ; i++) {
    if ( check(k/9, k%9, i) ) {  /* teste das Feld k mit allen i    */
      feld[k/9][k%9] = i;
      if ( (q = versuche(k+1) ) == 0) /* naechstes Feld  */
        feld[k/9][k%9] = 0;  /* Falls erfolglos, Ruecksetzen    */
    }
  }
  return q;
}

int main() {
  output();
  versuche(0);
  output();
}