A. third? Edition

There are several trials before and almost all of them are failures because I desperately want to try some fancy ideas.

After taking comp472 "Intro to AI", I want to go back to the track to do the most common DFS with heuristics.

B.The problem

Actually the title is a fake because I want to quickly run out of result, I change it to 9 puzzle. There are two versions

below, the first one is a decent DFS without heuristic and the second one is the one with heuristic of comparing distances

of each offset nodes. Of course the smaller, the better.

　

C.The idea of program

　

D.The major functions

There are few points to mention.

E.Further improvement

F.File listing
1. 15puzzle.cpp without heuristics.
2. 15puzzle.cpp with A* type of heuristics f(n)=g(n)+h(n) where h(n) is the sum of distances of all offset nodes
  　
  file name: 15puzzle.cpp (without heuristic and it is 8puzzle of course)
The result is like following:

failure!!!!

			

				                  

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

const int Dimension=3;
const int ChoiceNumber=4;
const int MaxDepth=1000;

/*
int startList[16]=
{
	1, 9, 10, 12, 
	0, 2, 11, 15,
	3, 4, 5,  14,
	13, 8, 7, 6
};

int goalList[16]=
{
	0,  1,  2,  3,
	4,  5,  6,  7,
	8,	9, 10, 11, 
	12,	13, 14, 15
};

*/

int startList[9]=
{
	1, 8, 3,
	0, 2, 5, 
	7, 4, 6
};

int goalList[9]=
{
	0,  1,  2,  
	3,	4,  5,  
	6,  7,	8	
};

enum EnumChoice
{
	Left=-1, Right=1, Up=-Dimension, Down=Dimension
};

int choices[ChoiceNumber]={Left, Right, Up, Down};

typedef vector<int> Puzzle;
typedef deque<Puzzle> Path;

class DFS
{
public:
	void initialize(int* startList, int* goalList);
	void run();
	bool generate();
	
protected:
	int depth;
	void display();
	void displayPuzzle(const Puzzle& puz);
	int getIndex(const Puzzle& puz);
	bool findInList(const Puzzle& puz, const Path& path);
	Puzzle current;
	Puzzle goal;
	Puzzle start;
	Path path;
	Path openList;
	Path closeList;
};

void DFS::displayPuzzle(const Puzzle& puz)
{
	for (int i=0; i<Dimension*Dimension; i++)
	{
		if (i!=0&&i%Dimension==0)
		{
			cout<<"\n";
		}
		cout<<puz[i]<<"   ";
	}
	cout<<"\n\n";
}

void DFS::initialize(int* startList, int* goalList)
{
	current.resize(Dimension*Dimension);
	goal.resize(Dimension*Dimension);
	for (int i=0; i<Dimension*Dimension; i++)
	{
		goal[i]=goalList[i];
		current[i]=startList[i];
	}
	openList.push_front(current);
}


void DFS::display()
{

	int index=0;
	
	for (Path::const_iterator it=path.begin(); it!=path.end(); it++)
	{
		cout<<"number "<<index<<":\n";

		displayPuzzle(*it);
		index++;
	}
	
}


void DFS::run()
{
	Puzzle result;
	bool ret;
	depth=0;
	while (!openList.empty())
	{
		ret=generate();
		current=openList.front();
		//openList.pop_front();
		if (ret)
		{		
			path.push_back(current);
		}
		else
		{
			closeList.push_front(current);
			openList.pop_front();
			path.pop_back();
		}
		if (current==goal)
		{
			display();
			break;
		}
		else
		{
			displayPuzzle(current);
		}
		depth++;
		if (depth==MaxDepth)
		{
			break;
		}
	}
	cout<<"no result\n";
	
}

int DFS::getIndex(const Puzzle& puz)
{
	int result;
	for (int i=0; i<Dimension*Dimension; i++)
	{
		if (puz[i]==0)
		{
			result=i;
			break;
		}
	}
	return result;
}

bool DFS::findInList(const Puzzle& puz, const Path& path)
{
	for (Path::const_iterator it=path.begin(); it!=path.end(); it++)
	{
		if (puz==*it)
		{
			return true;
		}
	}

	return false;
}


bool DFS::generate()
{
	bool result=false;
	int index=getIndex(current);
	int choiceIndex;
	Puzzle puz;
	for (int i=0; i<ChoiceNumber; i++)
	{
		choiceIndex=index+choices[i];
		if (choiceIndex<0||choiceIndex>=Dimension*Dimension)
		{
			continue;
		}
		puz=current;
		puz[choiceIndex]=current[index];
		puz[index]=current[choiceIndex];
		//if it is not in close list
		if (!findInList(puz, openList)&&!findInList(puz, closeList))
		{
			result=true;
			openList.push_front(puz);			
		}
	}
	return result;
}
		




int main()
{
	DFS dfs;
	dfs.initialize(startList, goalList);
	dfs.run();

	return 0;
}

file name: 15puzzle.cpp (with heuristic and it is 15puzzle of course)

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <deque>
#include <map>

using namespace std;

const int Dimension=4;
const int ChoiceNumber=4;
const int MaxDepth=100;


int startList[16]=
{
	1, 9, 10, 12, 
	0, 2, 11, 15,
	3, 4, 5,  14,
	13, 8, 7, 6
};

int goalList[16]=
{
	0,  1,  2,  3,
	4,  5,  6,  7,
	8,	9, 10, 11, 
	12,	13, 14, 15
};


/*
int startList[9]=
{
	1, 8, 3,
	0, 2, 5, 
	7, 4, 6
};

int goalList[9]=
{
	0,  1,  2,  
	3,	4,  5,  
	6,  7,	8	
};
*/
enum EnumChoice
{
	Left=-1, Right=1, Up=-Dimension, Down=Dimension
};

int choices[ChoiceNumber]={Left, Right, Up, Down};

typedef deque<int> Puzzle;

struct PathNode
{
	//PathNode* parent;
	int depth;
	int distance;
	Puzzle puzzle;
	Puzzle path;
};

/*
struct Node
{
	Puzzle puz;
	int distance;
};

struct NodeComp
{
	bool operator()(const Node& left, const Node& right)
	{
		return left.distance<right.distance;
	}
};
*/

class NodeComp
{
public:
	bool operator()(const PathNode& left, const PathNode& right)const
	{
		return left.distance<right.distance;
	}
};

//typedef deque<PathNode> Path;
//typedef list<PathNode, NodeComp> StateList;
typedef multiset<PathNode, NodeComp> StateList;

class DFS
{
public:
	void initialize(int* startList, int* goalList);
	void run();
	bool generate();
	
protected:
	int depth;
	int heuristic(const Puzzle& puz);
	bool doGenerate(const Puzzle& puz, int choice, Puzzle& result);
	void display();
	void displayPuzzle(const Puzzle& puz);
	int getIndex(const Puzzle& puz);
	void displayPath(const PathNode& path);
	void displayVector(const Puzzle& vect);
	void add2List(const PathNode& puz, StateList& lst);
	void removeFromList(StateList& lst);
	bool findInList(const PathNode& pathNode, const StateList& path);
	void displayList(const StateList& theList);
	PathNode current;
	Puzzle goal;
	Puzzle start;
	//Path path;
	StateList openList;
	StateList closeList;
};

void DFS::displayVector(const Puzzle& vect)
{
	cout<<"the vector is:\n";
	for (Puzzle::const_iterator it=vect.begin(); it!=vect.end(); it++)
	{
		cout<<*it<<"  ";
	}
	cout<<"\n";
}


void DFS::displayList(const StateList& theList)
{
	for (StateList::const_iterator it=theList.begin(); it!=theList.end(); it++)
	{
		displayPuzzle(it->puzzle);
	}
}

void DFS::displayPath(const PathNode& path)
{
	Puzzle puz=start, result;
	displayPuzzle(puz);
	for (Puzzle::const_iterator it=path.path.begin(); it!=path.path.end(); it++)
	{
		doGenerate(puz, *it, result);

		displayPuzzle(result);
		puz=result;
	}
}



/*
void DFS::displayPath(const PathNode& path)
{
	typedef deque<Puzzle> PathType;
	PathType myPath;
	Puzzle puz=path.puzzle, result;
	int index;
	//displayPuzzle(path.puzzle);
	//displayVector(path.path);
	//cout<<path.path[path.depth-2]<<endl;
	for (Puzzle::const_iterator it1=path.path.begin(); it1!=path.path.end(); it1++)
	{
		switch(*it1)
		{
		case 0:
			index=1;
			break;
		case 1:
			index=0;
			break;
		case 2:
			index=3;
			break;
		case 3:
			index=2;
			break;
		}
		if (!doGenerate(puz, index, result))
		{
			cout<<"unexpected!";
			exit(1);
		}

		myPath.push_back(result);
		puz=result;
	}
	for (PathType::const_iterator it2=myPath.begin(); it2!=myPath.end(); it2++)
	{
		displayPuzzle(*it2);
	}
}
*/
		


void DFS::displayPuzzle(const Puzzle& puz)
{
	for (int i=0; i<Dimension*Dimension; i++)
	{
		if (i!=0&&i%Dimension==0)
		{
			cout<<"\n";
		}
		cout<<puz[i]<<"   ";
	}
	cout<<"\n\n";
}

void DFS::initialize(int* startList, int* goalList)
{
	//Puzzle puzzle;;
	start.resize(Dimension*Dimension);
	goal.resize(Dimension*Dimension);
	for (int i=0; i<Dimension*Dimension; i++)
	{
		goal[i]=goalList[i];
		start[i]=startList[i];
	}
	current.depth=0; 
	//current.parent=NULL;
	current.puzzle=start;
	current.distance=heuristic(current.puzzle);
	add2List(current, openList);
}


void DFS::display()
{
	displayPath(current);
	
}

int DFS::heuristic(const Puzzle& puz)
{
	int result=0;
	int rowOffset, colOffset;
	for (int i=0; i<Dimension*Dimension; i++)
	{
		rowOffset=puz[i]%Dimension-i%Dimension;
		colOffset=puz[i]/Dimension-i/Dimension;
		if (rowOffset<0)
		{
			rowOffset=-rowOffset;
		}
		if (colOffset<0)
		{
			colOffset=-colOffset;
		}
		result+=rowOffset+colOffset;
	}
	return result;
}

void DFS::run()
{
	Puzzle result;
	bool ret;
	depth=0;
	while (!openList.empty())
	{	
		current=(*openList.begin());
		/*
		cout<<"now current is:\n";
		displayPuzzle(current.puzzle);
		cout<<"before remove from openlist\n";
		displayList(openList);
		*/
		removeFromList(openList);
		/*
		cout<<"after remove from openlist\n";
		displayList(openList);
		cout<<"before add to closelist\n";
		displayList(closeList);
		cout<<"and current is ?\n";
		displayPuzzle(current.puzzle);
		*/
		add2List(current, closeList);
		/*
		cout<<"after add to close list\n";
		displayList(closeList);
		*/
		ret=generate();

		if (current.puzzle==goal)
		{
			display();
			break;
		}
		else
		{
			//displayPuzzle(current.puzzle);
		}
		depth++;
		if (depth!=0&&depth%MaxDepth==0)
		{
			//break;
			cout<<"more than "<<depth<<" level\n";
		}
	}

	//cout<<"no result\n";
	//displayPath(current);
	
}

int DFS::getIndex(const Puzzle& puz)
{
	int result;
	for (int i=0; i<Dimension*Dimension; i++)
	{
		if (puz[i]==0)
		{
			result=i;
			break;
		}
	}
	return result;
}

bool DFS::findInList(const PathNode& path, const StateList& lst)
{
	for (StateList::const_iterator it=lst.begin(); it!=lst.end(); it++)
	{
		if (path.puzzle==(*it).puzzle)
		{
			return true;
		}
	}

	return false;
}

void DFS::add2List(const PathNode& path, StateList& lst)
{
	lst.insert(path);
}

void DFS::removeFromList(StateList& lst)
{
	lst.erase(lst.begin());
}

bool DFS::doGenerate(const Puzzle& puz, int choice, Puzzle& result)
{
	int index=getIndex(puz);
	int choiceIndex;
	int row=index/Dimension;
	int col=index%Dimension;
	switch (choices[choice])
	{
	case Left:
		row--;
		break;
	case Right:
		row++;
		break;
	case Up:
		col--;
		break;
	case Down:
		col++;
		break;
	}

	if (row<0||row>=Dimension||col<0||col>=Dimension)
	{
		return false;
	}
	choiceIndex=row*Dimension+col;
	result=puz;
	result[choiceIndex]=puz[index];
	result[index]=puz[choiceIndex];
	return true;
}

bool DFS::generate()
{
	bool result=false;
	//int index=getIndex(current.puzzle);
	//int choiceIndex;
	PathNode path;
	//Puzzle puz;
	//int row, col;

	for (int i=0; i<ChoiceNumber; i++)
	{	
		if (!doGenerate(current.puzzle, i, path.puzzle))
		{
			continue;
		}
		/*
		cout<<"my suspect puzzle:\n";
		displayPuzzle(path.puzzle);
		cout<<"\nand closeList:\n";
		displayList(closeList);
		cout<<"\nand openList:\n";
		displayList(openList);
		*/
		//if it is not in close list
		if (!findInList(path, openList)&&!findInList(path, closeList))
		{
			result=true;
			//add2List(puz, openList);
			path.depth=current.depth+1;
			//path.parent=&current;
			path.path=current.path;
			path.path.push_back(i);//push in the choice
			path.distance=heuristic(path.puzzle);
			add2List(path, openList);
		}
	}
	return result;
}
		




int main()
{
	DFS dfs;
	dfs.initialize(startList, goalList);
	dfs.run();

	return 0;
}









//recursive
/*
void DFS::displayPath(PathNode* path)
{
	if (path->parent==NULL)
	{
		displayPuzzle(path->puzzle);
	}
	else
	{
		displayPath(path->parent);
		displayPuzzle(path->puzzle);
	}
}
*/