数独を解くアルゴリズム

質問

バックトラック法で解いているのですが、どこがおかしいのか見当もつかないので教えてください。
コンパイルエラーはありません。
表示の関数は省いてあります。
よろしくお願いします。

#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;
}

回答No.1

himajin100000

#include <stdio.h>
#define M 3 //小さいブロックのサイズ
#define N (M*M) //全体のサイズ
#define MTX (N*N) //全体のマス数

//あっているかわからないが，とりあえずsudokuに設定されている
//データでは
/*
3,2,4,5,8,1,6,9,7,
9,8,6,3,2,7,1,5,4,
1,7,5,6,9,4,2,8,3,
2,9,8,4,5,3,7,6,1,
5,6,1,9,7,2,4,3,8,
7,4,3,1,6,8,5,2,9,
8,3,2,7,4,6,9,1,5,
4,1,9,2,3,5,8,7,6,
6,5,7,8,1,9,3,4,2,
*/
//という結果が求まった。

//念のために括弧で括ってみた。
//個人的な見易さの関係で一行ではなく複数行でif文を記述している
//また，普通はしないだろうが，やっぱり気になるのでif(Solve(level+1))とせず
//1と比較している。

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[i][y] == k){
return 0;
}
}

for(j=0; j < N; j++){ //その列に候補は入るか
if(sudoku[x][j] == k){
return 0;
}
}

p = x/M*M;
q = y/M*M;

//そのブロックに候補は入るか
for(i = p; i < p+M; i++){
for(j = q; j < q+M; j++){
if(sudoku[i][j] == k){
return 0;
}
}
}

return 1;
}

int Solve(int level) //戻り値をvoidからintにしてみた。各所で戻り値を設定。
{
int k;
int x,y;

if(level >= MTX){
printf("OK\n");
return 1;
}

x = level % N;
y = level / N;

if(sudoku[x][y] != 0){
if (Solve(level+1) == 1){
printf("skipped:%d,%d,%d\n",x,y);
return 1;
}

}else{
for(k = 1; k <= N; k++){
if(OKkouho(x,y,k) == 1){
sudoku[x][y] = k;
if(Solve(level+1) == 1){
printf("succeed:%d,%d,%d\n",x,y,k);
return 1;
}else{
printf("failed:%d,%d,%d\n",x,y,k);
sudoku[x][y] = 0;
}
}else{
printf("failed:%d,%d,%d\n",x,y,k);
}
}
return 0;
}

}

int main(void)
{
//どうもsudoku[y][x]でなくsudoku[x][y]でいいっぽい。
//最初から入力データが間違っていた場合については考慮していない。
if (Solve(0) == 1){
ShowAnswer();
}else{
printf("no answer!");
}
return 0;
}

int ShowAnswer(){
int i;
int j;
for (i = 0;i<N;i++){
for(j = 0;j<N;j++){
printf("%d,",sudoku[i][j]);
}
printf("\n");
}

return 1;
}