ライツアウトのC言語プログラム

[epson14]

ライツアウトのプログラムをCで書いています。
現在３＊３で作成してみました。
アルゴリズムは多重ループ探索を用いようと考えています。
しかし、左上が１の場合と中上が１の場合など二つの場合分けの
if文が同時動きません。
どうしたらよいのでしょうか？
よろしくお願いします。

コード:

#include<stdio.h>

int p[3][3];

int main(void){
	int i,j;
	for(j=0;j<3;j++){
		for(i=0;i<3;i++){
			p[j][i]=0;
		}
	}

	//配列
	// [0][0] [0][1] [0][2]
	// [1][0] [1][1] [1][2]
	// [2][0] [2][1] [2][2]
	
	p[0][0]=1;
	p[0][1]=1;
	p[0][2]=1;
	p[1][0]=1;
	p[1][1]=1;
	p[1][2]=1;
	p[2][2]=1;
	
	//上記初期値の結果
	// 1 1 1 
	// 1 1 1
	// 0 0 1

	//上記初期値の出力
	for(j=0;j<3;j++){
		for(i=0;i<3;i++){
			printf("%d ",p[j][i]);
		}
		printf("\n");
	}
	printf("\n\n");


		//パターン１
	for(j=0;j<3;j++){
		for(i=0;i<3;i++){
		
			//左上が１の場合
			if(j==0 && i==0){
				if(p[j][i]==1){
					p[j][i]=0;
				if(p[j+1][i]==0)p[j+1][i]=1;
				else p[j+1][i]=0;
				if(p[j+1][i+1]==0)p[j+1][i+1]=1;
				else p[j+1][i+1]=0;
				if(p[j+2][i]==0)p[j+2][i]=1;
				else p[j][i]=0;
				}
			

				for(j=0;j<3;j++){
					for(i=0;i<3;i++){
						printf("%d ",p[j][i]);
						}
				printf("\n");
				}
				printf("\n\n");
			}
			
			//中上が１の場合
			if(j==0 && i==1){
				if(p[j][i]==1){
					p[j][i]=0;
				if(p[j+1][i-1]==0)p[j+1][i-1]=1;
				else p[j+1][i-1]=0;
				if(p[j+1][i]==0)p[j+1][i]=1;
				else p[j+1][i]=0;
				if(p[j+1][i+1]==0)p[j+1][i+1]=1;
				else p[j+1][i+1]=0;
				if(p[j+2][i]==0)p[j+2][i]=1;
				else p[j+2][i]=0;
				}
			
			
			for(j=0;j<3;j++){
		for(i=0;i<3;i++){
			printf("%d ",p[j][i]);
		}
		printf("\n");
	}
	printf("\n\n");
			}
			//右上が１の場合
			if(j==0 && i==2){
				if(p[j][i]==1){
					p[j][i]=0;
				if(p[j+1][i-1]==0)p[j+1][i-1]=1;
				else p[j+1][i-1]=0;
				if(p[j+1][i]==0)p[j+1][i]=1;
				else p[j+1][i]=0;
				if(p[j+2][i]==0)p[j+2][i]=1;
				else p[j+2][i]=0;
				}
			
			for(j=0;j<3;j++){
		for(i=0;i<3;i++){
			printf("%d ",p[j][i]);
		}
		printf("\n");
	}
	printf("\n\n");
			}
		
		
		}
	}
	


	for(j=0;j<3;j++){
		for(i=0;i<3;i++){
			printf("%d ",p[j][i]);
		}
		printf("\n");
	}
	return 0;
	}

[softya（ソフト屋)]

フォーラムルールをお読みください。　　http://dixq.net/board/board.html
原則として課題の丸投げは禁止させて頂いておりますので、現状で出来ているコードを提示していただいて問題点の修正などアドバイスを受けて頂けると宜しいかと思います。

[box]

現在３＊３で作成してみました。
しかし、二つのif文が同時に動きません。
どうしたらよいのでしょうか？

とりあえず、そのコードを投稿していただけますか？

[softya（ソフト屋)]

投稿した内容の書き換えは残念ながら通知がメールで届きませんので、投稿されたことに気づかない場合が多いで必ず返答の形でお願いします。
あとフォーラムルールにありますが、codeタグをご利用ください。

[softya（ソフト屋)]

えーとルールを知らないのですが、これで合っていますか？
「ライツアウト - Wikipedia」
http://ja.wikipedia.org/wiki/%E3%83%A9% ... 6%E3%83%88

[epson14]

伝説なるハッカーさん、返信ありがとうございます。
http://www.algopro.co.jp/sflguide/sfl_g2/index.html
上記のURLのページを参考に作っています。
ルールもそちらにわかりやすく書いてあります。
よろしくお願いします。

[softya（ソフト屋)]

伝説なるハッカー(819,022 ポイント)は名前じゃなくてポイントで付く通り名です。

それと、作ろうとしているのは自動的にパズルを解くプログラムなのでしょうか？　それとも遊んでもらうプログラムなのですか？

[epson14]

申し訳ありません、かなり不慣れなもので間違えてしまいました。

これは、問題を与えて解くプログラムです。
最終的には解く時間を図れるようなプログラムを作成したいと考えています。

[box]

ライツアウトのルールは、ネットなどにあるとおり、
3×3とか5×5とかの盤面でライトがついている・ついていないの初期状態があって、
1つのマス目を指定するとそれと上下左右のマス目との点灯状態が反転し、
最終的には全部を消すことができれば完成ということでよいでしょうか。

だとすると、私だったら、こんな風にします。
実際の盤面よりも一回り大きなサイズの盤面を用意します。
例えば、実際の盤面が3×3だったら[4][4]の配列を、
実際の盤面が5×5だったら[6][6]の配列を、という具合です。
こうしておくと、上下左右のマス目が実際の盤面をはみ出したときでも
配列の定義範囲外になることはありません。
つまり、実際の盤面より大きい部分（配列の添字が[0]、もしくは実際の盤面のサイズと同じ）は
ダミーとして使います。
こういうデータ構造を採用することで、「指定したマス目が盤面の端だったら」という判定が
不要になります。

1つのマス目を指定するとそれと上下左右のマス目との点灯状態が反転し、
盤面の状態が変わりますが、変更後の盤面を表示する際には
実際の盤面の大きさが3×3（配列定義は[4][4]）だったら[1][1]～[3][3]を、
実際の盤面の大きさが5×5（配列定義は[6][6]）だったら[1][1]～[5][5]を表示すればすみます。

まあ、私のつたない考えですので、他の方からもっといい方法が寄せられるかもしれません。

[epson14]

返信ありがとうございます。
配列も特に理解していない状態から始めたため、その考えは思いつきませんでした。
３＊３の配列を[4][4]で定義してやってみようと思います。
ありがとうございます。

[softya（ソフト屋)]

>３＊３の配列を[4][4]で定義してやってみようと思います。

３*３の外周を0で埋めるには[5][5]に必要があります。

[softya（ソフト屋)]

ルールは理解出来ました。
処理の話をすると、まず同じような処理を何度も書くのはミスの元なので関数化してください。
ここでのライツアウトのスイッチ処理は関数化が必須です。そうしないと3*3でも大変ですが5*5だと死にます。

実のところビット演算でxorした方が高速化できて処理もシンプルにはなりますがビット演算について来られるかが問題ですね。
あとnxnのn=30か62の上限が出来てしまいます。

それと解法は、どれを使われるのでしょうか？
・総当り戦略（２＾Ｎ×Ｎ回）
・確定総当り戦略（２＾Ｎ回）
・連立方程式を解く（Ｎ×Ｎ回）
が書かれていましたが。

最初は理解しやすい形で作ったほうが良いと思います。

[epson14]

ビット演算の理解はとても難しいと思います。
それで、解法は確定総当り戦略（２＾N回）を用いて書いています。

[softya（ソフト屋)]

ビット演算の理解はとても難しいと思います。
それで、解法は確定総当り戦略（２＾N回）を用いて書いています。

そうですね。やはりビット演算は難しいと思います。
それと確定総当り戦略を取る場合は、3*3で最大32回調べなくてはいけませんので、元の配列から32コピーを作って32回調べる必要が出てきます。
【訂正】 32回なのは5*5の場合ですね。3*3だと6回です。【さらに訂正】あっ2の3乗だから8回でした。
(1)これは分かりますか？

(2)あと反転の関数化は出来そうでしょうか？
(3)その他に、再帰的に処理する必要が出てくると思います。これはOKですか？

以上、ご検討ください。

[box]

大変失礼いたしました。
盤面の配列定義は、3×3ならば[5][5]、5×5ならば[7][7]ですね。
申し訳ありません。

[epson14]

ご返信ありがとうございます。
（１）の２＾３で８になることは理解できました。
そして、（２）の上下左右の反転はプログラムできると思います。
あとは、その再帰のプログラムを作るのが少し難しい状態です。

[softya（ソフト屋)]

上段の処理をどうするかなのですが、再帰なしでビット演算もなしのパターンを考えてみます。せめて上段の何処の反転をするかでビット演算が使えれば楽なんですけどね。
２段目以降はfor文処理が可能です。と言うことで２段め以降を組んでみてください。

[softya（ソフト屋)]

まぁ、結論としてビット演算をするかビット演算モドキをするしか無いだろうという結論になりました。
ビット演算モドキの方が面倒なのでビット演算で解説します。

結局上段は、反転するかしないかの２択ですよね。それが各ボタン事にあるわけですから詰まる所２進法なんです。
3*3の場合は、横に3bitとみなす事ができます。5*5の場合は横に5bitです。

で、forループで3bitや5bitの２進カウンタを回してやると何処をON/OFFすれば良いかの全パターンを作り出すことができます。
まぁ、２進カウンタといってもただのintなんですけどね。
そういうことで、0から2のn乗-1までのループをまず作ります。

まず、 2のn乗をまず求めないと行けないわけですが、これは1を<<演算でシフトして作ります。
つまり、1<<3だと8になり、1<<5だと32になるって事です。

なのでNにボタン数が入っているとすると
int bit;
for( bit=0 ; bit<(1<<N) ; bit++ ) {
で回せば良いことになります。

ここまではＯＫでしょうか？

【補足】　分かりやすいように１０進の値とビットパターンの対応を書いておきます。N=3の場合。
(0) 000
(1) 001
(2) 010
(3) 011
(4) 100
(5) 101
(6) 110
(7) 111
このビットパターンで1の場合はボタンを押すと考えてください。
ビットパターンは、左から左上、中上、右上を表します。

[epson14]

みなさんの意見を参考にし、プログラムをすべて書き直しました。
ビット演算についても理解でき、今までにないプログラムを作成することができました。
本当にありがとうございました。
つぎに、あらゆる問題で試してみたいのですが、できない問題というものは存在するのでしょうか？
そこがわからず乱数を用いて問題を作成するか迷っています。
よろしくお願いします。

[softya（ソフト屋)]

ここのフォーラムルールなのですが、完成したコードを張って頂ければと思います。　
http://dixq.net/board/board.html


>つぎに、あらゆる問題で試してみたいのですが、できない問題というものは存在するのでしょうか？

ライツアウトの事でしたら、存在しないはずです。

>そこがわからず乱数を用いて問題を作成するか迷っています。

効率的に網羅テストするなら、ビット演算の手法で全パターンを作るほうが効率的です。

[epson14]

作ったプログラムはこちらです。

コード:

#include<stdio.h>

#define N 5
#define M 5

int p[N+2][M+2];
int q[N+2][M+2];


void hanten(int i,int j);
int solve(int n,int m);

int main(void){

	int i,j,ii,jj;
	int a,n,m,x,y,z,zz;
	int pro[16]={0,1, 0,2, 1,1, 1,2, 2,0, 2,3, 3,2, 4,3, 4,5, 5,3, 5,5 };
	int check[M];

	n=N+2;
	m=M+2;
	

	//syokiti
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){ 
			p[i][j]=0;
		}
	}

	//mondai
	for(i=0;i<((sizeof pro/sizeof pro[0])/2);i++) p[pro[2*i]+1][pro[2*i+1]+1]=1;

	//copy
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){ 
			q[i][j]=p[i][j];
		}
	}

	//問題出力
	printf("Problem is...\n");
	for(i=1;i<n-1;i++){
		for(j=1;j<m-1;j++) {
			printf("%2d" ,p[i][j]);
		}
		printf("\n");
	}
	printf("\n");

	x=0;
	//bekijyo
	z=1;
	for(i=0;i<N;i++) z*=2;
	zz=z;//8 8

	//解答手順
	i=0;
	do{
		a=i;
		z=zz;
		for(ii=0;ii<n;ii++){
			for(jj=0;jj<m;jj++){
				p[ii][jj]=q[ii][jj];
			}
		}

		for(j=0;j<N;j++){
			z=z/2;
			check[j]=a/z; 
			if(check[j]==1) a=a-z; 
		}

		printf("%d %d %d %d %d\n",check[0],check[1],check[2],check[3],check[4]);

		for(j=0;j<N;j++){
			if(check[j]==1) hanten(1,j+1);
		}

		x=solve(n,m);
		
		y=0;
		for(ii=1;ii<n-1;ii++){
			for(jj=1;jj<m-1;jj++){
				y+=p[ii][jj];
			}
		}
		i++;
	}while(y!=0 && i!=zz);

	//結果条件判定
	y=0;

	for(i=1;i<n-1;i++){
		for(j=1;j<m-1;j++) y+=p[i][j];
	}

	//結果記述
	if(y==0) printf("This problem can solve, %dtimes\n" ,x);
	else printf("This problem don't have the solution\n");

	printf("\n");

	return 0;
}


void hanten(int i,int j){
	if(p[i][j]==0) p[i][j]=1;
	else  p[i][j]=0;

	if(p[i][j+1]==0) p[i][j+1]=1;
	else  p[i][j+1]=0;

	if(p[i+1][j]==0) p[i+1][j]=1;
	else  p[i+1][j]=0;

	if(p[i][j-1]==0) p[i][j-1]=1;
	else  p[i][j-1]=0;

	if(p[i-1][j]==0) p[i-1][j]=1;
	else  p[i-1][j]=0;
}

int solve(int n,int m){

	int i,j;
	int ii,jj;
	int x;

	x=0;

	for(i=2;i<n-1;i++){
		for(j=1;j<m-1;j++){
			if(p[i-1][j]==1) {
				hanten(i,j);
				x++;
			}
		}
	}
	return x;
}

[softya（ソフト屋)]

このソースコードだとコンパイルが通らないですね。
int pro[16]={0,1, 0,2, 1,1, 1,2, 2,0, 2,3, 3,2, 4,3, 4,5, 5,3, 5,5 };
で配列の宣言と実際の初期化が有っていません。[20][22]なのではないでしょうか？

[epson14]

そうですね。　すぐやってみます

[epson14]

全通りやったが答えがでないみたいな答えになります。

[softya（ソフト屋)]

あと、ココのページのパターンと答えが合わないです。
「はじめてのパルテノン」
http://www.algopro.co.jp/sflguide/sfl_g2/index.html
動作テストが不完全ではないでしょうか？まず、ここをクリアしましょう。

ざっとしか見てませんが、プログラムのループ箇所やループ数が私の想定よりかなり少ないです。
今行っているアルゴリズムを言葉で書いてみてください。そうすればやっていることが明確になりますので、どう直せばよいのかも見えてくると思います。

[epson14]

すべてのプログラムが完成しました。
プログラムは、ランダム関数を用いてそれを配列にいれ問題を生成しました。
また、一問を解く時間を計る関数もいれて時間も計測しています。
しかし、次の３つも問題が起こりました。
１．解なしの問題が存在すること
２．N×N行列のライツアウトに関してN=９，１１，１４，１６のとき解ありの問題がほとんど作成できない。
　　また、一問解く時間が他のと比べ極端に時間が短い
３．Nが１９の時、解ありの問題がまったく作成できない。

この３つの問題が発生しました。
まったく理由がわかりません。

[softya（ソフト屋)]

すべてのプログラムが完成しました。
プログラムは、ランダム関数を用いてそれを配列にいれ問題を生成しました。
また、一問を解く時間を計る関数もいれて時間も計測しています。
しかし、次の３つも問題が起こりました。
１．解なしの問題が存在すること
２．N×N行列のライツアウトに関してN=９，１１，１４，１６のとき解ありの問題がほとんど作成できない。
　　また、一問解く時間が他のと比べ極端に時間が短い
３．Nが１９の時、解ありの問題がまったく作成できない。

この３つの問題が発生しました。
まったく理由がわかりません。

前のこともあるのでソースコードを見せて下さい。