A* 그래프 탐색을 이용한 하노이 탑 퍼즐 프로그램

 

하노이 탑 퍼즐

 

• 모든 경로를 탐색하여 그 경로를 토대로 구현한 간단한 하노이 탑 퍼즐

 

소 스  코 드

// n 디스크 하노이 탑 퍼즐 프로그램을 작성.
//  - h(hat) >= 0, A*그래프 탐색으로 풀이
//  - h(hat) = 0 보다 좋은 허용 가능한 함수를 사용하라.
//  -제출물: 본인의 학번과 성명이 들어간 소스코드와 실행 캡처 화면


#include <iostream>
#include <vector>
#include <algorithm>

constexpr int MAX_LINE_COUNT{ 3 };
constexpr int MAX_DISK_COUNT{ 3 };

///////////////////////////////////////////////////
// Hanoi Tower Class
class Hanoi_Tower {
	std::vector<int> left_line;         // left
	std::vector<int> middle_line;      // middle
	std::vector<int> right_line;      // right

	int h_count;                  // h(n)
	int f_count;                  // f(n)
	int g_count;                  // g(n)

public:
	bool is_flag = false;            // Create Graph
	int my_Level;                  // Depth
	int my_Number;                  // Vecter Index
	int parent_Number;               // Parent_Index
	std::vector<int> child_Number;      // Childe_Index

public:
	Hanoi_Tower();
	Hanoi_Tower(int);

	bool IsLeftEmpty();
	bool IsMiddleEmpty();
	bool IsRightEmpty();

	void Print_Hanoi_Tower() const;
	void Set_f(int);
	void Set_g();
	void Heuristics(int);
	void Move_Disk(int, int);
	int Get_h();
	int Get_f();
	int Get_g();

	bool IsDiskMove(int, int);
	bool operator ==(const Hanoi_Tower& other) const;
	bool operator <(const Hanoi_Tower& other) const;

	~Hanoi_Tower();
};

Hanoi_Tower::Hanoi_Tower() {
	//std::cout << "하노이 타워 생성" << std::endl;
}
Hanoi_Tower::~Hanoi_Tower() {
	//std::cout << "하노이 타워 삭제" << std::endl;
}

Hanoi_Tower::Hanoi_Tower(int disk_count) {
	//now_pointer = 0;            // First Pointer
	h_count = 0;            // h(0)
	f_count = 0;            // f(0)
	g_count = 0;            // g(0)
	for (int i = disk_count; i > 0; --i) left_line.emplace_back(i);
}

bool Hanoi_Tower::IsDiskMove(int  m0, int m1) {
	// [ left : 0 ] [ middle : 1 ] [ right : 2 ]
	int mfm0;
	int mtm1;
	switch (m0)
	{
	case 0:
		if (1 == m1) {
			if (middle_line.empty()) return true;

			mfm0 = left_line[left_line.size() - 1];
			mtm1 = middle_line[middle_line.size() - 1];

			if (mfm0 < mtm1) return true;
			else return false;
		}


		else if (2 == m1) {
			if (right_line.empty()) return true;

			mfm0 = left_line[left_line.size() - 1];
			mtm1 = right_line[right_line.size() - 1];

			if (mfm0 < mtm1) return true;
			else return false;
		}

		break;

	case 1:
		if (0 == m1) {
			if (left_line.empty()) return true;

			mfm0 = middle_line[middle_line.size() - 1];
			mtm1 = left_line[left_line.size() - 1];

			if (mfm0 < mtm1) return true;
			else return false;
		}


		else if (2 == m1) {
			if (right_line.empty()) return true;

			mfm0 = middle_line[middle_line.size() - 1];
			mtm1 = right_line[right_line.size() - 1];

			if (mfm0 < mtm1) return true;
			else return false;
		}
		break;

	case 2:
		if (0 == m1) {
			if (left_line.empty()) return true;

			mfm0 = right_line[right_line.size() - 1];
			mtm1 = left_line[left_line.size() - 1];

			if (mfm0 < mtm1) return true;
			else return false;
		}


		else if (1 == m1) {
			if (middle_line.empty()) return true;

			mfm0 = right_line[right_line.size() - 1];
			mtm1 = middle_line[middle_line.size() - 1];

			if (mfm0 < mtm1) return true;
			else return false;
		}
		break;

	default:
		break;
	}

	return true;
}

bool Hanoi_Tower::IsLeftEmpty() {
	return left_line.empty();
}

bool Hanoi_Tower::IsMiddleEmpty() {
	return middle_line.empty();
}

bool Hanoi_Tower::IsRightEmpty() {
	return right_line.empty();
}

// Show Hanoi_Tower()
void Hanoi_Tower::Print_Hanoi_Tower() const {
	std::cout << " ========================================== " << std::endl;
	std::cout << " ID     : " << my_Number << std::endl;
	std::cout << " Level  : " << my_Level << std::endl << std::endl;

	std::cout << " Parent : " << parent_Number << std::endl;
	std::cout << " Chlid  : ";
	for (const int& a : child_Number) std::cout << a << ", ";
	std::cout << std::endl << std::endl;


	std::cout << " Left   : ";
	for (const int& a : left_line) std::cout << a << "  ";
	std::cout << std::endl;

	std::cout << " Middle : ";
	for (const int& a : middle_line) std::cout << a << "  ";
	std::cout << std::endl;

	std::cout << " Right  : ";
	for (const int& a : right_line) std::cout << a << "  ";
	std::cout << std::endl;
	std::cout << " ========================================== " << std::endl;
}

// Heuristics Func - h(n)
// Comparison of purpose indexs
void Hanoi_Tower::Heuristics(int disk_count) {
	int h = 0;

	if (right_line.empty()) h = disk_count;
	else {
		for (int i = 0; i < right_line.size(); ++i) {
			if (right_line[i] == disk_count - i) continue;
			++h;
		}

		h += disk_count - right_line.size();

	}
	h_count = h;
}

// f(n)
void Hanoi_Tower::Set_f(int f_c) {
	f_count = f_c;
	Set_g();
}

// g(n) = f(n) + h(n)
void Hanoi_Tower::Set_g() {
	g_count = h_count + f_count;
}

// Moving Disk [ 0 : left | 1 : middle | 2 : right ]
void Hanoi_Tower::Move_Disk(int m0, int m1) {
	int last_pointer;
	int last_index;
	switch (m0) {
	case 0:
		if (0 == left_line.size()) {
			std::cout << " Moving Disk m0 empty Error " << std::endl;
			break;
		}

		last_pointer = left_line.size() - 1;
		last_index = left_line[last_pointer];
		left_line.erase(left_line.begin() + last_pointer);

		switch (m1) {
		case 0:
			std::cout << "Moving Disk Same Error" << std::endl;
			break;

		case 1:
			middle_line.emplace_back(last_index);
			break;

		case 2:
			right_line.emplace_back(last_index);
			break;

		default:
			std::cout << "Moving Disk m1 Error" << std::endl;
			break;
		}
		break;

	case 1:
		if (0 == middle_line.size()) {
			std::cout << " Moving Disk m0 empty Error " << std::endl;
			break;
		}

		last_pointer = middle_line.size() - 1;
		last_index = middle_line[last_pointer];
		middle_line.erase(middle_line.begin() + last_pointer);

		switch (m1) {
		case 0:
			left_line.emplace_back(last_index);
			break;

		case 1:
			std::cout << "Moving Disk Same Error" << std::endl;
			break;

		case 2:
			right_line.emplace_back(last_index);
			break;

		default:
			std::cout << "Moving Disk m1 Error" << std::endl;
			break;
		}
		break;

	case 2:
		if (0 == right_line.size()) {
			std::cout << " Moving Disk m0 empty Error " << std::endl;
			break;
		}

		last_pointer = right_line.size() - 1;
		last_index = right_line[last_pointer];
		right_line.erase(right_line.begin() + last_pointer);

		switch (m1) {
		case 0:
			left_line.emplace_back(last_index);
			break;

		case 1:
			middle_line.emplace_back(last_index);
			break;

		case 2:
			std::cout << "Moving Disk Same Error" << std::endl;
			break;

		default:
			std::cout << "Moving Disk m1 Error" << std::endl;
			break;
		}
		break;

	default:
		std::cout << "Moving Disk m0 Error" << std::endl;
		break;
	}
}

bool Hanoi_Tower::operator ==(const Hanoi_Tower& other) const {
	if (other.left_line != left_line) return false;
	if (other.middle_line != middle_line) return false;
	if (other.right_line != right_line) return false;

	return true;
}

bool Hanoi_Tower::operator <(const Hanoi_Tower& other) const {
	if (g_count == other.g_count) {
		return my_Number < other.my_Number;
	}
	return g_count < other.g_count;
}


int Hanoi_Tower::Get_h() {
	return h_count;
}
int Hanoi_Tower::Get_f() {
	return f_count;
}
int Hanoi_Tower::Get_g() {
	return g_count;
}


///////////////////////////////////////////////////

std::vector<Hanoi_Tower> Hanoi_Graph;
int id{ 0 };
//////////////////////////////////////////////////
// Func()
// Same Node Search
bool IsInGraph(Hanoi_Tower&);
bool IsLevelGraph_Child(int);
int GetNextNodeIndex();
void NewnNode(int pid, int m0, int m1);
void Make_node(int Pindex);
void Make_Graph(Hanoi_Tower start);

///////////////////////////////////////////////////

int main() {
	int disk_count{ MAX_DISK_COUNT };
	int max_move_count{ 1 };

	std::cout << " ================= " << std::endl;
	std::cout << " Disk Count : " << disk_count << std::endl;

	// Max_Move_Count 
	for (int i = 0; i < disk_count; ++i) {
		max_move_count *= 2;
	}
	max_move_count -= 1;
	std::cout << " Max Move : " << max_move_count << std::endl;
	std::cout << " ================= " << std::endl;



	// Init HanoiTower Start
	Hanoi_Tower Hanoi_n0{ disk_count };

	Make_Graph(Hanoi_n0);

	std::cout << " Hanoi_Graph Number of Cases : " << Hanoi_Graph.size() << std::endl;


	// 1. 2.
	// OpenList & CloseList
	std::vector<Hanoi_Tower> OpenList;
	std::vector<Hanoi_Tower> CloseList;


	OpenList.emplace_back(Hanoi_Graph[0]);
	// 
	int indexPointer{ 0 };
	Hanoi_Tower NHanoi;

	while (true) {
		// 3.
		if (OpenList.empty()) {
			std::cout << " Empty OpenList Error " << std::endl;
			break;
		}

		//
		++indexPointer;  // while 순서

		// Move OpenList 0 index -> CloseList
		NHanoi = OpenList[0];


		CloseList.emplace_back(NHanoi);
		OpenList.erase(OpenList.begin());

		if ((0 == NHanoi.Get_h()) && (0 != NHanoi.my_Number)) {
			std::cout << " Search Goal " << std::endl;
			break;
		}


		for (const auto& a : NHanoi.child_Number) {
			Hanoi_Graph[a].Set_f(indexPointer);
			OpenList.emplace_back(Hanoi_Graph[a]);
		}

		std::sort(OpenList.begin(), OpenList.end());

	}

	Hanoi_Tower SHonoi{ NHanoi };
	std::vector<Hanoi_Tower> FindHanoi;

	while (true) {
		if (SHonoi == Hanoi_Graph[0]) {
			FindHanoi.emplace_back(SHonoi);
			break;
		}
		FindHanoi.emplace_back(SHonoi);
		SHonoi = Hanoi_Graph[SHonoi.parent_Number];
	}



	for (int i = FindHanoi.size() - 1; i >= 0; --i) {
		std::cout << " =================== " << std::endl;
		std::cout << " 순서 : " << FindHanoi.size() - i - 1 << std::endl;
		FindHanoi[i].Print_Hanoi_Tower();
	}


	system("pause");
}

// Same Node Search
bool IsInGraph(Hanoi_Tower& co) {
	for (const auto& a : Hanoi_Graph) {
		if (a == co) return true;
	}
	return false;
}

// Level Child
bool IsLevelGraph_Child(int ml) {
	for (const auto& a : Hanoi_Graph) {
		if (a.my_Level != ml) continue;
		if (!a.child_Number.empty()) return true;
	}
	return false;
}


int GetNextNodeIndex() {
	for (const auto& a : Hanoi_Graph) {
		if (true == a.is_flag) continue;
		return a.my_Number;
	}
	return -1;
}


void NewnNode(int pid, int m0, int m1) {
	Hanoi_Tower * node = new Hanoi_Tower;
	*node = Hanoi_Graph[pid];


	node->Move_Disk(m0, m1);

	if (!IsInGraph(*node)) {
		++id;
		node->my_Number = id;
		Hanoi_Graph[pid].child_Number.emplace_back(node->my_Number);
		node->my_Level = Hanoi_Graph[pid].my_Level + 1;
		node->parent_Number = pid;
		Hanoi_Graph.emplace_back(*node);
		Hanoi_Graph[id].is_flag = false;
		Hanoi_Graph[id].child_Number.clear();

		Hanoi_Graph[id].Heuristics(MAX_DISK_COUNT);      // Setting h(n)
		delete node;
	}
	else {
		delete node;
	}
}


void Make_node(int Pindex) {

	Hanoi_Graph[Pindex].is_flag = true;
	//std::cout << "MakeNode ID: " << Pindex << std::endl;
	// 1EA

	// Start [left : O] [middle : X] [right : X]
	if ((!Hanoi_Graph[Pindex].IsLeftEmpty()) && ((Hanoi_Graph[Pindex].IsMiddleEmpty()) && (Hanoi_Graph[Pindex].IsRightEmpty()))) {
		// std::cout << " Start [left : O] [middle : X] [right : X] " << std::endl;

		if (Hanoi_Graph[Pindex].IsDiskMove(0, 1)) NewnNode(Pindex, 0, 1);
		if (Hanoi_Graph[Pindex].IsDiskMove(0, 2)) NewnNode(Pindex, 0, 2);
	}

	// Start [left : X] [middle : O] [right : X]
	if ((Hanoi_Graph[Pindex].IsLeftEmpty()) && ((!Hanoi_Graph[Pindex].IsMiddleEmpty()) && (Hanoi_Graph[Pindex].IsRightEmpty()))) {
		// std::cout << " Start [left : X] [middle : O] [right : X] " << std::endl;

		if (Hanoi_Graph[Pindex].IsDiskMove(1, 0)) NewnNode(Pindex, 1, 0);
		if (Hanoi_Graph[Pindex].IsDiskMove(1, 2)) NewnNode(Pindex, 1, 2);
	}

	// Start [left : X] [middle : X] [right : O]
	if ((Hanoi_Graph[Pindex].IsLeftEmpty()) && ((Hanoi_Graph[Pindex].IsMiddleEmpty()) && (!Hanoi_Graph[Pindex].IsRightEmpty()))) {
		// std::cout << " Start [left : X] [middle : X] [right : O] " << std::endl;
		if (Hanoi_Graph[Pindex].IsDiskMove(2, 0)) NewnNode(Pindex, 2, 0);
		if (Hanoi_Graph[Pindex].IsDiskMove(2, 1)) NewnNode(Pindex, 2, 1);
	}

	// 2EA

	// Start [left : O] [middle : O] [right : X]
	if ((!Hanoi_Graph[Pindex].IsLeftEmpty()) && ((!Hanoi_Graph[Pindex].IsMiddleEmpty()) && (Hanoi_Graph[Pindex].IsRightEmpty()))) {
		// std::cout << " Start [left : O] [middle : O] [right : X] " << std::endl;
		if (Hanoi_Graph[Pindex].IsDiskMove(0, 1)) NewnNode(Pindex, 0, 1);
		if (Hanoi_Graph[Pindex].IsDiskMove(0, 2)) NewnNode(Pindex, 0, 2);

		if (Hanoi_Graph[Pindex].IsDiskMove(1, 0)) NewnNode(Pindex, 1, 0);
		if (Hanoi_Graph[Pindex].IsDiskMove(1, 2)) NewnNode(Pindex, 1, 2);
	}

	// Start [left : O] [middle : X] [right : O]
	if ((!Hanoi_Graph[Pindex].IsLeftEmpty()) && ((Hanoi_Graph[Pindex].IsMiddleEmpty()) && (!Hanoi_Graph[Pindex].IsRightEmpty()))) {
		// std::cout << " Start [left : O] [middle : X] [right : O] " << std::endl;

		if (Hanoi_Graph[Pindex].IsDiskMove(0, 1)) NewnNode(Pindex, 0, 1);
		if (Hanoi_Graph[Pindex].IsDiskMove(0, 2)) NewnNode(Pindex, 0, 2);

		if (Hanoi_Graph[Pindex].IsDiskMove(2, 0)) NewnNode(Pindex, 2, 0);
		if (Hanoi_Graph[Pindex].IsDiskMove(2, 1)) NewnNode(Pindex, 2, 1);
	}

	// Start [left : X] [middle : O] [right : O]
	if ((Hanoi_Graph[Pindex].IsLeftEmpty()) && ((!Hanoi_Graph[Pindex].IsMiddleEmpty()) && (!Hanoi_Graph[Pindex].IsRightEmpty()))) {
		// std::cout << " Start [left : X] [middle : O] [right : O] " << std::endl;
		if (Hanoi_Graph[Pindex].IsDiskMove(1, 0)) NewnNode(Pindex, 1, 0);
		if (Hanoi_Graph[Pindex].IsDiskMove(1, 2)) NewnNode(Pindex, 1, 2);

		if (Hanoi_Graph[Pindex].IsDiskMove(2, 0)) NewnNode(Pindex, 2, 0);
		if (Hanoi_Graph[Pindex].IsDiskMove(2, 1)) NewnNode(Pindex, 2, 1);

	}

	// 3EA
	// Start [left : O] [middle : O] [right : O]
	if ((!Hanoi_Graph[Pindex].IsLeftEmpty()) && ((!Hanoi_Graph[Pindex].IsMiddleEmpty()) && (!Hanoi_Graph[Pindex].IsRightEmpty()))) {
		// std::cout << " Start [left : X] [middle : O] [right : X] " << std::endl;

		if (Hanoi_Graph[Pindex].IsDiskMove(0, 1)) NewnNode(Pindex, 0, 1);
		if (Hanoi_Graph[Pindex].IsDiskMove(0, 2)) NewnNode(Pindex, 0, 2);

		if (Hanoi_Graph[Pindex].IsDiskMove(1, 0)) NewnNode(Pindex, 1, 0);
		if (Hanoi_Graph[Pindex].IsDiskMove(1, 2)) NewnNode(Pindex, 1, 2);

		if (Hanoi_Graph[Pindex].IsDiskMove(2, 0)) NewnNode(Pindex, 2, 0);
		if (Hanoi_Graph[Pindex].IsDiskMove(2, 1)) NewnNode(Pindex, 2, 1);
	}
}

void Make_Graph(Hanoi_Tower start) {

	start.my_Number = 0;   // number 0
	start.my_Level = 0;      // index 0


	start.parent_Number = -1;   // Parent_Index

	Hanoi_Graph.emplace_back(start);
	int Max_Depth = 0;
	int isRoot = -1;

	int next_index = 0;


	while (true) {


		next_index = GetNextNodeIndex();
		if (-1 == next_index) break;
		Make_node(next_index);

	}



}

 

 

결 과 값