縦型探索（８パズル）

/*********************************/
/* 縦型探索（８パズル）          */
/*           coded by Y.Suganuma */
/*********************************/
#include <stdio.h>
#include <stack>
#include <map>
#include <string>
using namespace std;

class Depth
{
	public:
		int dep;
		string prev;
		Depth (string str, int dep1)
		{
			prev = str;   // 前の状態
			dep  = dep1;   // 深さ
		}
};

/********************************/
/* コマの移動                   */
/*      str : 現在の状態        */
/*      res : 移動後の状態      */
/*      return : 移動後の状態数 */
/********************************/
int move(string str, string *res)
{
	int k, n = 0;
	string str1;

	k = str.find("0");
	switch(k) {
		case 0:
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 1:
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 2:
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 3:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 4:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 5:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 6:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 7:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 8:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
	}

	return n;
}

/*************************/
/* 縦型探索（８パズル）  */
/*      start : 初期状態 */
/*      goal : 目標状態  */
/*      max : 最大深さ   */
/*************************/
void depth(string start, string goal, int max)
{
	int i1, n, node1 = 1, node2 = 0, dep = 1, ct = 1;
	string str, res[4];
	stack<pair<string, int> > s;
	map<string, Depth> m;
	map<string, Depth>::iterator it;
	bool sw;

	m.insert(pair<string, Depth>(start, Depth("",dep)));
	s.push(pair<string, int>(start, dep));
	while (!s.empty()) {
		str = s.top().first;
		dep = s.top().second;
		node2++;
					// ゴール
		if (str == goal) {
			ct = dep;
			break;
		}
					// ゴールでない
					// コマを移動し，同じ状態のものがなければキューに追加
		else {
			s.pop();
			if (dep < max) {
				n = move(str, res);
				for (i1 = 0; i1 < n; i1++) {
					sw = true;
					it = m.find(res[i1]);   // 同じ状態か？
					if (it != m.end()) {
						if (dep+1 < ((*it).second).dep)
							m.erase(it);
						else
							sw = false;
					}
					if (sw) {
						m.insert(pair<string, Depth>(res[i1], Depth(str,dep+1)));
						s.push(pair<string, int>(res[i1], dep+1));
						node1++;
					}
				}
			}
		}
	}
					// 結果の出力
	printf("   展開とチェック： %d %d，　最短距離： %d\n", node1, node2, ct);
	while (str.length() > 0) {
		printf("\n      %c %c %c\n", str.at(0), str.at(1), str.at(2));
		printf("      %c %c %c\n", str.at(3), str.at(4), str.at(5));
		printf("      %c %c %c\n", str.at(6), str.at(7), str.at(8));
		it  = m.find(str);
		str = ((*it).second).prev;
	}
}

int main()
{
	string goal = "123804765";

	printf("例１\n");
	string start = "283164705";
	depth(start, goal, 6);

	printf("例２\n");
	start = "216408753";
	depth(start, goal, 19);

	return 0;
}