反転ゲームの最小回数の求め方

[スー]

こんにちはスーです。

早速ですが質問があります。
反転ゲーム(正式名称がわからないです)のクリアまでの最小回数を求めるプログラムを作っています。

反転ゲーム
①
　□□□□
　□□□□
　□□□□
　□□□□
①の状態で左上を押したら、②の状態になります。

②
　■■□□
　■□□□
　□□□□
　□□□□
②の状態で[0][2]を押したら、③の状態になります。

③
　■□■■
　■□■□
　□□□□
　□□□□

これを繰り返して、すべて■にしたらゲームクリアです。

今できているプログラムが
①ランダムな所を指定し、反転させる。
②ゲームクリアまで繰り返します。
③ゲームクリアまでの回数をカウントします。
④カウントが一番小さい数を記憶し、①に戻ります。

このやり方ですと、確実な最小回数がでない可能性があります。
もっと効率の良い方法はないでしょうか？
どうぞよろしくお願いします。

環境
CPad for Borland C++ Compiler
C言語
WindowsXP
です。

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>

#define BLUE -1
#define RED 1
#define MASS 4

#define KAISUU 1000

void flip(int [/url][MASS],int ,int );
void draw(int [/url][MASS]);
int judge(int [/url][MASS]);


int main(){
	srand((unsigned)time(NULL));
	int b[MASS][MASS];
	//配列の初期化
	for(int i=0;i<MASS;i++){
		for(int j=0;j<MASS;j++){
			b[j] = BLUE;
		}
	}
	//最小値の初期化　これ以上大きい数はないはず…
	//いままでやった中の最小回数を記録
	int min = 2147483647;

	for(int k=0;k<KAISUU;k++){
		//全部REDになるまでの回数を記録
		int count = 0;

		while(1){
			//反転している数を記録
			int sum = 0;

			//draw(b);
			//適当な所していして、反転させる
			flip(b, rand()%MASS, rand()%MASS);

			sum = judge(b);
			count++;

			if(sum == MASS*MASS)break;
			//getch();
		}
		
		//minの記録
		if(count < min){
			min = count;
		}
		printf("%d回でできました。　現在の最小回数は%dです。\n",count,min);

		//getch();
		
		//初期化
		count = 0;
		for(int i=0;i<MASS;i++){
			for(int j=0;j<MASS;j++){
				b[j] = BLUE;
			}
		}
	}
	printf("最小回数は%dです。\n",min);
	getch();
	return 0;
}


//[j]の数を判定させる
void flip(int ary[/url][MASS],int i,int j){
	ary[j] *= -1;
	if(i-1 >= 0)
		ary[i-1][j] *= -1;
	if(i+1 <= MASS-1)
		ary[i+1][j] *= -1;
	if(j-1 >= 0)
		ary[j-1] *= -1;
	if(j+1 <= MASS-1)
		ary[j+1] *= -1;
}

//現在の状態を表示する
void draw(int ary[/url][MASS]){
	for(int i=0;i<MASS;i++){
		for(int j=0;j<MASS;j++){
			if(ary[j] == BLUE)
				printf("□");
			if(ary[j] == RED)
				printf("■");
		}
		printf("\n");
	}
	printf("\n");
}

//反転している物の数を返す
int judge(int ary[/url][MASS]){
	int count = 0;
	for(int i=0;i<MASS;i++){
		for(int j=0;j<MASS;j++){
			if(ary[j] == RED){
				count++;
			}
		}
	}
	return (count);
}

[box]

盤面の初期状態は、２の１６乗（＝６５５３６）とおりあります。
初期状態のそれぞれについて、１手目をどこから始めるかは１６とおりあります。
よって、６５５３６＊１６＝１０４８５７６とおりのすべてについて調べれば、
どの初期状態のときに１手目をどこから始めれば最小手数で反転するかが求まります。

[box]

＞６５５３６＊１６＝１０４８５７６とおり

盤面を９０度の整数倍だけ回転させたり、
裏表を反転させたりすることで、
同一盤面とみなせるケースがありますね。

よって、実際に調べるのは１０４８５７６とおりよりも少なくてすみます。

[さが]

>boxさん
このゲームは
１ 同じ場所で、二度反転すると意味が無い
２ 順番に依存しない
ので２の１６乗で大丈夫だと思います。

[さが]

int min = 65536;
for(int i=0;i<65536;i++){
   //配列初期化
   int count = 0;
   for(int j=0;j<16;j++){
      if( i & (1 << j) == 1){
         flip(b,j%4,j/4);
         count++;
      }
   }
   if(judge(b) == MASS*MASS)
      if(count < min)
         min = count;
}
printf("min = %d",min);

卓上で考えたので、激しく間違ってるかも知れません。

[mats]

これは「ライツアウト」というパズルです．

Nマスのとき，単純にはO(2^N)の計算時間で解けますが，工夫をすることでO( 2^sqrt(N) )まで落とせます．
問題の16マスならば2^4=16通りを調べれば解けるらしいです．
（自分ではまだ実装していないので，プログラムは無いです．すいません・・・）

他にも，連立方程式を解くことでいきなり解を求める方法もあるそうです．

参考URL：
http://www.ic-net.or.jp/home/takaken/nt ... ight2.html

[スー]

boxさん、さがさんありがとうございます。

2＾16通りの判定をすればいいことがわかりました。ありがとうございます。
すべてのパターンをするという理屈はわかるのですが、実際するとなるとイメージが掴めないです。

さがさんすみませんが、
if( i & (1 << j) == 1){
ココの意味を教えて頂けないでしょうか？
特に <<の左シフトが理解できないです。

どうぞよろしくお願いします。

[さが]

自分も最近知ったばかりなのであんまりえらい事いえないんですが

(1<<j)　これは　１を左にｊ回シフトするという意味で
左上から順にボタンを押すか押さないかの判定をしてます。

表の16個のボタンを下の様に表したとします。

1(0)    2(1)    4(2)     8(3)
  16(4)  32(5)  64(6)  128(7)
・・・・

*()内は ボタンの名前とします。
そして
３なら ０ と １
７なら ０ と １ と ２
を同時に押すことで表すとします。これを65536までやると押し全てのパターンを作ることが出来ます。

次に3という物を2進数で考えると

i               ２進数表示
   3    --->     11
   7    --->   111

なります。そして (1 << j) は

j=0   --->       1
   j=1   --->     10
   j=2   --->   100

となり、これと i でand をとってやれば、 for で変化する 変数 i において、押されているボタンが分かるというわけです。

[スー]

matsさん、さがさんレスありがとうございます。

matsさん
書き込み時間の関係で無視したみたいになってすみませんでした。
ライツアウトというゲーム名なので始めて知りました。
参考URLやライツアウトで検索したサイトを見たら解をだすまでの高速化と安定化することができました。
ありがとうございます。

さがさん
詳しく書いていただきありがとうございます。
おかげで総当りの方法ができそうです。
他のゲームとかにも応用できそうですね。使わせてもらいます。

boxさん、さがさん、matsさん
ありがとうございました。