数独を解くアルゴリズム
バックトラック法で解いているのですが、どこがおかしいのか見当もつかないので教えてください。
コンパイルエラーはありません。
表示の関数は省いてあります。
よろしくお願いします。
#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;
}
お礼
Color color1 = bmp[0]->GetPixel(m + ys, n + xs); r1 = color1.R; g1 = color1.G; b1 = color1.B; Color color2 = bmp[0]->GetPixel(m + ys, n + xs); r2 = color2.R; g2 = color2.G; b2 = color2.B; Color color3 = bmp[0]->GetPixel(m + 1 + ys, n + xs); r3 = color3.R; g3 = color3.G; b3 = color3.B; Color color4 = bmp[0]->GetPixel(m + 1 + ys, n + 1 + xs); r4 = color4.R; g4 = color4.G; b4 = color4.B; r = (int)(((1.0 - q) * (1.0 - p) * r1) + (p * r2) + (q * (1.0 - p) * r3) + p * r4); g = (int)(((1.0 - q) * (1.0 - p) * g1) + (p * g2) + (q * (1.0 - p) * g3) + p * g4); b = (int)(((1.0 - q) * (1.0 - p) * b1) + (p * b2) + (q * (1.0 - p) * b3) + p * b4); }else{ r = 0; g = 0; b = 0; } if(r < 0){r = 0;} if(g < 0){g = 0;} if(b < 0){b = 0;} if(r > 255){r = 255;} if(g > 255){g = 255;} if(b > 255){b = 255;} Color newColor = Color::FromArgb( r, g, b ); pic->SetPixel(i + ys * 2, j + xs * 2, newColor ); } 教えてもらったことと同じような感じですが、上記のようにやってみた結果うまくいきました。ありがとうございます。 それと、(m >= -ys)&&(m < ys - 1)&&(n >= -xs)&&(n < xs - 1)の部分なのですが、-1とは何のことだったのでしょう? 線形補間された画像の右と下に線があわられてしまいました。(_|のような感じ) -1を消したら何もでなくなりましたが。 SetPixel/GetPixel以外にも画素配置の方法があるということなので、調べてみます。本当にありがとうございました。