数独を解くアルゴリズム
バックトラック法で解いているのですが、どこがおかしいのか見当もつかないので教えてください。
コンパイルエラーはありません。
表示の関数は省いてあります。
よろしくお願いします。
#include <stdio.h>
#define M 3 //小さいブロックのサイズ
#define N M*M //全体のサイズ
#define MTX N*N //全体のマス数
int sudoku[N][N]={
{0,2,4,5,0,0,6,0,0},
{0,0,6,3,2,0,0,0,4},
{0,0,5,0,9,0,0,8,3},
{0,0,8,4,0,3,0,0,1},
{0,6,1,9,0,0,4,3,0},
{7,0,0,1,0,0,5,0,0},
{8,3,0,0,4,0,9,0,0},
{4,0,0,0,3,5,8,0,0},
{0,0,7,0,0,9,3,4,0}
};
/* 候補がOKかどうかチェック */
int OKkouho(int x, int y, int k)
{
int i,j;
int p,q;
for(i=0; i < N; i++){ //その行に候補は入るか
if(sudoku[y][i] == k)
return 0;
}
for(j=0; j < N; j++){ //その列に候補は入るか
if(sudoku[j][x] == k)
return 0;
}
p = x/M*M;
q = y/M*M;
//そのブロックに候補は入るか
for(j = q; j < q+M; j++){
for(i = p; i < p+M; i++){
if(sudoku[j][i] == k)
return 0;
}
}
return 1;
}
void Solve(int level)
{
int k;
int x,y;
if(level >= MTX){
printf("OK");
return;
}
x = level%N;
y = level/N;
if(sudoku[y][x])
Solve(level+1);
else{
for(k = 1; k <= N; k++){
if(OKkouho(x,y,k)){
sudoku[y][x] = k;
Solve(level+1);
sudoku[y][x] = 0;
}
}
}
}
int main(void)
{
Solve(0);
return 0;
}
