バックトラック法で解いているのですが、どこがおかしいのか見当もつかないので教えてください。
コンパイルエラーはありません。
表示の関数は省いてあります。
よろしくお願いします。
#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;
}
A 回答 (1件)
- 最新から表示
- 回答順に表示
No.1
- 回答日時:
#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;
}
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題の説明、各所ごとに 5 2023/07/26 11:03
- C言語・C++・C# C 言語の Gauss Jordan 法について 2 2022/12/28 11:16
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# c言語でユーザ関数を利用して入力された文字列を反転させるプログラムを作りたいです。 3 2023/01/29 19:47
- C言語・C++・C# C言語のエラーについて 2 2022/07/11 13:56
- C言語・C++・C# C言語の課題が出たのですが自力でやっても分かりませんでした。 要素数がnであるint型の配列v2の並 3 2022/11/19 17:41
- C言語・C++・C# C言語でif文が予想と違う動きをする件について7 4 2023/03/20 00:26
- C言語・C++・C# 質問です 下記のコードを分かりやすく解説お願いします 初心者です #include ‹stdio.h 3 2022/05/26 22:03
- C言語・C++・C# c言語 プログラムのエラー 1 2023/02/11 20:31
- C言語・C++・C# プログラミングの授業の課題です 1 2023/01/17 22:15
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語での引数の省略方法
-
「指定されたキャストは有効で...
-
#define _CRT_SECURE_NO_WARNIN...
-
C言語 エラーの原因がわからな...
-
課題でつまってます・・・
-
複数桁10進数の*桁目だけを抽出...
-
数字列を3桁ごとにカンマで区切...
-
配列v2を逆順にしてv1に格納す...
-
double型の値を、一桁ずつint型...
-
C言語の配列をC++のvectorに高...
-
if と配列の組み合わせ
-
【C++】関数ポインタの使い方
-
ラップ関数とはどんなものですか?
-
このプログラミング誰か教えて...
-
Win32APIで作るコンボボックス...
-
卒業研究でよく分からないとこ...
-
C#のコンパイルエラーCS0120に...
-
C言語についてです。
-
c言語の配列を使ってサイコロを...
-
(int *)の意味
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
C言語での引数の省略方法
-
#define _CRT_SECURE_NO_WARNIN...
-
「指定されたキャストは有効で...
-
C言語 配列と関数の練習問題
-
複数桁10進数の*桁目だけを抽出...
-
(int *)の意味
-
if と配列の組み合わせ
-
ラップ関数とはどんなものですか?
-
卒業研究でよく分からないとこ...
-
【C++】関数ポインタの使い方
-
c言語
-
足して100になるような乱数のア...
-
C言語初心者です、、、お助けく...
-
数字列を3桁ごとにカンマで区切...
-
C言語 エラーの原因がわからな...
-
実数の整数部,小数部の取得
-
課題でつまってます・・・
-
商と剰余を同時に求める(C言語)
-
C言語の配列をC++のvectorに高...
-
std::set<int> で、ある値が何...
おすすめ情報