Skip to content

Instantly share code, notes, and snippets.

@t-asa2000
Created July 17, 2022 14:05
Show Gist options
  • Save t-asa2000/77a92686e39b81fabbcfc06f185ef849 to your computer and use it in GitHub Desktop.
Save t-asa2000/77a92686e39b81fabbcfc06f185ef849 to your computer and use it in GitHub Desktop.
Solve number place values (with Japanese comments) | ナンバープレイス(数独)の解読
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
// 数独解読プログラム
int np[9][9]; //数独表
int fixed[9][9]; //最初から数字が入っていた場合は1
// 数独表生成(空欄は0, 区切り文字はなしorカンマorスペース)
// 失敗した場合は1を返す
int input(void){
int i = 0,j;
char str[256];
char *c;
// 1行ずつ取得
for(;i<9;i++){
// 文字入力
c = fgets(str,sizeof str,stdin);
// 1文字ずつ取得
for(j = 0;j < 9;c++){
// 文字ポインタがNULLの場合
if(c == NULL) return 1;
// 区切り文字を識別
if(*c == ',' || *c == ' ') continue;
// '0'の文字コードを差し引いて数値に変換
np[i][j] = *c - '0';
if(np[i][j] < 0 || np[i][j] > 9) return 1;
// 空欄かどうか確認
fixed[i][j] = np[i][j] == 0 ? 0 : 1;
// jをインクリメント
j++;
}
}
// 成功した場合は0を返す
return 0;
}
// 結果を出力
void output(void){
int i=0,j;
for(;i < 9;i++){
for(j = 0;j < 9;j++) printf("%d ",np[i][j]);
printf("\n");
}
}
// 行・列・3x3に同じ数字がないか確認(行, 列)
int check(int row,int col){
int i=0,j;
// 3x3の上端
int r = row - (row % 3);
// 3x3の左端
int c = col - (col % 3);
// 行・列の確認
for(;i < 9;i++){
// 同じ数字があった場合
if(i != col && np[row][i] == np[row][col]) return 1; // 同じ行内を確認
if(i != row && np[i][col] == np[row][col]) return 1; // 同じ列内を確認
}
// 3x3の確認
for(i=r;i < r+3;i++){
for(j=c;j < c+3;j++){
// 基準となるマスを参照してる場合
if(i == row && j == col) continue;
// 同じ数字があった場合
if(np[i][j] == np[row][col]) return 1;
}
}
// 同じ数字がない場合
return 0;
}
// 数字を格納(行, 列)
int setnum(int row,int col){
// 要素番号を修正
row += col / 9;
col %= 9;
// 全てのマスを参照し終えた場合(解読成功)
if(row == 9) return 0;
// 最初から数字が入ったマスの場合
if(fixed[row][col] > 0) return setnum(row,col+1);
// 1から順に代入していく
for(np[row][col] = 1;np[row][col] <= 9;np[row][col]++){
// 数字が重複している場合は次の数字へ
if(check(row,col) > 0) continue;
// 次のマスへ移動(解読成功した場合は終了)
if(setnum(row,col+1) == 0) return 0;
}
// 解読失敗
return 1;
}
// メイン関数
int main(void){
// 数独表の生成(失敗したら終了)
if(input() > 0) return 1;
// 解読
int result = setnum(0,0);
// 結果を出力
result > 0 ? printf("解読不可\n") : output();
return result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment