プログラマ専用SNS ミクプラ

はじめまして今c言語を使って数独を自動で回答するプログラムを作成しています。あるアルゴリズムの作成で困っています。
たとえば、以下のようなボックス（3*3のスペース）があったとします
-----
|870|
|490|
|530|
-----
このようになっていた場合、このボックス以外の空欄(0=空欄)の列にあるマスには[1,2,6]を入れることができません。
・・・このようなアルゴリズムを実装したいのですがどのようにすればいいかご教授していただきたいです。

下記は今まで出作成したプログラムです。

コード:

#include<stdio.h>
#include <windows.h>
#include <time.h>
void yokocheck(int suudoku[10][10][10]);
void tatecheck(int suudoku[10][10][10]);
void boxcheck(int suudoku[10][10][10]);
void botticheck(int suudoku[10][10][10]);
void show(int suudoku[10][10][10]);
void oneboxonespace(int suudoku[10][10][10]);
void suudokusyokika(int suudoku[10][10][10]);
int main(void){
	int i,j,k;
	int suudoku[10][10][10];
	int yf[81],xf[81],syokiti[81];
	suudokusyokika(suudoku);
	i=0;
	while(1){
	/*	printf("初期値(y,x,入れたい値)を入力して下さい\n");
		printf("入力が終了したら -1 と入力して下さい\n");*/
		scanf("%d %d %d",&yf[i],&xf[i],&syokiti[i]);
		if(yf[i]==-1) break;
		i++;
	}
	clock_t start,end;
	start = clock();
	for(j=0;j<i;j++) suudoku[yf[j]][xf[j]][0]=syokiti[j];
	for(i=0;i<10;i++){　/*このfor文はいずれ「答えが出るまで」ループする予定です*/
		show(suudoku);	//現在の確定している数字を表示
		yokocheck(suudoku);	//全てのx軸の候補を削除
		tatecheck(suudoku);	//全てのy軸の候補を削除
		boxcheck(suudoku);	//box内に確定している数字がある時、ボックス内の他のマスの候補を削減する
		botticheck(suudoku);	//一つのマスに入れることができる数字の候補が一つしかないとき、確定させる
		oneboxonespace(suudoku); //一ボックスに一マスのみ入れることができる数字があるとき、確定させる
		for(j=4;j<=6;j++){
			for(k=7;k<=9;k++){
				printf("%d ",suudoku[j][k][9]);
			}
		}
		printf("\n");
	}
	printf("\n");
	end = clock();
	printf("%.2f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC);
	return 0;
}
void yokocheck(int suudoku[10][10][10]){
	int i,j,k;
	for(i=1;i<=9;i++){
		for(j=1;j<=9;j++){
			if(suudoku[i][j][0]!=0){
				for(k=0;k<=9;k++){
					suudoku[i][k][suudoku[i][j][0]]=0;
				}
			}
		}
	}
}
void tatecheck(int suudoku[10][10][10]){
	int i,j,k;
	for(j=1;j<=9;j++){
		for(i=1;i<=9;i++){
			if(suudoku[i][j][0]!=0){
				for(k=0;k<=9;k++){
					suudoku[k][j][suudoku[i][j][0]]=0;
				}
			}
		}
	}
}
void boxcheck(int suudoku[10][10][10]){
	int i,j,k,l,xziku,yziku;
	for(i=1;i<=9;i++){
		for(j=1;j<=9;j++){
			if(suudoku[i][j][0]>=1){
				if(i<=3) yziku=1;
				else if(i<=6) yziku=4;
				else yziku=7;
				if(j<=3) xziku=1;
				else if(j<=6) xziku=4;
				else xziku=7;
				for(k=yziku;k<=yziku+2;k++){
					for(l=xziku;l<=xziku+2;l++){
						suudoku[k][l][suudoku[i][j][0]]=0;
					}
				}
			}
		}
	}
}
void botticheck(int suudoku[10][10][10]){
	int i,j,k,cnt;
	for(i=1;i<=9;i++)
		for(j=1;j<=9;j++){
			if(suudoku[i][j][0]!=0);
			else {
				cnt=0;
				for(k=1;k<=9;k++) if(suudoku[i][j][k]==1) cnt++; 
				if(cnt==1) {
					for(k=1;k<=9;k++) if(suudoku[i][j][k]==1) suudoku[i][j][0]=k;
				}
			}
		}
}
void show(int suudoku[10][10][10]){
	int i,j;
	printf("\n");
	for(i=1;i<=9;i++){
		for(j=1;j<=9;j++){
			printf("%d",suudoku[i][j][0]);
			if(j%3==0 && j!=9) printf("|");
		}
		printf("\n");
		if(i%3==0 && i!=9) printf("------------\n");
	}
	printf("\n");
}
void oneboxonespace(int suudoku[10][10][10]){
	int i,j,k,l,m,xziku,yziku,cnt[10];
	for(i=1;i<=9;i+=3){
		for(j=1;j<=9;j+=3){	
			for(l=1;l<=9;l++) cnt[l]=0;	
			for(m=1;m<=9;m++) {			//調べたい数字
				for(k=i;k<=i+2;k++){	//1ボックスの中で調べる
					for(l=j;l<=j+2;l++){
						if(suudoku[k][l][0]==m) {
							cnt[m]=-1;
							break;
						}
						else if(suudoku[k][l][m]==1 && suudoku[k][l][0]==0) cnt[m]++; 
					}
					if(cnt[m]==-1) break;
				}
				if(cnt[m]==1){
					for(k=i;k<=i+2;k++){	//1ボックスの中で調べる
						for(l=j;l<=j+2;l++){
							if(suudoku[k][l][m]==1 && suudoku[k][l][0]==0) suudoku[k][l][0]=m;
						}
					}
				}
			}	
		}
	}
}
void suudokusyokika(int suudoku[10][10][10]){
	int i,j,k;
	for(i=0;i<=9;i++){
		for(j=0;j<=9;j++){
			suudoku[i][j][0]=0;
			for(k=1;k<=9;k++)suudoku[i][j][k]=1;
		}
	}
}

配列の[0]を使わないことで可読性を上げているんですね。なるほど。

9x9のマスの1/3～1/2が埋まっていない状態からスタートするとすると、総当たり法では解き終われないと思います。
人間が解くように、穴の数の少ないところから埋めていって、巡回させるんじゃないかと思いますが、そのプログラムが果たして300行程度で収まるかはちょっと想像がつかないです。

このCのプログラムはきちんと解きに行っていると思います。

https://github.com/rg3/sudoku/blob/master/sudoku.c

283行のコメントを見ると総当たりに近い解き方みたいですね。

総当たりなら 40行程度できます。

コード:

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

char b[9][9], k;

void print(void)
{
    printf("\n");
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++) printf("%c%c", b[i][j], " \n"[j==8]);
}

int ok(int n, int x, int y)
{
    for (int i = 0; i < 9; i++)
        if (b[x][i] == n || b[i][y] == n) return 0;
    for (int i = x / 3 * 3, j = y / 3 * 3, k = 0; k < 3; k++)
        if (b[i][j+k] == n || b[i+1][j+k] == n || b[i+2][j+k] == n) return 0;
    return 1;
}

void step(int i, int j)
{
    if (j == 9) j = 0, i++;
    if (i == 9) print(), ++k == 2 && (exit(0), 0);
    else if (b[i][j] != ' ') step(i, j+1);
    else for (char c = '1'; c <= '9'; c++)
        ok(c, i, j) && (b[i][j] = c, step(i, j+1), b[i][j] = ' ');
}

int main(void)
{
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++) {
            if (scanf(" %c", &b[i][j]) != 1) return puts("input error"), 1;
            if (b[i][j] < '0' || b[i][j] > '9') b[i][j] = ' ';
        }
    step(0, 0);
    return 0;
}

入力データ(スペースや改行は省略可)

コード:

 . . 5 3 . . . . .
 8 . . . . . . 2 .
 . 7 . . 1 . 5 . .
 4 . . . . 5 3 . .
 . 1 . . 7 . . . 6
 . . 3 2 . . . 8 .
 . 6 . 5 . . . . 9
 . . 4 . . . . 3 .
 . . . . . 9 7 . .

実行結果

コード:

1 4 5 3 2 7 6 9 8
8 3 9 6 5 4 1 2 7
6 7 2 9 1 8 5 4 3
4 9 6 1 8 5 3 7 2
2 1 8 4 7 3 9 5 6
7 5 3 2 9 6 4 8 1
3 6 7 5 4 2 8 1 9
9 8 4 7 6 1 2 3 5
5 2 1 8 3 9 7 6 4

かずまさん、さすがです。

コードが少し技巧的だったので、初心者向けの書き方にして、コメントを追加しました。
しかしアルゴリズムの美しさに感心します。

コード:

#include <stdio.h>

int board[9][9];
const int NIL = 0; // 分かっていない数

// 分かっていない数('.')毎に1～9の数字を当てはめてチェックする再帰関数
// boardに正解が格納されていれば、TRUE(0以外)を返す。
// 答えが見つからなければ0を返す。
int step(int i, int j) {
	if (i == 9) return 1; // 「10行目」に到達したので、正解を発見
	
	// 数字が入っていない場合は、1～9の数字を当てはめてチェックする
	if (board[i][j] == NIL) {
		for (int k = 1; k <= 9; k++) {
			int isOk = 1;
			board[i][j] = k;
			for (int l = 0; l < 9; l++) {
				if (l != j && board[i][l] == k) isOk = 0; // 行チェック
				if (l != i && board[l][j] == k) isOk = 0; // 列チェック
			}
			// ブロックチェック
			int starti = i - i % 3;
			int startj = j - j % 3;
			for (int l = 0; l < 3; l++) {
				for (int m = 0; m < 3; m++) {
					int curi = starti + l;
					int curj = startj + m;
					if (curi == i && curj == j) continue;
					if (board[curi][curj] == k) isOk = 0;
				}
			}
			if (!isOk) continue;
			// 次のステップに進む
			int nexti = (j == 8) ? (i + 1) : i;
			int nextj = (j + 1) % 9;
			if (step(nexti, nextj)) return 1; // もし正解なら1を返す
		}
		// 1～9の全てで失敗した場合は、数字をNILに戻して、0を返す
		board[i][j] = NIL;
		return 0; // 1～9の全てで失敗した場合は、0を返す
	}

	// 数字が入っている場合は、そのまま次のステップに進む
	int nexti = (j == 8) ? (i + 1) : i;
	int nextj = (j + 1) % 9;
	return step(nexti, nextj);
}

int main() {

	// 標準入力の読み取り
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			unsigned char c;
			scanf(" %c", &c);
			if (c == '.')
				board[i][j] = NIL;
			else if (c >= '1' && c <= '9')
				board[i][j] = (int)(c - '0');
			else {
				printf("入力が不正です。\n");
				return 1;
			}
		}
	}

	// 問題を解く
	if (step(0, 0)) {
		// 答えが正解であれば、現在のボードを表示
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				printf("%d", board[i][j]);
				if (j < 8) printf(" ");
				else printf("\n");
			}
		}
	} else {
		// 答えが正解でなければ（答えが見つからなければ）、それを通知
		printf("この問題の解はありません。\n");
	}
	return 0;
}

再帰関数をループに直したバージョンです。
コードの見た目はすっきりしましたが、（再帰関数を知っている人にとっては）多少わかりづらくなっていると思います。

コード:

#include <stdio.h>

int board_init[9][9]; // ボード（最初の状態）
int board[9][9];
const int NIL = 0; // 分かっていない数


// 現在のボード(board)について、位置(i, j)のマスの数字が
// 周りの数字(縦・横・ブロック)と重複していないかチェックする関数
// 重複していなければTRUE(0以外), 重複していれば0を返す
int check(int i, int j) {
	int board_ij = board[i][j];
	
	for (int k = 0; k < 9; k++) {
		if (k != j && board[i][k] == board_ij) return 0; // 行チェック
		if (k != i && board[k][j] == board_ij) return 0; // 列チェック
	}
	// ブロックチェック
	int starti = i - i % 3;
	int startj = j - j % 3;
	for (int l = 0; l < 3; l++) {
		for (int m = 0; m < 3; m++) {
			int curi = starti + l;
			int curj = startj + m;
			if (curi == i && curj == j) continue;
			if (board[curi][curj] == board_ij) return 0;
		}
	}
	return 1;
}

// ボードのステップ(i, j)をインクリメントする
void incr_step(int *i, int *j) {
	int nexti = (*j == 8) ? *i + 1 : *i;
	int nextj = (*j + 1) % 9;
	*i = nexti;
	*j = nextj;
}

// ボードのステップ(i, j)をデクリメントする
void decr_step(int *i, int *j) {
	int nexti = (*j == 0) ? *i - 1 : *i;
	int nextj = (*j == 0) ? 8 : *j - 1;
	*i = nexti;
	*j = nextj;
}

// 分かっていない数('.')毎に1～9の数字を当てはめてチェックする関数
// boardに正解が格納されていれば、TRUE(0以外)を返す。
// 答えが見つからなければ0を返す。
int solve() {
	int i = 0;
	int j = 0;
	
	// ステップ(i, j)がボードの外に出るまでループ
	while (i < 9 && i >= 0) {
		if (board_init[i][j] != NIL) {
			// 元々数字が入っていた場合は、そのまま次のステップに進む
			incr_step(&i, &j);
		}
		else if (board[i][j] == NIL) {
			// 数字が入っていなかった場合は、1を当てはめて、チェックする
			board[i][j] = 1;
			if (check(i, j))
				incr_step(&i, &j);
		}
		else if (board[i][j] != 9) {
			// 数字が最後の数字でないときは、数字をインクリメントして、チェックする
			board[i][j]++;
			if (check(i, j))
				incr_step(&i, &j);
		}
		else {
			// 数字が最後の数字のときは、数字を元に戻して、ステップを戻す
			while (i >= 0 && (board_init[i][j] != NIL || board[i][j] == 9)) {
				board[i][j] = board_init[i][j];
				decr_step(&i, &j);
			}
		}
	}
	
	if (i == 9) return 1; // ステップが「10行目」になったときは、正解なので1を返す
	return 0; // ステップが「0行目」になったときは、正解が見つからなかったので0を返す
}

int main() {

	// 標準入力の読み取り
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			unsigned char c;
			scanf(" %c", &c);
			if (c == '.')
				board[i][j] = NIL;
			else if (c >= '1' && c <= '9')
				board[i][j] = (int)(c - '0');
			else {
				printf("入力が不正です。\n");
				return 1;
			}
		}
	}
	
	// ボードのコピー
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
			board_init[i][j] = board[i][j];
	
	// 問題を解く
	if (solve()) {
		// 答えが正解であれば、現在のボードを表示
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				printf("%d", board[i][j]);
				if (j < 8) printf(" ");
				else printf("\n");
			}
		}
	} else {
		// 答えが正解でなければ（答えが見つからなければ）、それを通知
		printf("この問題の解はありません。\n");
	}
	return 0;
}

プログラマ専用SNS ミクプラ

数独のアルゴリズム

数独のアルゴリズム

Re: 数独のアルゴリズム

Re: 数独のアルゴリズム

Re: 数独のアルゴリズム

Re: 数独のアルゴリズム

Re: 数独のアルゴリズム