/* Backtracking Sudoku Solver
 * (C) Bernd Edlinger 2012
 */
#include <stdio.h>


#define DIM1 3
#define DIM2 3
#define BACKTRACKING


void print(int s[DIM1*DIM2][DIM1*DIM2])
{
  int x,y;
  for (y=0; y<DIM1*DIM2; y++)
  {
    for (x=0; x<DIM1*DIM2; x++)
    {
      printf(" %d", s[y][x]);
      if ((x%DIM1) == DIM1-1)
        printf(" ");
    }
    if ((y%DIM2) == DIM2-1)
      printf("\n");
    printf("\n");
  }
}


int check(int s[DIM1*DIM2][DIM1*DIM2])
{
  int x,y,z;
  int u[DIM1*DIM2+1];

  for (y=0; y<DIM1*DIM2; y++)
    for (x=0; x<DIM1*DIM2; x++)
      if (s[y][x]<0 || s[y][x]>DIM1*DIM2)
        return -1;

  for (z=0; z<=DIM1*DIM2; z++)
    u[z] = 0;

  /* zeilen */
  for (y=0; y<DIM1*DIM2; y++) {
    for (x=0; x<DIM1*DIM2; x++)
      u[s[y][x]]++;
    for (z=1; z<=DIM1*DIM2; z++)
      if (u[z]>1)
        return -2;
      else
        u[z] = 0;
  }

  /* spalten */
  for (x=0; x<DIM1*DIM2; x++) {
    for (y=0; y<DIM1*DIM2; y++)
      u[s[y][x]]++;
    for (z=1; z<=DIM1*DIM2; z++)
      if (u[z]>1)
        return -3;
      else
        u[z] = 0;
  }

  /* bloecke */
  for (x=0; x<DIM1*DIM2; x++) {
    for (y=0; y<DIM1*DIM2; y++)
      u[s[x/DIM2*DIM2+y/DIM1][x%DIM2*DIM1+y%DIM1]]++;
    for (z=1; z<=DIM1*DIM2; z++)
      if (u[z]>1)
        return -4;
      else
        u[z] = 0;
  }

  return u[0] ? 0 : 1;
}

int solve(int s[DIM1*DIM2][DIM1*DIM2])
{
  int v,w,x,y,z;
  int result;

  if (check(s)<0)
    return -1;

  result=0;

  search:

  /* regel 1 */
  for (y=0; y<DIM1*DIM2; y++)
    for (z=1; z<=DIM1*DIM2; z++) {
        v=w=0;
        for (x=0; x<DIM1*DIM2 && v<=1; x++)
          if (s[y][x]==0) {
            s[y][x] = z;
            if (check(s)>=0) {
              v++;
              w=x;
            }
            s[y][x] = 0;
          }
        if (v==1) {
          printf("rule 1: s[%d][%d]=%d\n", y,w,z);
          s[y][w] = z;
          result++;
          goto search;
        }
      }


  /* regel 2 */
  for (x=0; x<DIM1*DIM2; x++)
    for (z=1; z<=DIM1*DIM2; z++) {
        v=w=0;
        for (y=0; y<DIM1*DIM2 && v<=1; y++)
          if (s[y][x]==0) {
            s[y][x] = z;
            if (check(s)>=0) {
              v++;
              w=y;
            }
            s[y][x] = 0;
          }
        if (v==1) {
          printf("rule 2: s[%d][%d]=%d\n", w,x,z);
          s[w][x] = z;
          result++;
          goto search;
        }
      }


  /* regel 3 */
  for (x=0; x<DIM1*DIM2; x++)
    for (z=1; z<=DIM1*DIM2; z++) {
        int x0, y0;
        v=w=0;
        for (y=0; y<DIM1*DIM2 && v<=1; y++) {
          x0 = x%DIM2*DIM1+y%DIM1;
          y0 = x/DIM2*DIM2+y/DIM1;
          if (s[y0][x0]==0) {
            s[y0][x0] = z;
            if (check(s)>=0) {
              v++;
              w=y;
            }
            s[y0][x0] = 0;
          }
        }
        if (v==1) {
          x0 = x%DIM2*DIM1+w%DIM1;
          y0 = x/DIM2*DIM2+w/DIM1;
          printf("rule 3: s[%d][%d]=%d\n", y0,x0,z);
          s[y0][x0] = z;
          result++;
          goto search;
        }
      }


  /* regel 4 */
  for (y=0; y<DIM1*DIM2; y++)
    for (x=0; x<DIM1*DIM2; x++)
      if (s[y][x]==0) {
        v=w=0;
        for (z=1; z<=DIM1*DIM2 && v<=1; z++) {
          s[y][x] = z;
          if (check(s)>=0) {
            v++;
            w=z;
          }
          s[y][x] = 0;
        }
        if (v==1) {
          printf("rule 4: s[%d][%d]=%d\n", y,x,w);
          s[y][x] = w;
          result++;
          goto search;
        }
        if (v==0) {
          printf("rule 4: s[%d][%d]=?\n", y,x);
          return -2;
        }
      }


#ifdef BACKTRACKING
  /* regel 5 */
  w=DIM1*DIM2;
  for (y=0; y<DIM1*DIM2; y++)
    for (x=0; x<DIM1*DIM2; x++)
      if (s[y][x]==0) {
        v=0;
        for (z=1; z<=DIM1*DIM2; z++) {
          s[y][x] = z;
          if (check(s)>=0)
            v++;
        }
        s[y][x] = 0;
        if (v<w)
          w=v;
      }

  for (y=0; y<DIM1*DIM2; y++)
    for (x=0; x<DIM1*DIM2; x++)
      if (s[y][x]==0) {
        int x1,y1;
        int s1[DIM1*DIM2][DIM1*DIM2];
        int s2[DIM1*DIM2][DIM1*DIM2];
        v=0;
        for (z=1; z<=DIM1*DIM2 && v<=w; z++) {
          s[y][x] = z;
          if (check(s)>=0)
            v++;
        }
        s[y][x] = 0;
        if (v>w)
          continue;
        v=w=0;
        for (z=1; z<=DIM1*DIM2 && v<=1; z++) {
          for (y1=0; y1<DIM1*DIM2; y1++)
            for (x1=0; x1<DIM1*DIM2; x1++) {
              s1[y1][x1] = s[y1][x1];
            }
          s1[y][x] = z;
          if (check(s1)>=0) {
            printf("guess : s[%d][%d]=%d\n", y,x,z);
            if (solve(s1)>=0) {
              v++;
              w=z;
              for (y1=0; y1<DIM1*DIM2; y1++)
                for (x1=0; x1<DIM1*DIM2; x1++) {
                  if (s1[y1][x1]==0) {
                    goto revert;
                  }
                  s2[y1][x1] = s1[y1][x1];
                }
            }
          }
        }
        if (v==1) {
          printf("rule 5: s[%d][%d]=%d\n", y,x,w);
          s[y][x] = w;
          result++;
          for (y1=0; y1<DIM1*DIM2; y1++)
            for (x1=0; x1<DIM1*DIM2; x1++)
              if (s[y1][x1] == 0) {
                s[y1][x1] = s2[y1][x1];
                result++;
              }
          goto search;
        }
        if (v==0) {
          printf("rule 5: s[%d][%d]=?\n", y,x);
          return -2;
        }
      revert:
        printf("revert: s[%d][%d]=0\n", y,x);
        return result;
      }
#endif /* BACKTRACKING */


  return result;
}

int main()
{
  int x,y,z;
  int s[DIM1*DIM2][DIM1*DIM2];

  for (y=0; y<DIM1*DIM2; y++)
    for (x=0; x<DIM1*DIM2; x++)
      s[y][x]=0,scanf(" %d", &s[y][x]);

  print(s);
  z=solve(s);
  printf("solve=>%d\n",z);
  print(s);
  z=check(s);
  printf("check=>%d\n",z);
  return z;
}