eightpuzzle.cpp

Solve the 8-puzzle problem using A * algorithme. Input: Program reads start state and goal state

#include <iostream>
#include <fstream>

using namespace std;

static const char fINP[] = "EightPuzzle.INP";
static const char fOUT[] = "EightPuzzle.OUT";

static const int dx[4] = {-1, 0, 1,  0};
static const int dy[4] = { 0, 1, 0, -1};

struct Node
{
	Node()
	{
		pre = -1;
		fn = gn = hn = 0;
		notRemoved = true;
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				tile[i][j] = 0;
		x = y = 0;
	}
	
	Node &operator=(Node &b)
	{
		pre = b.pre;
		fn = b.fn;
		gn = b.gn;
		hn = b.hn;
		notRemoved = b.notRemoved;
		
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				tile[i][j] = b.tile[i][j];
		x = b.x;
		y = b.y;
		return b;
	}
	
	friend ofstream &operator<<(ofstream &f, Node &b)
	{
		for(int i = 0; i < 3; i++)
		{
			for(int j = 0; j < 3; j++)
				f << b.tile[i][j] << " ";
			f << endl;
		}
		f << endl;
		return f;
	}
	
	void swapTile(int &new_x, int &new_y)
	{
		tile[x][y] = tile[new_x][new_y];
		tile[new_x][new_y] = 0;
		x = new_x;
		y = new_y;
	}
	
	int tile[3][3];
	int pre;
	int fn, gn, hn;
	bool notRemoved;
	int x, y; // pos of blank
};

Node begin, end, queue[250000 * 10];
char heuristic = ' ';
int numStates;
bool ok = false;
int track = 0;

// read and write to file
void readFile();
void writeFile();

// calculate h(n)
int numberOfMisplacedTiles(Node &, Node &);
int sumOfManhattanDistance(Node &, Node &);

// A* function
void AStar(int heuristicFunc(Node &, Node&));

int main()
{
	readFile();
	//cout << heuristic << endl;
	
	if(heuristic == 'N')
		AStar(numberOfMisplacedTiles);
	else if(heuristic == 'S')
		AStar(sumOfManhattanDistance);
	
	writeFile();
	
	//cin.get();
	return 0;
}

// read and write to file
void readFile()
{
	ifstream f(fINP);
	
	f >> heuristic;
	
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
		{
			f >> begin.tile[i][j];
			if(begin.tile[i][j] == 0)
			{
				begin.x = i;
				begin.y = j;
			}
		}
	
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
		{
			f >> end.tile[i][j];
			if(end.tile[i][j] == 0)
			{
				end.x = i;
				end.y = j;
			}
		}
			
	f.close();
}

void writeFile()
{
	ofstream f(fOUT);
	
	if(ok)
	{
		f << numStates << " " << queue[track].gn << endl;
		int *tmp = new int[queue[track].gn + 1];
		int i = 0;
		while(track != -1)
		{	
			tmp[i] = track;
			i++;
			track = queue[track].pre;
		}
		for(i--; i >= 0; i--)
		{
			f << queue[tmp[i]];
		}
	}
	else 
	{
		f << numStates << " " << -1 << endl;
	}
	
	f.close();
}

// calculate h(n)
int numberOfMisplacedTiles(Node &a, Node &b)
{
	int s = 0;
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			if(a.tile[i][j] != 0)
				if(a.tile[i][j] != b.tile[i][j])
					s++;
	return s;
}

int sumOfManhattanDistance(Node &a, Node &b)
{
	int s = 0;
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			if(a.tile[i][j] != 0)
			{
				int h, k;
				for(h = 0; h < 3; h++)
				{
					for(k = 0; k < 3; k++)
						if(a.tile[i][j] == b.tile[h][k])
						{
							s += (abs(h-i) + abs(k-j));
							break;
						}
					if(k < 3)
						break;
				}
			}
	return s;
}

bool isEqual(Node &a, Node &b)
{
	if(a.x != b.x || a.y != b.y)
		return false;
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			if(a.tile[i][j] != b.tile[i][j])
				return false;
	return true;
}

void AStar(int heuristicFunc(Node &, Node &))
{
	int cur = 0, last = 1;
	numStates = 0;
	queue[0] = begin;
	queue[0].hn = heuristicFunc(queue[0], end);
	queue[0].gn = 0;
	queue[0].fn = queue[0].gn + queue[0].hn;
	
	while(1)
	{
		/////////////////////////////////////////////////////////////////
		// Find the node which f(n) is minimal
		/////////////////////////////////////////////////////////////////
		// Find first node is not removed from queue
		cur = -1;
		for(int i = 0; i < last; i++)
			if(queue[i].notRemoved)
			{
				cur = i;
				break;
			}
		// Find the node which is minimal
		for(int i = cur + 1; i < last; i++)
			if(queue[i].notRemoved)
			{
				if(queue[i].fn < queue[cur].fn)
					cur = i;
			}
		
		/////////////////////////////////////////////////////////////////
		// Check cur is goal node or not
		/////////////////////////////////////////////////////////////////
		if(cur == -1) // If Queue is empty, faile
		{
			ok = false;
			numStates = last;
			return;
		} 
		else if(queue[cur].hn == 0) // If cur is goal node
		{
			ok = true;
			track = cur;
			numStates = last;
			return;
		}
		
		//////////////////////////////////////////////////////////////
		// Remove cur from Queue. Add to Queue all cur's children
		//////////////////////////////////////////////////////////////
		// Remove cur from Queue
		queue[cur].notRemoved = false;
		// Add to Queue all cur's children
		for(int i = 0; i < 4; i++)
		{
			int new_x = queue[cur].x + dx[i];
			int new_y = queue[cur].y + dy[i];
			if(new_x < 0 || new_x > 2 || new_y < 0 || new_y > 2)
				continue;
			
			queue[last] = queue[cur];
			queue[last].swapTile(new_x, new_y);
			queue[last].pre = cur;
			
			//  Check for a node is same one of its fathers
			int k = cur;
			while(k != -1)
			{
				if(isEqual(queue[last], queue[k]))
					break;
				k = queue[k].pre;
			}
			if(k >= 0)
				continue;
			
			queue[last].hn = heuristicFunc(queue[last], end);
			queue[last].gn = queue[cur].gn + 1;
			queue[last].fn = queue[last].gn + queue[last].hn;
			queue[last].notRemoved = true;
			last++;
			
			if(last > 250000)
			{
				ok = false;
				numStates = last;
				return;
			}
		}
	}
}