#include<stdio.h>
//読み込むファイルはテキストファイルで、内容は例えば以下のようなものです。
//25.|.3.|9.1
//.1.|..4|...
//4.7|...|268
//---+---+---
//..5|2.1|..6
//...|.98|1..
//.4.|..3|...
//---+---+---
//...|36.|.72
//.7.|...|..3
//923|...|614
//「+」「-」「|」は枠で、「.」は空白を表します。数字は任意ですが、形式はこのようなものです。
//書きこむ形式もこれに則ります。
//盤面データ構造体
struct sudoku_t{
int cell[9][9];
};
//盤面をすべて「空白」にする関数
void sudoku_clear(struct sudoku_t *s){
int i,j;
for(i=0;i<=8;i++){
for(j=0;j<=8;j++){
s->cell[i][j] = 0777;
}
}
}
//マス(r, c)の値を取得する関数
int sudoku_get(const struct sudoku_t *s, int r, int c)
{
if (s->cell[r][c] == 0001){return 1;}
else if(s->cell[r][c] == 0002){return 2;}
else if(s->cell[r][c] == 0004){return 3;}
else if(s->cell[r][c] == 0010){return 4;}
else if(s->cell[r][c] == 0020){return 5;}
else if(s->cell[r][c] == 0040){return 6;}
else if(s->cell[r][c] == 0100){return 7;}
else if(s->cell[r][c] == 0200){return 8;}
else if(s->cell[r][c] == 0400){return 9;}
else{return 0;}
}
//盤面を数独形式で出力する関数
void sudoku_write(const struct sudoku_t *s, FILE *fp){
if (fp == NULL){
fprintf(stderr,"cannot open for writing\n");
fclose(fp);
}
else{
int r,c;
for(r=0;r<=8;r++){
for(c=0;c<=8;c++){
if(sudoku_get(s,r,c)==0){fprintf(fp,".");}
else if(sudoku_get(s,r,c)!=0){fprintf(fp,"%d",sudoku_get(s,r,c));}
if((c==2)||(c==5)){fprintf(fp,"|");}
else if(c==8){fprintf(fp,"\n");}
}
if((r==2)||(r==5)){fprintf(fp,"---+---+---\n");}
}
}
}
//盤面を数独形式で入力する関数
void sudoku_read(struct sudoku_t *s, FILE *fp) {
if (fp == NULL){
fprintf(stderr,"cannot open for reading\n");
fclose(fp);
}
else{
int r,c,fg;
r=0;
c=0;
while((fg=fgetc(fp))!=EOF){
switch (fg) {
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
s->cell[r][c] = (1 << (fg - '1'));
break;
case '.':
s->cell[r][c] = 0777;
break;
default:
continue;
break;
}
c++;
if(c >= 9){
c=0;
r++;
if (r >= 9) {
break;
}
}
}
}
}
//(r,c)に数字kは入らないとする関数
int sudoku_kill(struct sudoku_t *s, int r, int c, int k) {
if ((s->cell[r][c] & ~(0001 << (k-1))) != s->cell[r][c]) {
(s->cell[r][c]) = (((s->cell[r][c])) & ( ~(0001 << (k-1)) ) );
return 1;
}
else {return 0;}
}
//制約1(横列に同じ数が入らない制約)によりほかのマスの状態数を変更する関数
int sudoku_kill_col(struct sudoku_t *s, int r, int c){
int k,r1;
int n=0;
for(k=1;k<=9;k++){
if((s->cell[r][c]) == (0001 <<(k-1))){
for(r1=0;r1<=8;r1++){
if(r1==r){continue;}
if(sudoku_kill(s,r1,c,k)==1){n++;}
}
}
}
return n;
}
//制約2(縦行に同じ数が入らない制約)~
int sudoku_kill_row(struct sudoku_t *s, int r, int c){
int k,c1;
int n=0;
for(k=1;k<=9;k++){
if((s->cell[r][c]) == (0001 <<(k-1))){
for(c1=0;c1<=8;c1++){
if(c1==c){continue;}
if(sudoku_kill(s,r,c1,k)==1){n++;}
}
}
}
return n;
}
//制約3(同ブロックに同じ数が入らない制約)~
int sudoku_kill_block(struct sudoku_t *s, int r, int c){
int r11,r12,r13,c11,c12,c13,r21,r22,r23,c21,c22,c23,r31,r32,r33,c31,c32,c33;
int k,n;
n=0;
for(k=1;k<=9;k++){
if((s->cell[r][c]) == (0001 <<(k-1))){
if(r>=0 && r<=2){
if(c>=0 && c<=2){ //ブロック11
for(r11=0;r11<=2;r11++){
for(c11=0;c11<=2;c11++){
if(s->cell[r11][c11] == s->cell[r][c]){continue;}
if(sudoku_kill(s,r11,c11,k)){n++;}
}
}
}
if(c>=3 && c<=5){ //ブロック12
for(r12=0;r12<=2;r12++){
for(c12=3;c12<=5;c12++){
if(s->cell[r12][c12] == s->cell[r][c]){continue;}
if(sudoku_kill(s,r12,c12,k)){n++;}
}
}
}
if(c>=6 && c<=8){ //ブロック13
for(r13=0;r13<=2;r13++){
for(c13=6;c13<=8;c13++){
if(s->cell[r13][c13] == s->cell[r][c]){continue;}
if(sudoku_kill(s,r13,c13,k)){n++;}
}
}
}
}
if(r>=3 && r<=5){
if(c>=0 && c<=2){ //ブロック21
for(r21=3;r21<=5;r21++){
for(c21=0;c21<=2;c21++){
if(s->cell[r21][c21] == s->cell[r][c]){continue;}
if(sudoku_kill(s,r21,c21,k)){n++;}
}
}
}
if(c>=3 && c<=5){ //ブロック22
for(r22=3;r22<=5;r22++){
for(c22=3;c22<=5;c22++){
if(s->cell[r22][c22] == s->cell[r][c]){continue;}
if(sudoku_kill(s,r22,c22,k)){n++;}
}
}
}
if(c>=6 && c<=8){ //ブロック23
for(r23=3;r23<=5;r23++){
for(c23=6;c23<=8;c23++){
if(s->cell[r23][c23] == s->cell[r][c]){continue;}
if(sudoku_kill(s,r23,c23,k)){n++;}
}
}
}
}
if(r>=6 && r<=8){
if(c>=0 && c<=2){ //ブロック31
for(r31=6;r31<=8;r31++){
for(c31=0;c31<=2;c31++){
if(s->cell[r31][c31] == s->cell[r][c]){continue;}
if(sudoku_kill(s,r31,c31,k)){n++;}
}
}
}
if(c>=3 && c<=5){ //ブロック32
for(r32=6;r32<=8;r32++){
for(c32=3;c32<=5;c32++){
if(s->cell[r32][c32] == s->cell[r][c]){continue;}
if(sudoku_kill(s,r32,c32,k)){n++;}
}
}
}
if(c>=6 && c<=8){ //ブロック33
for(r33=6;r33<=8;r33++){
for(c33=6;c33<=8;c33++){
if(s->cell[r33][c33] == s->cell[r][c]){continue;}
if(sudoku_kill(s,r33,c33,k)){n++;}
}
}
}
}
}
}
return n;
}
int main(int argc, char *argv[]){
FILE *fin = NULL;
FILE *fout = NULL;
struct sudoku_t s;
sudoku_clear(&s);// 初期化
fin = fopen(argv[1],"r");//入力数独ファイルを開く処理
sudoku_read(&s, fin); // 盤面データを読み込む
fclose(fin);//入力ファイル fin を閉じる処理
int r0,c0,n0;
while(n0!=0){ //変更するマスが無くなったら終了
n0=0;
for(r0=0;r0<=8;r0++){
for(c0=0;c0<=8;c0++){
sudoku_kill_col(&s,r0,c0);
sudoku_kill_row(&s,r0,c0);
sudoku_kill_block(&s,r0,c0);
n0 = n0 + sudoku_kill_col(&s,r0,c0) + sudoku_kill_row(&s,r0,c0) + sudoku_kill_block(&s,r0,c0);
}
}
}
fout = fopen(argv[2],"w"); //出力数独ファイルを開く処理
sudoku_write(&s, fout); //盤面データを書き込む
fclose(fout);// 出力ファイル fout を閉じる処理
sudoku_write(&s, stdout);
return 0;
}