#include <stdio.h>
#include <stdlib.h>
#include <string>
#define KARA 12
#define OK 0
#define NG -1
#define CANCEL 1
#define TRUE 1
#define FALSE 0

char Mondai_Nyuryoku(char d[9][9]);
int Kaitou_Sakusei(char Doku[9][9]);
void Input_Jun(char d[9][9]);
void Input_Line(char d[9][9],int i);
int Check_D(char d[9][9],bool hyoji);
void Doku_Kakunin(char d[9][9],char *msg);
int LineIsTrue(char d[9][9],char Line);
int RayIsTrue(char d[9][9],char Ray);
int PartIsTrue(char d[9][9],char Part);

struct BBB{
	char boku;
	char Num;
};

int main(void)
{
  char Doku[9][9];
  char work[32];
  bool loop=TRUE ,loop2=TRUE, fff=FALSE;
  char lp=0;

  for(int i=0;i<9;i++){
	  for(int j=0;j<9;j++){
		  Doku[i][j]=KARA;
	  }
  }
  while(loop2){
  printf("////////////////////////////////////////////////////\n");
  printf("\t\t―――数独解答作成プログラム Ver 1.03\n");
  printf("////////////////////////////////////////////////////\n");
  while(loop){
	printf("#メニューを選択してください。(1,2,3)\n");
	printf(" 1.問題入力\n");
	printf(" 2.解答作成\n");
	printf(" 3.終了\n");
	printf(">");
	work[0]='\0';
	scanf("%s",work);
	if(strlen(work)!=1){
		printf("ERROR:入力桁数が不正。\n\n");
		loop=TRUE;
	}
	else if(strspn(work,"123")!=strlen(work)){
		printf("ERROR:メニュー番号以外が入力された。\n\n");
		loop=TRUE;
	}
	else loop=FALSE;
  }
  switch(work[0]){
  case '1':
	  lp=Mondai_Nyuryoku(Doku);
	  loop2=TRUE;
	  loop=TRUE;
	  fff=TRUE;
	  break;
  case '2':
	  if(fff==FALSE){
		  printf("#問題が入力されていません。\n");
		  printf("\n");
	  }
	  else if(lp==0){
		  Kaitou_Sakusei(Doku);
	  }
	  else{
		  printf("#問題に数字の重なりがあります。\n");
		  printf("#問題入力から、入力し直してください。\n");
		  printf("\n");
	  }
	  loop2=TRUE;
	  loop=TRUE;
	  break;
  case '3':
	  loop2=FALSE;
	  break;
  }
  }
  return 0;
}

int Kaitou_Sakusei(char Doku[9][9]){
  unsigned int YokoKa[9];
  unsigned int TateKa[9];
  unsigned int KukakuKa[9];
  unsigned int ca=0;
  unsigned int da=0;
  da=~da;
  printf("【2】解答作成 ―――――――――――――――――――\n");

  for(int i=0;i<9;i++){
	  YokoKa[i]=0;
	  TateKa[i]=0;
	  KukakuKa[i]=0;
  }
  //YOKOKAの設定
  for(int i=0;i<9;i++){
	  for(int j=0;j<9;j++){
		  if(Doku[i][j]==KARA){
			  continue;
		  }
		  ca|=1<<(Doku[i][j]-1);
	  }
	  ca=~ca;
	  ca&=~(da<<9);
	  YokoKa[i]=ca;
	  ca=0;
  }
  //TATEKAの設定
  for(int i=0;i<9;i++){
	  for(int j=0;j<9;j++){
		  if(Doku[j][i]==KARA){
			  continue;
		  }
		  ca|=1<<(Doku[j][i]-1);
	  }
	  ca=~ca;
	  ca&=~(da<<9);
	  TateKa[i]=ca;
	  ca=0;
  }
  //KUKAKUKAの設定
  for(int i=0;i<9;i++){
	  for(int j=((i/3)*3);j<((i/3)*3+3);j++){
		  for(int k=((i%3)*3);k<((i%3)*3+3);k++){
			  if(Doku[j][k]==KARA){
				  continue;
			  }
			  ca|=1<<(Doku[j][k]-1);
		  }
	  }
	  ca=~ca;
	  ca&=~(da<<9);
	  KukakuKa[i]=ca;
	  ca=0;
  }
  struct BBB BA[81];
  char cnt=0;
  for(char i=0;i<81;i++){
	  BA[cnt].Num=0;
	  if(Doku[i/9][i%9]==KARA){
		  BA[cnt].boku=i;
		  cnt++;
	  }
  }
  int j=0;
  int k=0;
  int tate=0;
  int yoko=0;
  int Kukaku=0;
  unsigned int kano=0;
  int u;
  int kon=0;
  for(u=0;u<cnt;u++){
	  yoko=BA[u].boku%9;
	  tate=BA[u].boku/9;
	  Kukaku=((tate/3)*3)+(yoko/3);
	  kano=(YokoKa[tate]&TateKa[yoko])&KukakuKa[Kukaku];
	  for(j=BA[u].Num;j<9;j++){
		  unsigned int pp=0;
		  pp|=(1<<j);
		  if(!(kano&pp)){
			  continue;
		  }
		  else{
			  if(BA[u].Num){
				  YokoKa[tate]|=(1<<(BA[u].Num-1));
				  TateKa[yoko]|=(1<<(BA[u].Num-1));
				  KukakuKa[Kukaku]|=(1<<(BA[u].Num-1));
				  //選択可能数を加える。
			  }

			 BA[u].Num=j+1;
			 YokoKa[tate]&=~(pp);
			 TateKa[yoko]&=~(pp);
			 KukakuKa[Kukaku]&=~(pp);
			 break;
		  }
	  }

	  if(j==9){
		  if(BA[u].Num){
				  YokoKa[tate]|=(1<<(BA[u].Num-1));
				  TateKa[yoko]|=(1<<(BA[u].Num-1));
				  KukakuKa[Kukaku]|=(1<<(BA[u].Num-1));
				  //選択可能数を加える。
		  }
		  if(!u){
			  printf("\n#答え無し。問題文のミスが考えられます。\n");
			  printf("\n");
			  return NG;
		  }
			  BA[u].Num=0;
			  //yokoka,tateka,kukakukaのリセット
			  u-=2;
			  //少し戻って、可能範囲の訂正、更新
	  }
  }
  int f=0;
  printf("\t 【解答】\t 【問題】\n");
  for(int i=0;i<9;i++){
	  printf("\t");
	  for(j=0;j<9;j++){
		  if(Doku[i][j]==KARA){
			  printf("%d",BA[f].Num);
			  f++;
		  }
		  else{
			  printf("%d",Doku[i][j]);
		  }
		  if(j==2 || j==5){
			printf("|");
		  }
	  }
	  printf("\t");
	  for(j=0;j<9;j++){
		  if(Doku[i][j]==KARA){
			  printf(" ");
		  }
		  else{
			  printf("%d",Doku[i][j]);
		  }
		  if(j==2 || j==5){
			  printf("|");
		  }
	  }
	  printf("\n");
	  if(i==2||i==5){
		printf("\t---+---+---\t---+---+---\n");
	  }
	}
  ///////////////////////////////////////////////
  int s;
  for(s=0;s<999;s++){
    for(int i=cnt-1;i<cnt;i++){
	  yoko=BA[i].boku%9;
	  tate=BA[i].boku/9;
	  Kukaku=((tate/3)*3)+(yoko/3);
	  kano=(YokoKa[tate]&TateKa[yoko])&KukakuKa[Kukaku];
	  for(j=BA[i].Num;j<9;j++){
		  unsigned int pp=0;
		  pp|=(1<<j);
		  if(!(kano&pp)){
			  continue;
		  }
		  else{
			  if(BA[i].Num){
				  YokoKa[tate]|=(1<<(BA[i].Num-1));
				  TateKa[yoko]|=(1<<(BA[i].Num-1));
				  KukakuKa[Kukaku]|=(1<<(BA[i].Num-1));
				  //選択可能数を加える。
			  }
			 BA[i].Num=j+1;
			 YokoKa[tate]&=~(pp);
			 TateKa[yoko]&=~(pp);
			 KukakuKa[Kukaku]&=~(pp);
			 break;
		  }
	  }
	  if(j==9){
		  if(BA[i].Num){
				  YokoKa[tate]|=(1<<(BA[i].Num-1));
				  TateKa[yoko]|=(1<<(BA[i].Num-1));
				  KukakuKa[Kukaku]|=(1<<(BA[i].Num-1));
				  //選択可能数を加える。
		  }
		  if(!i){
			  goto SOTO;
			  break;
		  }
		  else{
			  BA[i].Num=0;
			  //yokoka,tateka,kukakukaのリセット
			  i-=2;
			  //少し戻って、可能範囲の訂正、更新
		  }
	  }
	 }
  }
SOTO:
  printf("\n");
  if(s==0){
	  printf("#この解答が唯一です。\n");
  }
  else if(s==999){
	  printf(" 注:解答は全部で1000通り以上あります。\n");
  }
  else{
	  printf(" 注:解答は全部で%d通りあります。\n",s);
  }
	/////////////////////////////////////////
  printf("\n");
  return 0;
}

char Mondai_Nyuryoku(char d[9][9]){
	char work[32];
	bool loop1=TRUE,loop2=TRUE;
while(loop2){
	while(loop1){
		printf("【1】問題入力 ―――――――――――――――――――\n");
		printf("#入力メニューを選択してください。(1,2,3,4)\n");
		printf(" 1:1行ずつ順に入力\n");
		printf(" 2:指定した1行を入力\n");
		printf(" 3:入力の確認\n");
		printf(" 4:入力の完了\n");
		printf(">");
		work[0]='\0';
		scanf("%s",work);
		if(strlen(work)!=1){
			printf("ERROR:入力桁数が不正。\n\n");
			loop1=TRUE;
		}
		else if(strspn(work,"1234")!=strlen(work)){
			printf("ERROR:指定された番号以外が入力された。\n\n");
			loop1=TRUE;
		}
		else loop1=FALSE;
	}
	loop1=TRUE;
	switch(work[0]){
	case '1':
		Input_Jun(d);
		break;
	case '2':
		while(loop1){
			printf("#何行目を入力しますか？(1-9)\n");
			printf(">");
			work[0]='\0';
			scanf("%s",work);
			if(strlen(work)!=1){
				printf("ERROR:入力桁数が不正。\n\n");
				loop1=TRUE;
			}
			else if(strspn(work,"123456789")!=strlen(work)){
				printf("ERROR:(1-9)番号以外が入力された。\n\n");
				loop1=TRUE;
			}
			else loop1=FALSE;
		}
		Input_Line(d,atoi(&work[0]));
		break;
	case '3':
		Doku_Kakunin(d,"#登録された問題は下記の通りです。");
		Check_D(d,TRUE);
		break;
	case '4':
		char l=0;
		if((l=Check_D(d,FALSE))!=0){
			printf("ERROR:%d個の数字の重なりがあります。\n",l);
			printf("#メニューに戻りますが、このままでは解答を作成できません。\n");
		}
		return l;
	}
	loop1=TRUE;
}
return 0;
}

void Input_Jun(char d[9][9]){
	char cach[2];
	cach[2]='\0';
	char work[32];
	for(int i=1;i<10;i++){
		printf("#%d行目を入力してください。(例:290704180) 0:空欄 e:入力中止(1-9,0,e)\n",i);
		printf(">");
    work[0]='\0';
    scanf("%s",work);
    if(work[0]=='e'||work[0]=='E'){
      return;
    }
    if(strlen(work)!=9){
      printf("ERROR:入力文字数が9でありません。\n");
      i--;
      continue;
    }
    else if(strspn(work,"1234567890")!=9){
      printf("ERROR:1-9,0以外が入力されました。\n");
      i--;
      continue;
    }
    else{
      for(int j=0;j<9;j++){
		if(work[j]=='0'){
			d[i-1][j]=KARA;
		}
		else{
			cach[0]=work[j];
			d[i-1][j]=atoi(cach);
		}
	  }
	}
  }
	printf("#全ての行の入力が終わりました。\n");
	printf("\n");
	return;
}

void Input_Line(char d[9][9],int i){
	char work[32];
	bool loop=TRUE;
	char cach[2];
	cach[2]='\0';

	printf("#第%d行目の現在の値は次の通りです。0:空欄\n",i);
	printf("【旧】 ");
	for(int j=0;j<9;j++){
		if(d[i-1][j]==KARA)printf("0");
		else printf("%d",d[i-1][j]);
	}
	printf("\n");

	while(loop){
		printf("#第%d行を入力してください。(例:290704180) 0:空欄 e:変更しない(1-9,0,e)\n",i);
	printf("【新】 ");
	work[0]='\0';
	scanf("%s",work);
	if(strlen(work)==1 && (work[0]=='e' || work[0]=='E')){
		return;
	}
	if(strlen(work)!=9){
		printf("ERROR:入力桁数が不正。\n\n");
		loop=TRUE;
	}
	else if(strspn(work,"1234567890")!=strlen(work)){
		printf("ERROR:(1-9,0)以外が入力された。\n\n");
		loop=TRUE;
	}
	else loop=FALSE;
	}
	for(int j=0;j<9;j++){
		if(work[j]=='0'){
			d[i-1][j]=KARA;
		}
		else{
			cach[0]=work[j];
			d[i-1][j]=atoi(cach);
		}
	}
	printf("#%d行目の変更が完了しました。\n",i);
	printf("\n");
	return;
}

int Check_D(char d[9][9],bool hyoji){
	char chk=0;
	char error_num=0;

	for(int i=0;i<9;i++){
		if((chk=LineIsTrue(d,i))!=OK){
			if(hyoji)printf("Error:第%d行に重なりがあります。\n",chk);
			error_num++;
		}
	}
	for(int i=0;i<9;i++){
		if((chk=RayIsTrue(d,i))!=OK){
			if(hyoji)printf("Error:第%d列に重なりがあります。\n",chk);
			error_num++;
		}
	}
	for(int i=0;i<9;i++){
		if((chk=PartIsTrue(d,i))!=OK){
			if(hyoji)printf("Error:縦%dx横%d 小区画に重なりがあります。\n",(chk-1)/3+1,(chk-1)%3+1);
			error_num++;
		}
	}
	printf("\n");

	return error_num;
}
void Doku_Kakunin(char d[9][9],char *msg){
	printf(msg);
	printf("\n\n");
	    for(int i=0;i<9;i++){
			printf(" ");
      for(int j=0;j<9;j++){
		  if(d[i][j]==KARA){
			  printf(" ");
		  }
		  else{
			  printf("%d",d[i][j]);
		  }
		if(j==2 || j==5){
			printf("|");
		}
      }
	  printf("\n");
	  if(i==2||i==5){
		printf(" ");
		printf("---+---+---\n");
	  }
    }
}
int Kakunin_Msg(char *msg){
	int loop=TRUE;
	char work[12];

	while(TRUE){
		while(loop){
			printf(msg);
			printf("?(Y/N)\n>");
			work[0]='\0';
			scanf("%s",work);
			if(strlen(work)!=1){
				printf("入力エラーです。\n");
			}
			else{
				loop=FALSE;
			}
		}
		switch(work[0]){
		case 'Y':
		case 'y':
			return OK;
			break;
		case 'N':
		case 'n':
			return NG;
			break;
		default:
			printf("入力エラーです。\n");
			break;
		}
    }
}
//重なりが無かったらOK(0)あったら、行番号(1~9を返す)
int LineIsTrue(char d[9][9],char Line){
	unsigned int flg=0;
	unsigned int store=0;
	int i;
	for(i=0;i<9;i++){
		if(d[Line][i]==KARA){
			continue;
		}
		else{
			flg^=(0x01<<(d[Line][i]-1));
			if((flg&store)==store){   //OK
				store=flg;
			}
			else{
				return Line+1;
			}
		}
	}
	return OK;
}

//重なりが無かったらOK(0)あったら、列番号(1~9を返す)
int RayIsTrue(char d[9][9],char Ray){
	unsigned int flg=0;
	unsigned int store=0;
	int i;
	for(i=0;i<9;i++){
		if(d[i][Ray]==KARA){
			continue;
		}
		else{
			flg^=(0x01<<(d[i][Ray]-1));
			if((flg&store)==store){   //OK
				store=flg;
			}
			else{
				return Ray+1;
			}
		}
	}
	return OK;
}

//重なりが合ったらOK(0)あったら、小区画番号(1~9)を返す。
int PartIsTrue(char d[9][9],char Part){
	char Yoko,Tate;
	unsigned int flg=0;
	unsigned int store=0;
	Yoko=Part%3;
	Tate=Part/3;
	for(char i=Yoko*3;i<Yoko*3+3;i++){
		for(char j=Tate*3;j<Tate*3+3;j++){
			if(d[j][i]==KARA){
				continue;
			}
			else{
				flg^=(0x01<<(d[j][i]-1));
					if((flg&store)==store){   //OK
						store=flg;
					}
					else{
						return Part+1;
					}
			}
		}
	}
	return OK;
}