/* -------------------------- *
 * ナンプレの解答を全探索で
 * 求めるプログラム
 * 2014/09/05
 * -------------------------- */

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

#define TRUE 0
#define FALSE 1

//１つのブロックの１辺のマスの数
#define SSIZE 3
#define SIZE (SSIZE*SSIZE)

void usage(char *progName);
int solve_nan(char *dataFileName);
void print_bd(int *board);
int find(int *board, int pos);
int check(int *board, int pos, int num);

int main(int argc, char *argv[])
{
  int i;
  
  if(argc < 2)
  {
    usage(argv[0]);
    return FALSE;
  }
  
  for(i = 1; i < argc; i++)
  {
    if( solve_nan(argv[i]) == FALSE )
      return FALSE;
  }
  
  return TRUE;
}

void usage(char *progName)
{
  printf(
    "使用方法\n"
    "%s \"data file name\"\n",
    progName);
}

//問題を格納したファイル名を指定すると
//そのファイルを読み込み解き始める
int solve_nan(char *dataFileName)
{
  int x, y, number, rFlug;
  FILE *fp;
  int *board;
  
  // --------------------
  // 初期化処理
  // --------------------
  rFlug = TRUE;
  fp = NULL;
  board = NULL;
  
  if( (fp = fopen(dataFileName, "r")) == NULL)
  {
    printf("Cannot open data file![%s]\n", dataFileName);
    rFlug = FALSE;
    goto quit;
  }
  
  if( (board = (int *)calloc(SIZE*SIZE, sizeof(int))) == NULL)
  {
    printf("Cannot allocate memory![board]\n");
    rFlug = FALSE;
    goto quit;
  }
  
  // --------------------
  // 問題データの読み込み
  // --------------------
  while(fscanf(fp,"%d %d %d",&x, &y, &number) != EOF)
  {
    x--; y--; //配列の表現に合わせるために数値を1だけ減らす
    board[SIZE*x + y] = number;
  }
  
  print_bd(board);
  
  if( find(board, 0) == FALSE )
  {
    rFlug = FALSE;
    goto quit;
  }
  
  //結果
  printf("\n\n");
  print_bd(board);
  
quit:
  if( fp != NULL) fclose(fp);
  if( board != NULL) free(board);
  return rFlug;
}

//ナンプレの盤面を表示する関数
void print_bd(int *board)
{
  int i, j;
  
  for(i = 0; i < SIZE; i++)
  {
    for(j = 0; j < SIZE; j++)
    {
      if(board[SIZE*i + j] == 0)
        printf("  /");
      else
        printf("%3d", board[SIZE*i + j]);
      if(j%SSIZE == (SSIZE - 1))
        printf(" ");
    }
    printf("\n");
    if(i%SSIZE == (SSIZE - 1))
      printf("\n");
  }
}

//最初にpos = 0でこの関数を呼び出すと全探索を開始する
//解答が見つかると TRUE を返り値として返す。
int find(int *board, int pos)
{
  int i;
  
  //すべてのマスが埋まった時
  if(pos >= SIZE*SIZE)
    return TRUE;
  
  //数字が存在すれば次のマスへ移動する
  if(board[pos])
  {
    if( find(board, pos + 1) == TRUE)
      return TRUE;
  }
  else //数字が存在しない場合は矛盾しない数値を入れて次へ進む
  {
    for(i = 1; i <= SIZE; i++)
    {
      if( check(board, pos, i) == TRUE)
      {
        //置けるのであれば数値を代入して次のマスへ
        board[pos] = i;
        if( find(board, pos + 1) == TRUE)
          return TRUE;
        
        board[pos] = 0;
      }
    }
  }
  
  return FALSE;
}

//配列の場所posに数値numが矛盾せずに入るかどうかを確かめる関数
int check(int *board, int pos, int num)
{
  int x, y, i, j;
  
  x = pos%SIZE;
  y = pos/SIZE;
  
  //行と列に数値numが存在しないか確かめる
  for(i = 0; i < SIZE; i++)
  {
    if(board[SIZE*y + i] == num)
      return FALSE;
    if(board[SIZE*i + x] == num)
      return FALSE;
  }
  
  x /= SSIZE;
  x *= SSIZE;
  y /= SSIZE;
  y *= SSIZE;
  
  //ブロックSSIZE×SSIZEの範囲に数値numが存在しないか確かめる
  for(i = 0; i < SSIZE; i++)
    for(j = 0; j < SSIZE; j++)
    {
      if(board[SIZE*(y + i) + (x + j)] == num)
        return FALSE;
    }
  
  return TRUE;
}