#define ARDUINO=1


// JUST define for Arduino
// sd6 takes approx 7 sec on Arduino
#if defined(ARDUINO)
#define II char
#else
#define II int
#endif // ARDUINO


#if defined (ARDUINO)
#else
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#endif
#define SIZE 9

// #define BUG
volatile int level = 0;
volatile int actLevel=0;
int iter=0,elimCnt=0,totElimCnt;

int nrTests=0;

//#define ARDUINO

#ifdef ARDUINO
#define PSTR(x) Serial.print(x)
#define PNL(x) Serial.println("")
#define PI(x) Serial.print( (int)x)
#else
#define PSTR(x) printf("%s",x)
#define PNL(x) printf("\n")
#define PI(x) printf("%i",x)
#endif // ARDUINO

#if defined(ARDUINO)
struct soduko {
  II sdk[SIZE][SIZE]= {
    {
      8,0,0,0,0,0,0,0,0    }
    ,
    {
      0,0,3,6,0,0,0,0,0    }
    ,
    {
      0,7,0,0,9,0,2,0,0    }
    ,
    {
      0,5,0,0,0,7,0,0,0    }
    ,
    {
      0,0,0,0,4,5,7,0,0    }
    ,
    {
      0,0,0,1,0,0,0,3,0    },
    {
      0,0,1,0,0,0,0,6,8    }
    ,
    {
      0,0,8,5,0,0,0,1,0    }
    ,
    {
      0,9,0,0,0,0,4,0,0,    }
  };

  II xholes[SIZE*SIZE];
  II yholes[SIZE*SIZE];
  II nrHoles;
};
#else
struct soduko {
  II sdk[SIZE][SIZE];
  II xholes[SIZE*SIZE];
  II yholes[SIZE*SIZE];
  II nrHoles;
};

#endif
struct soduko first,bup;

#ifdef ARDUINO
long startT,stopT;
int maxloop=1;
#else
int maxloop=1000;
clock_t startT,stopT;
#endif // ARDUINO

#ifdef ARDUINO
void loop() {
}
#endif

void sdkInit()
{
#ifdef ARDUINO
  Serial.begin(9600);
#else
#endif // ARDUINO
}


#if defined(ARDUINO)
void rd(void)
{


}
#else
//read soduko from file format 9 linies 1 2
void rd(void)
{
  char str[100],*ss;
  II i,j;
  for (i=0; i < SIZE; i++) {
    gets(str); // ved godt den er giftig hvis linie er aaalt for lang
    ss = strtok(str," ");
    first.sdk[i][0] = atoi(ss);
    for (j=1; j < SIZE; j++) {
      ss = strtok(NULL," ");
      first.sdk[i][j] = atoi(ss);
    }
  }
}

#endif

void dmpHoles(void)
{
  II i;
  PSTR("nr holes ");
  PI(first.nrHoles);
  PSTR("\n");
  if (first.nrHoles) {
    for (i=0; i < first.nrHoles; i++) {
      PSTR("(");
      PI(first.xholes[i]);
      PSTR(",");
      PI(first.yholes[i]);
      PSTR(") ");
    }
    PSTR("\n");
  }
}
void dmpSoduko ()
{
  II i, j;
  PSTR("-------------------\n");

  for (i = 0; i < SIZE; i++) {
    for (j = 0; j < SIZE; j++) {

      PI(first.sdk[i][j]);
      PSTR(" ");
      if ((j + 1) % 3 == 0) {
        PSTR(" ");
      }
    }
    PNL(0);
    if ((i + 1) % 3 == 0) {
      PNL(0);
    }
  }
}


II countVacant()
{
  II i,j,c;
  c = 0;

  for (i=0; i< SIZE; i++) {
    for (j=0; j < SIZE; j++) {
      if (first.sdk[i][j] == 0) {
        first.xholes[c] = i;
        first.yholes[c] = j;
        c++;
      }
    }
  }
  first.nrHoles = c;
  return (c);
}

// is number in row ?
II inRow(II number, II rowNr)
{
  II i;
  for (i=0; i < SIZE; i++) {
    if (first.sdk[rowNr][i] == number)
      return 1; // fundet
  }
  return 0; // ikke fundet
}

// is number in column ?
II inCol(II number, II colNr)
{
  II i;
  for (i=0; i < SIZE; i++) {
    if (first.sdk[i][colNr] == number)
      return 1; // fundet
  }
  return 0; // ikke fundet
}

II in3x3(II val,II x, II y)
{
  II i,j;
  // find upper left corner for travelling
  x = 3*(x/3);
  y = 3*(y/3);
  for (i=x; i < 3+x; i++) {
    for (j=y; j < 3+y; j++) {
      if (first.sdk[i][j] == val)
        return 1;	// found
    }
  }
  return 0; // not in 3x3
}

// will val fit on locat ion x,y ?
II
chkLegal (II val, II x, II y)
{
  II i, j, k, l;

  if (inRow(val,x))
    return 0;

  if (inCol(val,y))
    return 0;

  if (in3x3(val,x,y))
    return 0;

  return 1; // ok - not found
}

int cntLegalIn3x3(II val, II kvadrat, II *xpos, II *ypos)
{
  // kvadrat 0..9
  int cnt=0, i,j,x,y;
  // x and y in upper left
  x = 3*(kvadrat/3);
  y = 3*(kvadrat % 3);

  if (! in3x3(val,x,y)) {

    for (i=x; i < 3+x; i++) {
      for (j=y; j < 3+y; j++) {
        if (first.sdk[i][j] == 0) {  // must no be populated
          if (chkLegal(val,i,j)) {
            cnt ++;
            *xpos = i;
            *ypos = j;
          }
        }
      }
    }
  }
  return cnt; // how many places val is valid in 3x3
}

void elimFirst()
{
  II v,k,x,y;

  totElimCnt=0;
  do {
    level = countVacant();
    elimCnt=0;

    for (k=0; k < SIZE; k++) {
      for (v=1; v < SIZE+1; v++) {
        if ( 1 == cntLegalIn3x3(v,k,&x,&y)) {
          elimCnt++;
          first.sdk[x][y] = v;
        }
      }
    }
    totElimCnt+=elimCnt;
  }
  while (elimCnt);
}


void calcExeTime()
{
#ifdef ARDUINO
  Serial.print("exe time ");
  Serial.println(stopT-startT);
#else
  printf("%6.2f(msec) exection time for %i solves\n",(float)(  (stopT-startT)/1000.0), maxloop );
  printf("%i nr of iterations\n",iter);
  printf("%2.2f usec/iteration\n", (float)( (100.0*(stopT-startT))/(100.0*iter) ));
#endif // ARDUINO
}

II
chk ()
{
  II ii, jj, k,res;

  iter++; // just for statistics
  if (actLevel == level )
    return 0;  // all seats occupied so we are finished

  // find a vacant place
  ii = first.xholes[actLevel];
  jj = first.yholes[actLevel];

  // lets try 1-9 on vacant place
  for (k=1; k < SIZE+1; k++) {
    if (chkLegal (k, ii, jj)) {
      first.sdk[ii][jj] = k; // let us try

      actLevel++;
      res =  chk (); // i,j bq no need to srch for vacant from start every time
      actLevel--;

      if (res == 0) { // yes :-)
        //*s = sWrk; // let us bring it back
        return 0;
      }
    }
  }
  first.sdk[ii][jj] = 0; // reset
  return -1; // no legal values
}


#if defined( ARDUINO)
void setup(void)
#else
int
main (void)
#endif // ARDUINO
{
  II res,l;


  sdkInit();
  rd(); // rd from std input

  dmpSoduko();


  bup = first;
  level = countVacant();
  PSTR("Vacant seats ");
  PI(level);
  PNL();

#ifdef ARDUINO
  startT = millis();
#else
  startT = clock();
#endif // ARDUINO

  for (l=0; l< maxloop; l++) {
    first = bup;
    level = countVacant();
    actLevel=0;
    iter=0;
    res = chk ();
  }

#ifdef ARDUINO
  stopT = millis();
#else
  stopT = clock();
#endif // ARDUINO
  dmpSoduko ();
  PSTR("Solved (0 = yes) ");
  PI(res);
  PNL();

  calcExeTime();

#ifdef ARDUINO
  startT = millis();
#else
  startT = clock();
#endif // ARDUINO

  for (l=0; l< maxloop; l++) {
    first = bup;
    elimFirst();
    actLevel=0;
    iter=0;
    res = chk ();
  }

#ifdef ARDUINO
  stopT = millis();
#else
  stopT = clock();
#endif // ARDUINO
  dmpSoduko ();
  PSTR("eliminations: ");
  PI(totElimCnt);
  PNL();
  PSTR("Solved (0 = yes) ");
  PI(res);
  PNL();


  calcExeTime();

}