#include <stdio.h>
#define N 3
#define N2 N*N
#define N3 N*N*N
#define N4 N2*N2
 
// global
const int n2 = N2;
const int n3 = N3;
const int n4 = N4;
char board[N4 + 1];
char candidate[N4][N2 + 2];
 
// prototype
void initialize();
int continueCheck();
void printBoard();
void decideAll();
void spread(int);
 
void candidatePrint()
{
  int i;
  for (i = 0; i < n4; ++i)
    if (board[i] == ' ')printf("candidate[%d] = %s\n", i, candidate[i]);
}
 
void initialize()
{
  int i;
  printBoard();
  for (i = 0; i < n4; ++i)
    sprintf(candidate[i], " 123456789" );
  for (i = 0; i < n4; ++i)
    if (board[i] > '0')
      spread(i);
}
 
int continueCheck()
{
  char *s = board;
  printBoard();
  for (s = board; *s; ++s)
    if (*s < '0') return 1;
  return 0;
}
 
void printBoard()
{
  int i = 0;
  char *x = board;
  printf("\n------------------");
  for (; *x; ++i, ++x) {
    if (i % n2 == 0)putchar('\n');
    printf("%c ", *x);
  }
  printf("\n------------------");
}
 
void decideAll()
{
  int i, count;
  char *s, w;
  for (i = 0; i < n4; ++i) {
    if (board[i] != ' ')continue;
    // count candidate chars
    for (s = candidate[i], count = 0; *s; ++s) {
      if (*s != ' ') {
        w = *s;
        ++count;
      }
    }
    if (count == 1) {
      board[i] = w;
      spread(i);
    }
  }
}
 
void spread(const int n)
{
  int i, j, ii, jj, w;
  w = board[n] - '0';
  // horizontal
  i = n / n2;
  for (j = 0; j < n2; ++j)
    candidate[i * n2 + j ][w] = ' ';
  // vertical
  j = n % n2;
  for (i = 0 ; i < n2; ++i)
    candidate[i * n2 + j ][w] = ' ';
  // local
  for (i = n / n2 / N * N, ii = 0; ii < N; ++i, ++ii) {
    for (j = n % n2 / N * N, jj = 0; jj < N; ++j, ++jj) {
      candidate[i * n2 + j][w] = ' ';
    }
  }
}
 
int main()
{
  sprintf(board,
          "53  7    " \
          "6  195   " \
          " 98    6 " \
          "8   6   3" \
          "4  8 3  1" \
          "7   2   6" \
          " 6    28 " \
          "   419  5" \
          "    8  79"
         );
  initialize();
  do {
    decideAll();
  } while (continueCheck());
 
  return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNkZWZpbmUgTiAzCiNkZWZpbmUgTjIgTipOCiNkZWZpbmUgTjMgTipOKk4KI2RlZmluZSBONCBOMipOMgoKLy8gZ2xvYmFsCmNvbnN0IGludCBuMiA9IE4yOwpjb25zdCBpbnQgbjMgPSBOMzsKY29uc3QgaW50IG40ID0gTjQ7CmNoYXIgYm9hcmRbTjQgKyAxXTsKY2hhciBjYW5kaWRhdGVbTjRdW04yICsgMl07CgovLyBwcm90b3R5cGUKdm9pZCBpbml0aWFsaXplKCk7CmludCBjb250aW51ZUNoZWNrKCk7CnZvaWQgcHJpbnRCb2FyZCgpOwp2b2lkIGRlY2lkZUFsbCgpOwp2b2lkIHNwcmVhZChpbnQpOwoKdm9pZCBjYW5kaWRhdGVQcmludCgpCnsKICBpbnQgaTsKICBmb3IgKGkgPSAwOyBpIDwgbjQ7ICsraSkKICAgIGlmIChib2FyZFtpXSA9PSAnICcpcHJpbnRmKCJjYW5kaWRhdGVbJWRdID0gJXNcbiIsIGksIGNhbmRpZGF0ZVtpXSk7Cn0KCnZvaWQgaW5pdGlhbGl6ZSgpCnsKICBpbnQgaTsKICBwcmludEJvYXJkKCk7CiAgZm9yIChpID0gMDsgaSA8IG40OyArK2kpCiAgICBzcHJpbnRmKGNhbmRpZGF0ZVtpXSwgIiAxMjM0NTY3ODkiICk7CiAgZm9yIChpID0gMDsgaSA8IG40OyArK2kpCiAgICBpZiAoYm9hcmRbaV0gPiAnMCcpCiAgICAgIHNwcmVhZChpKTsKfQoKaW50IGNvbnRpbnVlQ2hlY2soKQp7CiAgY2hhciAqcyA9IGJvYXJkOwogIHByaW50Qm9hcmQoKTsKICBmb3IgKHMgPSBib2FyZDsgKnM7ICsrcykKICAgIGlmICgqcyA8ICcwJykgcmV0dXJuIDE7CiAgcmV0dXJuIDA7Cn0KCnZvaWQgcHJpbnRCb2FyZCgpCnsKICBpbnQgaSA9IDA7CiAgY2hhciAqeCA9IGJvYXJkOwogIHByaW50ZigiXG4tLS0tLS0tLS0tLS0tLS0tLS0iKTsKICBmb3IgKDsgKng7ICsraSwgKyt4KSB7CiAgICBpZiAoaSAlIG4yID09IDApcHV0Y2hhcignXG4nKTsKICAgIHByaW50ZigiJWMgIiwgKngpOwogIH0KICBwcmludGYoIlxuLS0tLS0tLS0tLS0tLS0tLS0tIik7Cn0KCnZvaWQgZGVjaWRlQWxsKCkKewogIGludCBpLCBjb3VudDsKICBjaGFyICpzLCB3OwogIGZvciAoaSA9IDA7IGkgPCBuNDsgKytpKSB7CiAgICBpZiAoYm9hcmRbaV0gIT0gJyAnKWNvbnRpbnVlOwogICAgLy8gY291bnQgY2FuZGlkYXRlIGNoYXJzCiAgICBmb3IgKHMgPSBjYW5kaWRhdGVbaV0sIGNvdW50ID0gMDsgKnM7ICsrcykgewogICAgICBpZiAoKnMgIT0gJyAnKSB7CiAgICAgICAgdyA9ICpzOwogICAgICAgICsrY291bnQ7CiAgICAgIH0KICAgIH0KICAgIGlmIChjb3VudCA9PSAxKSB7CiAgICAgIGJvYXJkW2ldID0gdzsKICAgICAgc3ByZWFkKGkpOwogICAgfQogIH0KfQoKdm9pZCBzcHJlYWQoY29uc3QgaW50IG4pCnsKICBpbnQgaSwgaiwgaWksIGpqLCB3OwogIHcgPSBib2FyZFtuXSAtICcwJzsKICAvLyBob3Jpem9udGFsCiAgaSA9IG4gLyBuMjsKICBmb3IgKGogPSAwOyBqIDwgbjI7ICsraikKICAgIGNhbmRpZGF0ZVtpICogbjIgKyBqIF1bd10gPSAnICc7CiAgLy8gdmVydGljYWwKICBqID0gbiAlIG4yOwogIGZvciAoaSA9IDAgOyBpIDwgbjI7ICsraSkKICAgIGNhbmRpZGF0ZVtpICogbjIgKyBqIF1bd10gPSAnICc7CiAgLy8gbG9jYWwKICBmb3IgKGkgPSBuIC8gbjIgLyBOICogTiwgaWkgPSAwOyBpaSA8IE47ICsraSwgKytpaSkgewogICAgZm9yIChqID0gbiAlIG4yIC8gTiAqIE4sIGpqID0gMDsgamogPCBOOyArK2osICsramopIHsKICAgICAgY2FuZGlkYXRlW2kgKiBuMiArIGpdW3ddID0gJyAnOwogICAgfQogIH0KfQoKaW50IG1haW4oKQp7CiAgc3ByaW50Zihib2FyZCwKICAgICAgICAgICI1MyAgNyAgICAiIFwKICAgICAgICAgICI2ICAxOTUgICAiIFwKICAgICAgICAgICIgOTggICAgNiAiIFwKICAgICAgICAgICI4ICAgNiAgIDMiIFwKICAgICAgICAgICI0ICA4IDMgIDEiIFwKICAgICAgICAgICI3ICAgMiAgIDYiIFwKICAgICAgICAgICIgNiAgICAyOCAiIFwKICAgICAgICAgICIgICA0MTkgIDUiIFwKICAgICAgICAgICIgICAgOCAgNzkiCiAgICAgICAgICk7CiAgaW5pdGlhbGl6ZSgpOwogIGRvIHsKICAgIGRlY2lkZUFsbCgpOwogIH0gd2hpbGUgKGNvbnRpbnVlQ2hlY2soKSk7CgogIHJldHVybiAwOwp9Cg==