パズルをコンピュータにやらせてみた。

先日、実家に帰ったときにパズルを渡された。64個の立方体がヘビのように連なっており、それぞれの立方体の面同士が合わさるように繋がっていてその部分は回すことが出来る。で、その部分を回して組み立てることにより４＾３の立方体に組み上げるというパズル。図がないとなんとも説明しずらいけどまあ頑張ってイメージしてくれ（ぉ
で、最初はちょっと自力で頑張ってみたけどこれ人間が出来るパズルじゃないんじゃないかと思われ早々に諦めてコンピュータに丸投げした。各立方体の繋がり方は二種類だけで、直進しているか直交しているかだけ。で、直進している場合は回しても変わらないから１パターンだけで、直交する場合はその方向が４方向に回るので４パターン。で直交する部分は数えてみたら４５個だったので組み合わせは全部で４＾45。単純に考えたら現実的な計算時間では終わらないけど、動的計画法で劇的に減らせるので試してみました。

class Vector3D
{
public:
	Vector3D( int xx, int yy, int zz ):x(xx),y(yy),z(zz){}
	int x,y,z;
	Vector3D operator+( const Vector3D& vec )const{
		return Vector3D( x+vec.x, y+vec.y, z+vec.z );
	}

	int dot( const Vector3D& vec )const{
		return x*vec.x + y*vec.y + z*vec.z;
	}
};

const Vector3D g_avec[6] = {
	Vector3D( 0, 0, 1 ),
	Vector3D( 0, 0,-1 ),
	Vector3D( 0, 1, 0 ),
	Vector3D( 0,-1, 0 ),
	Vector3D( 1, 0, 0 ),
	Vector3D(-1, 0, 0 ),
};

const int g_aiNext[] = {
	1,1,2,2,1,2,2,2,1,1,2,2,1,2,2,1,2,2,1,2,2,2,2,2,2,2,2,2,1,2,1,2,2,2,2,2,2,1,2,1,1,2,2,2,2,1,1,2,2,1,2,2,2,2,2,2,2,2,2,2,1,1,2,
};

bool IsNext( int nowIndex, const Vector3D& nowVec, const Vector3D& direct, int aaaiNum[4][4][4] )
{
	if( nowIndex == 64 ){
		//成功
		return true;
	}
	if( !(0 <= nowVec.x && nowVec.x < 4 && 0 <= nowVec.y && nowVec.y < 4 && 0 <= nowVec.z && nowVec.z < 4) ){
		//範囲外
		return false;
	}
	if( aaaiNum[nowVec.z][nowVec.y][nowVec.x] != -1 ){
		//既に通っている
		return false;
	}
	aaaiNum[nowVec.z][nowVec.y][nowVec.x] = nowIndex;

	if( g_aiNext[nowIndex] == 1 ){
		//そのまままっすぐ進む
		if( IsNext( nowIndex+1, nowVec + direct, direct, aaaiNum ) ){
			//成功
			return true;
		}
	}else{
		//90度回転
		for( int i = 0; i < 6; ++i ){
			if( g_avec[i].dot( direct ) == 0 ){
				if( IsNext( nowIndex+1, nowVec + g_avec[i], g_avec[i], aaaiNum ) ){
					//成功
					return true;
				}
			}
		}
	}
	//失敗
	aaaiNum[nowVec.z][nowVec.y][nowVec.x] = -1;
	return false;
}

int main()
{
	int aaaiNum[4][4][4];
	for( int z = 0; z < 4; ++z ){
		for( int y = 0; y < 4; ++y ){
			for( int x = 0; x < 4; ++x ){
				aaaiNum[z][y][x] = -1;
			}
		}
	}

	if( IsNext( 0, Vector3D( 0, 0, 0 ), Vector3D( 0, 0, 1 ), aaaiNum ) ){
		for( int z = 0; z < 4; ++z ){
			for( int y = 0; y < 4; ++y ){
				for( int x = 0; x < 4; ++x ){
					std::cout << aaaiNum[z][y][x] << '\t';
				}
				std::cout << std::endl;
			}
			std::cout << std::endl;
		}
	}else{
		std::cout << "false" << std::endl;
	}


	return 0;
}

ベクトルを自作する時間も含めて20分程しか使っていないので突っ込みどころが多いけどまあ勘弁してくれ。ていうかベクトルは早く標準ライブラリに追加してくれ（ぉ
考え方は単純で、端から順番に全パターンを試していく。途中で外に出たり重なったら一つ戻る。全部ダメならさらに戻る。ということを再帰的に繰り返して最後までたどり着いたらそれが正解である。ちなみに出発点もどこにあるかわからないけどきっと角だろうと思ってそれ以上のルーチンは組んでいない。あと、解は複数パターンある可能性がある(少なくとも面対称なのがあるから2つは絶対ある)けど、たまたま最初に見つけたパターンしか返しません。

で、実際計算させたら実家の少々古いPCでも数十秒で終わってくれた。で実際のパズルを組み立てたらちゃんと立方体に組みあがってちょっと感動した（＾＾；　まあパズルとしては反則だけどなんとなく勝った気分でした（ぇ