/*ヘッダ関数の導入*/
#include  <stdio.h>
#include  <time.h>
/*マクロ定義*/
#define OK 1
#define ERROR 0
#define N 9                  /*盤のマスのサイズ*/
#define BLACK_NUM 20         /*配置される黒マスの個数*/
/*関数のプロトタイプ宣言*/
/*黒マスを配置する関数*/
int set_black(int *board);
/*引数のboard[row][rank]の上下左右に黒マスがないか調べる関数*/
int check_around(int row, int rank, int *board);
/*黒マス以外のところに正しい数字を配置する関数*/
int set_number(int *board);
/*盤board[row][rank]に配置しようとする数字numと同じ数字が同じタテまたはヨコの列にないかチェックする関数*/
int check_number(int *board, int num, int row, int rank);
/*黒マスのところに数字を配置する関数*/
void set_dummy_num(int *board);
/*回答盤boardのタテ，ヨコに同じ数字が重複していないかチェックする関数*/
int compare(int *board);
/*引数の盤boardの黒マスによって盤面が分断されていないかチェックする関数*/
int check_divide(int *board);
/*囲み分断をチェックする関数*/
int check_around_divide(int *board, int *check, int i, int j, int k);
/*端分断をチェックする関数*/
int check_edge_divide(int *board, int i, int j, int k, int l, int m);

/*メイン関数*/
main()
{
  int i, j, x;
  int row, rank;
  /*盤面をN*Nとし，二次元配列をそれぞれのマスに対応させる*/
    /*黒マスは0で表すものとする*/
    int answer[N][N];        /*正解盤*/
    int question[N][N];      /*問題盤*/
    int board[N][N];         /*回答盤*/
  /*毎回異なる問題が生成されるように乱数を用いる*/
  /*現在の時間をシードとして乱数列を生成*/ 
  srand(time(NULL));
  /*問題を生成する*/
  do {
    /*まず黒マスを配置する*/
    do {
      for(i=0;i<N;i++) 
        for(j=0;j<N;j++) 
          answer[i][j] = 10;
       x = set_black(&(answer[0][0]));
    } while(x==ERROR || check_divide(&(answer[0][0]))==ERROR);
    
    /*黒マス以外のところに正しい数字を配置する*/
    x = set_number(&(answer[0][0]));
  } while(x==ERROR);
  /*answer[N][N]の中身をquestion[N][N]にコピーする*/
  for(i=0;i<N;i++) 
    for(j=0;j<N;j++)
      question[i][j] = answer[i][j];
  /*黒マスのところにダミーの数字を配置する*/
  set_dummy_num(&(question[0][0]));
  /*問題を出力する*/
  for(i=0;i<N;i++) {
    for(j=0;j<N;j++) {
      printf("%d ", question[i][j]);
    }
    printf("\n");
  }
  /*問題を回答盤にコピーする*/
  for(i=0;i<N;i++) 
    for(j=0;j<N;j++) 
      board[i][j] = question[i][j];
  while(1) {
    printf("Input the place of the black!\n");
    printf("If row is i and rank is j,input:i j.\n");
    printf("When you give up, input :0 0.\n");
    scanf("%d %d",&row ,&rank);
    /*ギブアップする場合*/
    if (row == 0 && rank == 0) {
      printf("Never mind!\n");
      printf("An example of answer is\n");
      for(i=0;i<N;i++) {
        for(j=0;j<N;j++) {
          printf("%d ", answer[i][j]);
        }
        printf("\n");
      }
      return 0;
    }
    /*入力のエラーチェック*/
    else if(!(row>0 && rank>0 && row<=N && rank<=N)) {
      printf("Input correctly!\n");
      continue;
    }
    /*黒マスがタテ，ヨコに連続していないかのエラーチェック*/
    else if(check_around(row-1, rank-1, &(board[0][0])) == ERROR) {
      printf("The places of the black must not continue.\n");
      continue;
    }
    board[row-1][rank-1] = 0;
    /*黒マスによって盤面が分断されていないかのチェック*/
    if(check_divide(&(board[0][0]))==ERROR) {
      printf("The places of the black must not divide the board.\n");
      board[row-1][rank-1] = question[row-1][rank-1];
      continue;
    }
    /*現時点での盤の状態を出力する*/
    for(i=0;i<N;i++) {
      for(j=0;j<N;j++) {
        printf("%d ", board[i][j]);
      }
      printf("\n");
    }
    /*タテ列，ヨコ列に同じ数字が重複しなくなったら正解*/
    if(compare(&(board[0][0])) == OK) {
      printf("Conguratulation!!\n");
      return 0;
    }
  }
}

/*黒マスを配置する関数*/
int set_black(int *board)
{
  int i, j, a, x, y;
  /*BLACK_NUM個の黒マスが配置されるようにする*/
  for(i=0;i<BLACK_NUM;i++) {
    j = 0;
    do
    {
      /*0〜N*N-1の範囲で乱数を発生させる*/
      a = rand() % (N*N);
      x = a/N;
      y = a%N;
      j++;
      /*このdo-while文を100回繰り返しても終わらない場合は黒マスの配置をはじめからやり直す*/
      if(j==100) return ERROR;
    } while((check_around(x, y, board) == ERROR) || *(board+x*N+y)==0);
    *(board+x*N+y) = 0;
  }
  return OK;
}

/*board[row][rank]の上下左右に黒マスがないか調べる関数*/
/*上下左右に黒マスがない時はOKを返し，ある時はERRORを返す*/
int check_around(int row, int rank, int *board)
{
  int left, right, up, down;
  left = rank - 1;
  right = rank + 1;
  up = row - 1;
  down = row + 1;
  /*左右をチェック*/
  if(left >= 0) if(*(board+(row*N)+left) == 0) return ERROR;
  if(right <= N-1) if(*(board+(row*N)+right) == 0) return ERROR;
  /*上下をチェック*/
  if(up >= 0) if(*(board+(up*N)+rank) == 0) return ERROR;
  if(down <= N-1) if(*(board+(down*N)+rank) == 0) return ERROR;
  return OK;
}

/*黒マス以外のところに正しい数字を配置する関数*/
int set_number(int *board) 
{
  int i, j, k, num;
  for(i=0;i<N;i++) {
    for(j=0;j<N;j++) {
      if(*(board+i*N+j) != 0) {
        k = 0;
        do
        {
          /*1〜Nの範囲で乱数を発生させる*/
          num = rand() % N + 1;
          k++;
          /*このdo-while文を100回繰り返しても終わらない場合は黒マスの配置からやり直す*/
          if(k==100) return ERROR;
        } while(check_number(board, num, i, j) == ERROR);
        *(board+i*N+j) = num;
      }
    }
  }
  return OK;
}

/*board[row][rank]に配置しようとする数字numと同じ数字が同じタテまたはヨコの列にないかチェックする関数*/
/*同じタテまたはヨコの列に同じ数字がない時はOKを，ある時はERRORを返す*/
int check_number(int *board, int num, int row, int rank)
{
  int i;
  i=0;
  /*ヨコをチェック*/
  while(i<N) {
    if(i!=rank && num == *(board+row*N+i)) return ERROR;
    i++;    
  }
  /*タテをチェック*/
  i=0;
  while(i<N) {
    if(i!=row && num ==*(board+i*N+rank)) return ERROR;
    i++;
  }
  return OK;
}

/*黒マスのところにダミーの数字を配置する関数*/
void set_dummy_num(int *board)
{
  int i, j, m, n;
  /*黒マスのところをダミーの数字に変える*/
  for(i=0;i<N;i++) {
    for(j=0;j<N;j++) {
      if(*(board+i*N+j) == 0) {
        /*board[i][j]を含むタテの列からダミーの数字を作るか
        ヨコの行からダミーの数字を作るかを決める*/
        m = rand() % 2;
        if(m == 0) {
          /*ヨコの行からダミーの数字を作る場合*/
          do 
          {
            n = rand() % N;
          } while(n == j || *(board+i*N+n) == 0);
          *(board+i*N+j) = *(board+i*N+n);
        }
        if(m == 1) {
          /*タテの列からダミーの数字を作る場合*/
          do 
          {
            n = rand() % N;
          } while(n == i || *(board+n*N+j) == 0);
          *(board+i*N+j) = *(board+n*N+j);
        }
      }
    }
  }
}

/*盤boardのタテ，ヨコに同じ数字が重複していないかチェックする関数*/
/*重複があればERRORを，なければOKを返す*/
int compare(int *board)
{
  int i, j, k;
  /*ヨコの行を確認*/
  for(i=0;i<N;i++) 
    for(j=0;j<N;j++) 
      for(k=j+1;k<N;k++) 
        if(*(board+i*N+j)!=0 && *(board+i*N+j)==*(board+i*N+k)) 
                  return ERROR;
  /*タテの列を確認*/
  for(i=0;i<N;i++) 
    for(j=0;j<N;j++) 
      for(k=i+1;k<N;k++) 
        if(*(board+i*N+j)!=0 && *(board+i*N+j)==*(board+k*N+j)) 
                  return ERROR;
  return OK;
}

/*引数の盤boardの黒マスによって盤面が分断されていないかチェックする関数*/
int check_divide(int *board)
{
  /*分断を調べるために黒マスをチェックする配列を導入*/
  /*チェックされると１が入る*/
  int check[N][N];
  int i, j;
  /*チェック配列を０に初期化*/
  for(i=0;i<N;i++) 
    for(j=0;j<N;j++) 
            check[i][j] = 0;
  /*チェックしていない黒マスのみを調べる*/
  for(i=0;i<N;i++) 
    for(j=0;j<N;j++) 
      if(check[i][j]==0 && *(board+i*N+j)==0 
          && check_around_divide(board, &(check[0][0]), i, j, 0)==ERROR) 
             return ERROR;
  /*端の黒マスのみを調べる*/
  for(i=0;i<N;i++)
    for(j=0;j<N;j++) 
            if((i==0 || j==0 || i==N-1 || j==N-1) && *(board+i*N+j)==0 
                 && check_edge_divide(board, i, j, 0, i, j)==ERROR) 
                     return ERROR;
  return OK;
}

/*囲み分断をチェックする関数*/
/*引数に，調べる盤の配列の先頭ポインタ，今現在の場所i，j，来た方向kをとる*/
/*左上から右下への方向を１とする*/
/*右上から左下への方向を２とする*/
/*左下から右上への方向を３とする*/
/*右下から左上への方向を４とする*/
int check_around_divide(int *board, int *check, int i, int j, int k) 
{
  /*まず盤の範囲内かどうか調べる*/
  if(i>=0 && i<N && j>=0 && j<N) {
    /*この関数を再帰させて黒マスのつながりを調べていき，
      すでにチェックしてある黒マスに戻ってきたら囲み分断になっている*/
    if(*(check+i*N+j)==1) return ERROR;
    /*黒マスがあったらチェックして，周りを調べていく*/
    else if(*(board+i*N+j)==0 && *(check+i*N+j)==0) {
      *(check+i*N+j) = 1;
      if((i>0 && j>0) && (k!=1)) 
        if(check_around_divide(board, check, i-1, j-1, 4)==ERROR) 
          return ERROR;
      if((i>0 && j<N-1) && (k!=2)) 
        if(check_around_divide(board, check, i-1, j+1, 3)==ERROR) 
          return ERROR;
      if((i<N-1 && j>0) && (k!=3)) 
        if(check_around_divide(board, check, i+1, j-1, 2)==ERROR) 
          return ERROR;
      if((i<N-1 && j<N-1) && (k!=4)) 
        if(check_around_divide(board, check, i+1, j+1, 1)==ERROR) 
          return ERROR;
    }
  }
  return OK;
}

/*端分断をチェックする関数*/
/*引数に，調べる番の配列の先頭ポインタ，今現在の場所i，j，来た方向k，出発点l，mをとる*/
/*左上から右下への方向を１とする*/
/*右上から左下への方向を２とする*/
/*左下から右上への方向を３とする*/
/*右下から左上への方向を４とする*/
int check_edge_divide(int *board, int i, int j, int k, int l, int m)
{
  /*まず盤の範囲内かどうか調べる*/
  if(i>=0 && i<N && j>=0 && j<N) {
    /*出発点と異なる端にたどり着けば端分断になっている*/
    if(*(board+i*N+j)==0 && (i==0 || j==0 || i==N-1 || j==N-1) 
        && !(i==l && j==m)) return ERROR;
    /*黒マスがあったら，周りを調べていく*/
    else if(*(board+i*N+j)==0) {
      if((i>0 && j>0) && (k!=1)) 
        if(check_edge_divide(board, i-1, j-1, 4, l, m)==ERROR)
          return ERROR;
      if((i>0 && j<N-1) && (k!=2)) 
        if(check_edge_divide(board, i-1, j+1, 3, l, m)==ERROR)
          return ERROR;
      if((i<N-1 && j>0) && (k!=3))
        if(check_edge_divide(board, i+1, j-1, 2, l, m)==ERROR)
          return ERROR;
      if((i<N-1 && j<N-1) && (k!=4)) 
        if(check_edge_divide(board, i+1, j+1, 1, l, m)==ERROR)
          return ERROR;
    }
  }
  return OK;
}