ナンプレ

[ファー]

1 /* << np311.c >> */
2 /* 9× 9のナンバープレース*/
3 #include <stdio.h>
4 int a[10][10], /* マス目。*/
5 gyo[10][10], /* gyo[m]=0は、i行に数字mが出現していない。
6 gyo[m]=1は、i行に数字mが出現している。*/
7 retu[10][10], /* retu[m]=0は、i列に数字mが出現していない。
8 retu[m]=1は、i列に数字mが出現している。*/
9 block[10][10],/* block[m]=0は、iブロックに数字mが出現していない。
10 block[m]=1は、iブロックに数字mが出現している。*/
11 count; /* 配置の個数。*/
12 main() {
13 int i,j,k,m;
14 void gen(int d);
15 /* 問題の読み込み。*/
16 for( i=1; i<=9; i++ ) {
17 for( j=1; j<=9; j++ ) { scanf("%d",&a[j]); }
18 }
19 /* 初期設定。*/
20 for( i=1; i<=9; i++ ) {
21 for( j=1; j<=9; j++ ) {
22 gyo[j] = 0; retu[j] = 0; block[j] = 0;
23 }
24 }
25 for( i=1; i<=9; i++ ) {
26 for( j=1; j<=9; j++ ) {
27 m = a[i][j];
28 if( m > 0 ) {
29 gyo[i][m] = 1; retu[j][m] = 1;
30
31 block[k][m] = 1;
32 }
33 }
34 }
35 count = 0;
36 /* バックトラック。*/
37 gen(1);
38 printf("9× 9 count=%d\n",count);
39 }
40 void gen(int d) {
41 int i,j,k,m;
42 if( d > 81 ) {
43 count++; printf("[%d]\n",count);
44 for( i=1; i<=9; i++ ) {
45 for( j=1; j<=9; j++ ) { printf("%3d",a[i][j]); }
46 printf("\n");
47 }
48 } else {
- 11 -
ナンバープレイス
49 /* 行i */
50
51 /* 列j */
52
53 if( a[i][j] == 0 ) {
54 /* ブロックk */
55
56 for( m=1; m<=9; m++ ) {
57 if( (gyo[i][m] == 0)&&(retu[j][m] == 0)
58 &&(block[k][m] == 0) ) {
59
60
61
62
63
64 }
65 }
66 } else {
67
68 }
69 }
70 }

[ファー]

上記の答えを教えてください。
C言語初心者です。
三日間もかかったんですが。。。。
お願いします。

できない部分は一番したの条件文です。

[バグ]

とりあえず、丸投げは禁止ですので・・・
http://jubilo.cis.ibaraki.ac.jp/~isemba ... OG/866.pdf

[沖 滉均]

フォーラムルールは読まれましたでしょうか？
バグさんも書かれていますが、課題の丸投げは禁止されております。

自分で考えたコードを載せた上でのアドバイス等はできますので、自分で書いたものや
分からない箇所を具体的にあげるなどしてください。

[ファー]

すみませんでした。
最後のとこらに書いたの条件はよくわからないです。
自分の理解では
//0のときmを代入する条件。。。。。
for( i=1; i<=9; i++ ) {
for( j=1; j<=9; j++ ) {
gyo[m] = m;
retu[j][m] = m;
k = ((i-1)/3)*3 + (j-1)/3 + 1;
block[k][m] = m;
printf("%3d",gyo[j]);
}
}
実行してだめでした（T_T）；

[さかまき]

>最後のとこらに書いたの条件はよくわからないです。
はっきり言って、何を言っているのかわかりません。
御自分の理解で書かれたソースは問題文のどこに置いたのでしょう？
実行したソースコードをソースを貼るルールに従って貼りましょう。

ＰＤＦの問題部分をコピペすると、そっくりそのまま、まさに丸投げ。
頭の行番号を消したり、改ページ部分のゴミを消したりの労力もかけていません。
茨城も大変でしょうが、（もうすこし）がんばろう日本！


>48 } else {
>- 11 -
>ナンバープレイス
>49 /* 行i */

#このＰＤＦをコピーすると、ページ番号が表示のものと違ってくるんですねぇ

[ファー]

>最後のとこらに書いたの条件はよくわからないです。
入力間違いました（-_-）
ごめんなさい。


PDFの問題を勉強しようとおもっているだけです。
だめだったらごめんなさい。

問題をやってみたら、なかなかできなくて
教えてくれませんか？

今は最後のif文に
count++;
printf("[%d]\n",count);
for(i=1;i<=9;i++){
for( m=1; m<=9; m++ ) { printf("%3d",gyo[m]);
}
printf("\n");
}
を書いてみて
実行した結果はこれです。
[1]
1 1 0 0 1 0 0 0 1
0 0 0 0 0 1 1 1 0
1 0 0 0 0 0 1 1 0
0 1 1 0 0 0 0 0 0
0 0 1 0 1 0 1 0 0
1 1 0 0 1 0 0 0 0
0 0 0 1 1 1 0 1 0
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0
9× 9 count=1

[さかまき]

>PDFの問題を勉強しようとおもっているだけです。
自主的に挑んでいたのでしたら失礼しました。
特にそれを解く必要がなく、ナンプレのパズルの解法にチャレンジするなら
他の所でどうですか？探せば、説明も充実している所はいっぱいありますよ。
http://mediatips.co.jp/puzzle-9x9.html

[ファー]

すみません
まだできません（苦笑）
下記に書いてみたんですが...
count++;
printf("[%d]\n",count);
for(i=0;i<9;i++){
for( j=0; j<9; j++ ) {
a[0][0] = m;
printf("%3d",a[j]);
　　　　　　　　　　　　　　　　　}
}

結果は
[1]
0 0 0 0 0 0 0 4 0
0 0 5 1 9 0 0 0 2
0 8 0 0 0 7 0 0 6
0 7 0 0 0 1 0 8 0
0 0 0 3 0 2 0 0 0
0 3 0 5 0 0 0 7 0
1 0 0 2 0 0 0 5 0
6 0 0 0 5 4 8 0 0
0 4 0 0 0 0 0 0 0
[2]
2 0 0 0 0 0 0 4 0
0 0 5 1 9 0 0 0 2
0 8 0 0 0 7 0 0 6
0 7 0 0 0 1 0 8 0
0 0 0 3 0 2 0 0 0
0 3 0 5 0 0 0 7 0
1 0 0 2 0 0 0 5 0
6 0 0 0 5 4 8 0 0
0 4 0 0 0 0 0 0 0
[3]
3 0 0 0 0 0 0 4 0
0 0 5 1 9 0 0 0 2
0 8 0 0 0 7 0 0 6
0 7 0 0 0 1 0 8 0
0 0 0 3 0 2 0 0 0
0 3 0 5 0 0 0 7 0
1 0 0 2 0 0 0 5 0
6 0 0 0 5 4 8 0 0
0 4 0 0 0 0 0 0 0
[4]
4 0 0 0 0 0 0 4 0
0 0 5 1 9 0 0 0 2
0 8 0 0 0 7 0 0 6
0 7 0 0 0 1 0 8 0
0 0 0 3 0 2 0 0 0
0 3 0 5 0 0 0 7 0
1 0 0 2 0 0 0 5 0
6 0 0 0 5 4 8 0 0
0 4 0 0 0 0 0 0 0
[5]
6 0 0 0 0 0 0 4 0
0 0 5 1 9 0 0 0 2
0 8 0 0 0 7 0 0 6
0 7 0 0 0 1 0 8 0
0 0 0 3 0 2 0 0 0
0 3 0 5 0 0 0 7 0
1 0 0 2 0 0 0 5 0
6 0 0 0 5 4 8 0 0
0 4 0 0 0 0 0 0 0
9× 9 count=5


できなくてめっちゃ悔しいです（泣）
間違ったところや考え方を教えてください
お願い致します。

[non]

バグさんが示しているＰＤＦを参考にしているのなら　４×４はできているのでしょうか？
それから、「再帰呼び出し」って知ってますか？もしくは、「バックトラック」って。
知らないなら、まずこのあたりを調べてみましょう。

[ファー]

下記のサイトに参考してるんですが
http://mediatips.co.jp/puzzle-9x9.html
バックトラックを利用するって書いてあるんですが
なんにかまだ理解できてないです。

今こんな感じです。
printf("mm=%d\n",m);//m = 0
count++;
printf("[%d]\n",count);
for(i=0;i<9;i++){
for( j=0; j<9; j++ ) {
gyo[j] = 0;
retu[j] = 0;
block[j] = 0;
if(a[j] == 0){
if((gyo[j] == m) && (retu[j] == m) && (block[j] == m)){
　　　　　a[j] != m;
　　　　　　}
　　　　　　a[j] = m;
　　　　　　}
　　　　　　printf("%3d",a[j]);
　　　　　　}
　　　　　　printf("\n");
}

実行した結果はこれです。
mm=0
[1]
0 0 0 0 0 0 0 4 0
0 0 5 1 9 0 0 0 2
0 8 0 0 0 7 0 0 6
0 7 0 0 0 1 0 8 0
0 0 0 3 0 2 0 0 0
0 3 0 5 0 0 0 7 0
1 0 0 2 0 0 0 5 0
6 0 0 0 5 4 8 0 0
0 4 0 0 0 0 0 0 0
mm=1
[2]
1 1 1 1 1 1 1 4 1
1 1 5 1 9 1 1 1 2
1 8 1 1 1 7 1 1 6
1 7 1 1 1 1 1 8 1
1 1 1 3 1 2 1 1 1
1 3 1 5 1 1 1 7 1
1 1 1 2 1 1 1 5 1
6 1 1 1 5 4 8 1 1
1 4 1 1 1 1 1 1 1
mm=2
[3]
1 1 1 1 1 1 1 4 1
1 1 5 1 9 1 1 1 2
1 8 1 1 1 7 1 1 6
1 7 1 1 1 1 1 8 1
1 1 1 3 1 2 1 1 1
1 3 1 5 1 1 1 7 1
1 1 1 2 1 1 1 5 1
6 1 1 1 5 4 8 1 1
1 4 1 1 1 1 1 1 1
mm=3
[4]
1 1 1 1 1 1 1 4 1
1 1 5 1 9 1 1 1 2
1 8 1 1 1 7 1 1 6
1 7 1 1 1 1 1 8 1
1 1 1 3 1 2 1 1 1
1 3 1 5 1 1 1 7 1
1 1 1 2 1 1 1 5 1
6 1 1 1 5 4 8 1 1
1 4 1 1 1 1 1 1 1
mm=4
[5]
1 1 1 1 1 1 1 4 1
1 1 5 1 9 1 1 1 2
1 8 1 1 1 7 1 1 6
1 7 1 1 1 1 1 8 1
1 1 1 3 1 2 1 1 1
1 3 1 5 1 1 1 7 1
1 1 1 2 1 1 1 5 1
6 1 1 1 5 4 8 1 1
1 4 1 1 1 1 1 1 1
mm=5
[6]
1 1 1 1 1 1 1 4 1
1 1 5 1 9 1 1 1 2
1 8 1 1 1 7 1 1 6
1 7 1 1 1 1 1 8 1
1 1 1 3 1 2 1 1 1
1 3 1 5 1 1 1 7 1
1 1 1 2 1 1 1 5 1
6 1 1 1 5 4 8 1 1
1 4 1 1 1 1 1 1 1
mm=6
[7]
1 1 1 1 1 1 1 4 1
1 1 5 1 9 1 1 1 2
1 8 1 1 1 7 1 1 6
1 7 1 1 1 1 1 8 1
1 1 1 3 1 2 1 1 1
1 3 1 5 1 1 1 7 1
1 1 1 2 1 1 1 5 1
6 1 1 1 5 4 8 1 1
1 4 1 1 1 1 1 1 1
mm=7
[8]
1 1 1 1 1 1 1 4 1
1 1 5 1 9 1 1 1 2
1 8 1 1 1 7 1 1 6
1 7 1 1 1 1 1 8 1
1 1 1 3 1 2 1 1 1
1 3 1 5 1 1 1 7 1
1 1 1 2 1 1 1 5 1
6 1 1 1 5 4 8 1 1
1 4 1 1 1 1 1 1 1
mm=8
[9]
1 1 1 1 1 1 1 4 1
1 1 5 1 9 1 1 1 2
1 8 1 1 1 7 1 1 6
1 7 1 1 1 1 1 8 1
1 1 1 3 1 2 1 1 1
1 3 1 5 1 1 1 7 1
1 1 1 2 1 1 1 5 1
6 1 1 1 5 4 8 1 1
1 4 1 1 1 1 1 1 1
9× 9 count=9

どうか教えてください。
お願いします。

[non]

>if((gyo[j] == m) && (retu[j] == m) && (block[j] == m)){
これは、何を考えているのかさっぱりわかりません。
４×４の問題１から順番に解かれることをお勧めします。
まだ、再帰呼び出しについて調べていないようですね。

[たいちう]

話の流れを無視して投稿。Cで書いた方が良かったかな。
変わらないか。

コード:

#include <iostream>
#include <string>

using namespace std;

char* data[] = {
	"100700402",
	"020080050",
	"003009006",
	"700400100",
	"080050020",
	"009006003",
	"400100700",
	"050020080",
	"016003009",
};

int board[9][9];
int row[9];
int col[9];
int room[3][3];

void show() {
	static int count;
	cout << ++count << " :" << endl;
	for (int y = 0; y < 9; y++) {
		cout << "    ";
		for (int x = 0; x < 9; x++) {
			cout << board[x][y] << ' ';
			if (x % 3 == 2) cout << ' ';
		}
		cout << endl;
		if (y % 3 == 2) cout << endl;
	}
	cout << endl;
}

void put(int x, int y, int n) {
	int bit = 1 << (n - 1);
	row[y] |= bit;
	col[x] |= bit;
	room[x / 3][y / 3] |= bit;
}

void del(int x, int y, int n) {
	int bit = 1 << (n - 1);
	row[y] &= ~bit;
	col[x] &= ~bit;
	room[x / 3][y / 3] &= ~bit;
}

bool canPut(int x, int y, int n) {
	int bit = 1 << (n - 1);
	if (row[y] & bit) return false;
	if (col[x] & bit) return false;
	if (room[x / 3][y / 3] & bit) return false;
	return true;
}

void backtrack(int n) {
	if (n == 81) {
		show();
		return;
	}

	int x, y;
	for (;;) {
		x = n % 9;
		y = n / 9;
		if (board[x][y] == 0) break;
		n++;
		if (n == 81) {
			show();
			return;
		}
	}

	for (int i = 1; i <= 9; i++)
		if (canPut(x, y, i)) {
			board[x][y] = i;
			put(x, y, i);
			backtrack(n + 1);
			board[x][y] = 0;
			del(x, y, i);
		}
}

int main() {
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
			put(i, j, board[i][j] = data[j][i] - '0');

	backtrack(0);

	// quit
	cout << "End." << endl;
	cin.get();
	return 0;
}