labyrith

Labyrinth-Revisited

    A. Fourth? Edition

    This is the intermediate version of my 15 puzzle. And it is not surprise to ask what is relation

    between this labyrinth-finding question and 15 puzzle. I want to use a "snake" to represent my

    path on board. This "snake" or "Cluster" can grow and move step by step. It is the path for "space"

    to move. It can also be the body of a "string of numbers", i.e. 1234. You will see that on 15 puzzle

    your goal is to make a correct sequence of numbers. If you can see this, you will understand what

    I want to do.

    B.The problem

The 15 puzzle? Or the path for a node to move? Or the path for a cluster of number to move, like snake? Or the

number cluster itself?

¡¡

C.The idea of program
¡¡

    Since I have to memorize all coordinate I have been in the labyrinth, there is no better way than a simple DFS. I would not

    bother to find any algorithm, as all algorithms require you to memorize the position you have been to.

    D.The major functions

    ¡¡

    E.Further improvement

    The next step is to implement the move a single node on board, then the whole cluster move.

    F.File listing

    1. node.h

    2. node.cpp

    3. cluster.h

    4. cluster.cpp

    5. board.h

    6. board.cpp

    7. main.cpp

    ¡¡

    file name: node.h

    #ifndef NODE_H
    #define NODE_H

    #include <stdio.h>
    #include <math.h>

    const int BoardSize=4;
    const int MaxNodesLength=BoardSize*2-1;
    const int MaxBoardSize=10;
    const int MinimumRotateSize=2;

    //#define abs(x) (x>=0?x:-x)

    enum Direction
    {
    	U, R , D , L, None
    };

    enum Position
    {
    	Right, DownRight, Down, DownLeft, Left, UpLeft, Up, UpRight
    };

    //class Puzzle;

    class Coord
    {
    	friend class Board;
    private:
    	int row;
    	int col;
    public:
    	const Coord& operator=(const Coord& rhs);
    	bool operator==(const Coord& rhs) const;
    	bool operator!=(const Coord& rhs) const ;
    	bool neighbour(const Coord& rhs) const;
    	void move(Direction dir);
    	Coord(int r=-1, int c=-1);
    };

    #endif

    ¡¡

    file name: node.cpp

    #include "cluster.h"
    #include <math.h>

    const Coord Cluster::getHead()
    {
    	return nodes[head];
    }

    bool Cluster::removeHead()
    {
    	if (length==0)
    	{
    		return false;
    	}
    	else
    	{
    		length--;
    		head=(head+1)%MaxNodesLength;
    	}
    	return true;
    }

    void Cluster::clear()
    {
    	initialize();
    }

    bool Cluster::step(Direction dir)
    {
    	Coord dummy;
    	dummy=nodes[head];
    	dummy.move(dir);
    	return step(dummy);
    }

    //valid for two meanings:
    //1. not eat any node
    //2. adjacent to head
    bool Cluster::step(const Coord& newPos)
    {
    	//don't bite your tail or body
    	if (isNode(newPos))
    	{
    		return false;
    	}
    	//can you bite too far?
    	if (!nodes[head].neighbour(newPos))
    	{
    		return false;
    	}
    	head--;
    	if (head<0)
    	{
    		head+=MaxNodesLength;
    	}
    	nodes[head]=newPos;
    	return true;
    }

    bool Cluster::isNode(const Coord& rhs)
    {
    	for (int i=0; i<length; i++)
    	{
    		if (this->operator[](i)==rhs)
    		{
    			return true;
    		}
    	}
    	return false;
    }

    void Cluster::initialize()
    {
    	head=-1;
    	length=0;
    }

    Cluster::Cluster()
    {
    	initialize();
    }

    //unless it is first time or cleared, you cannot set head
    //when it already has one
    bool Cluster::setHead(const Coord& first)
    {
    	if (head!=-1)
    	{
    		return false;
    	}
    	head=0;
    	length=1;
    	nodes[head]=first;
    	return true;
    }

    bool Cluster::addTail(const Coord& newTail)
    {
    	int tail=(head+length)%MaxNodesLength;
    	if (length==MaxNodesLength)
    	{
    		return false;
    	}
    	if (isNode(newTail))
    	{
    		return false;
    	}
    	if (!nodes[tail].neighbour(newTail))
    	{
    		return false;
    	}

    	length++;
    	tail=(head+length)%MaxNodesLength;
    	nodes[tail]=newTail;
    	return true;
    }

    int Cluster::index(const Coord& pos) const
    {
    	for (int i=0; i<length; i++)
    	{
    		if (this->operator [](i)==pos)
    		{
    			return i;
    		}
    	}
    	return -1;
    }

    bool Cluster::addHead(const Coord& newHead)
    {
    	if (length==MaxNodesLength)
    	{
    		return false;
    	}
    	if (isNode(newHead))
    	{
    		return false;
    	}
    	if (!nodes[head].neighbour(newHead))
    	{
    		return false;
    	}
    	length++;
    	head--;
    	if (head<0)
    	{
    		head+=MaxNodesLength;
    	}

    	nodes[head]=newHead;
    	return true;
    }

    Coord Cluster::operator [](int index) const
    {
    	return nodes[(head+index)%MaxNodesLength];
    }

    ¡¡

    file name: cluster.h

    #include <stdio.h>
    #include "node.h"

    class Cluster
    {
    private:
    	int length;
    	Coord nodes[MaxNodesLength];
    	//bool ascending;
    	int head;//this is the head pos, as head is moving
    	void initialize();
    public:
    	void clear();
    	const Coord getHead();
    	bool step(const Coord& newPos);//must be a valid move
    	bool step(Direction dir);
    	bool addTail(const Coord& newTail);
    	bool isNode(const Coord& rhs);
    	bool addHead(const Coord& newHead);
    	bool removeHead();
    	bool setHead(const Coord& first);
    	Coord operator[](int index) const;
    	int index(const Coord& pos) const;
    	Cluster();
    };

    file name: cluster.cpp

    #include "cluster.h"
    #include <math.h>

    const Coord Cluster::getHead()
    {
    	return nodes[head];
    }

    bool Cluster::removeHead()
    {
    	if (length==0)
    	{
    		return false;
    	}
    	else
    	{
    		length--;
    		head=(head+1)%MaxNodesLength;
    	}
    	return true;
    }

    void Cluster::clear()
    {
    	initialize();
    }

    bool Cluster::step(Direction dir)
    {
    	Coord dummy;
    	dummy=nodes[head];
    	dummy.move(dir);
    	return step(dummy);
    }

    //valid for two meanings:
    //1. not eat any node
    //2. adjacent to head
    bool Cluster::step(const Coord& newPos)
    {
    	//don't bite your tail or body
    	if (isNode(newPos))
    	{
    		return false;
    	}
    	//can you bite too far?
    	if (!nodes[head].neighbour(newPos))
    	{
    		return false;
    	}
    	head--;
    	if (head<0)
    	{
    		head+=MaxNodesLength;
    	}
    	nodes[head]=newPos;
    	return true;
    }

    bool Cluster::isNode(const Coord& rhs)
    {
    	for (int i=0; i<length; i++)
    	{
    		if (this->operator[](i)==rhs)
    		{
    			return true;
    		}
    	}
    	return false;
    }

    void Cluster::initialize()
    {
    	head=-1;
    	length=0;
    }

    Cluster::Cluster()
    {
    	initialize();
    }

    //unless it is first time or cleared, you cannot set head
    //when it already has one
    bool Cluster::setHead(const Coord& first)
    {
    	if (head!=-1)
    	{
    		return false;
    	}
    	head=0;
    	length=1;
    	nodes[head]=first;
    	return true;
    }

    bool Cluster::addTail(const Coord& newTail)
    {
    	int tail=(head+length)%MaxNodesLength;
    	if (length==MaxNodesLength)
    	{
    		return false;
    	}
    	if (isNode(newTail))
    	{
    		return false;
    	}
    	if (!nodes[tail].neighbour(newTail))
    	{
    		return false;
    	}

    	length++;
    	tail=(head+length)%MaxNodesLength;
    	nodes[tail]=newTail;
    	return true;
    }

    int Cluster::index(const Coord& pos) const
    {
    	for (int i=0; i<length; i++)
    	{
    		if (this->operator [](i)==pos)
    		{
    			return i;
    		}
    	}
    	return -1;
    }

    bool Cluster::addHead(const Coord& newHead)
    {
    	if (length==MaxNodesLength)
    	{
    		return false;
    	}
    	if (isNode(newHead))
    	{
    		return false;
    	}
    	if (!nodes[head].neighbour(newHead))
    	{
    		return false;
    	}
    	length++;
    	head--;
    	if (head<0)
    	{
    		head+=MaxNodesLength;
    	}

    	nodes[head]=newHead;
    	return true;
    }

    Coord Cluster::operator [](int index) const
    {
    	return nodes[(head+index)%MaxNodesLength];
    }

    ¡¡

    file name: board.h

    #include "cluster.h"
    #include "node.h"

    class Board
    {
    	friend class Cluster;
    private:
    	int board [BoardSize][BoardSize];
    	bool map[BoardSize][BoardSize];
    	bool restrict[BoardSize][BoardSize];
    	Cluster path;
    	int size;
    	void initialize();
    	bool valid(const Coord& pos);
    	Direction findDir(const Coord& start, const Coord& end);
    	Direction findNextDir(const Coord& curr, Direction dir);
    	bool impasse(const Coord& curr, Direction dir);
    	bool doPathFinding(const Coord& curr, const Coord& end, Direction dir);
    public:
    	Board(int theSize=BoardSize);
    	void display();
    	void displayPath(bool showPath=true);
    	bool pathFinding(const Coord& start, const Coord& end);
    	bool pathFinding(const Coord& end);
    	bool pathFinding2(const Coord& start, const Coord& end);
    	void setRestrict(const Coord& pos);
    	void resetRestrict(const Coord& pos);
    };

    file name: board.cpp

    #include "board.h"

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

    void Board::displayPath(bool showPath)
    {
    	Coord curr;
    	int index;
    	for (int i=0; i<size; i++)
    	{
    		for (int j=0; j<size; j++)
    		{
    			curr.row=i;
    			curr.col=j;
    			index=path.index(curr);
    			if (index!=-1)
    			{
    				if (showPath)
    				{
    					printf("%2d\t", index);
    				}
    				else
    				{
    					printf("%2d\t", board[i][j]);
    				}
    			}
    			else
    			{
    				printf("%c%c\t", '*', '*');
    			}
    		}
    		printf("\n");
    	}
    }

    //this is the rather direct path
    bool Board::pathFinding(const Coord& start, const Coord& end)
    {
    	Coord curr;
    	Direction dir;
    	path.clear();
    	path.setHead(start);
    	curr=path.getHead();
    	while (curr!=end)
    	{
    		dir=findDir(curr, end);
    		curr.move(dir);
    		if (valid(curr))
    		{
    			path.addHead(curr);
    			curr=path.getHead();//??not necessary
    		}
    		else
    		{
    			//it must be something restricted and it is a
    			//a more generate way of finding path
    			for (int i=0; i<size; i++)
    			{
    				for (int j=0; j<size; j++)
    				{
    					map[i][j]=false;
    				}
    			}
    			map[start.row][start.col]=true;//I am here!!!
    			path.clear();//restart!!
    			path.setHead(start);
    			return pathFinding2(start, end);
    		}
    	}
    	return true;
    }

    bool Board::pathFinding2(const Coord& start, const Coord& end)
    {
    	Coord curr;
    	if (start==end)
    	{
    		return true;
    	}
    	for (int dir=0; dir<4; dir++)
    	{
    		curr=start;
    		curr.move((Direction)dir);
    		if (valid(curr))
    		{
    			if (!map[curr.row][curr.col])
    			{
    				path.addHead(curr);
    				map[curr.row][curr.col]=true;
    				if (pathFinding2(curr, end))
    				{
    					return true;
    				}
    				else
    				{
    					path.removeHead();
    					//anyway, I have been here before
    					//map[curr.row][curr.col]=false;
    				}
    			}
    		}
    	}
    	return false;
    }

    void Board::setRestrict(const Coord& pos)
    {
    	restrict[pos.row][pos.col]=true;
    }

    void Board::resetRestrict(const Coord& pos)
    {
    	restrict[pos.row][pos.col]=false;
    }

    bool Board::impasse(const Coord& curr, Direction dir)
    {
    	Coord dummy;
    	dummy=curr;
    	dummy.move(dir);
    	return valid(dummy);
    }

    //this way has a fatal problem of circling
    Direction Board::findNextDir(const Coord& curr, Direction dir)
    {
    	Direction result=dir, turnLeft;
    	//first try old direction,
    	while (impasse(curr, result))
    	{
    		//cannot advance, so turn right, or next dir
    		result=(Direction)((result+1)%4);
    	}
    	if (result!=dir)//means we already turned to right, so, return
    	{
    		return result;
    	}
    	else
    	{
    		//we must turn to left BEFORE we run into wall
    		turnLeft=result;//initialize
    		do
    		{
    			result=turnLeft;//must!!!
    			turnLeft=(Direction)(result-1<0?3:result-1);
    		}while (!impasse(curr, turnLeft));
    		return result;//result is the dir before turning left
    	}
    }

    bool Board::pathFinding(const Coord& end)
    {
    	Coord curr;
    	Direction dir;
    	curr=path.getHead();
    	//in what case, should I return false? a dead end?
    	dir=findDir(curr, end);
    	while (curr!=end)
    	{
    		dir=findNextDir(curr, dir);
    		curr.move(dir);
    		path.addHead(curr);
    		curr=path.getHead();
    	}
    	return true;
    }

    Direction Board::findDir(const Coord& start, const Coord& end)
    {
    	int rOff, cOff;
    	rOff=end.row-start.row;
    	cOff=end.col-start.col;
    	if (abs(rOff)>abs(cOff))
    	{
    		return rOff>0?D:U;
    	}
    	else
    	{
    		return cOff>0?R:L;
    	}
    }

    Board::Board(int theSize)
    {
    	size=theSize;
    	initialize();

    }

    bool Board::valid(const Coord& pos)
    {
    	if (pos.col<0||pos.row<0||pos.col>=size||pos.row>=size)
    	{
    		return false;
    	}
    	return !restrict[pos.row][pos.col];
    }

    void Board::display()
    {
    	printf("the size of board is %d\n", size);
    	for (int i=0; i<size; i++)
    	{
    		for(int j=0; j<size; j++)
    		{
    			printf("%2d\t", board[i][j]);
    		}
    		printf("\n");
    	}
    }

    void Board::initialize()
    {
    	for (int i=0; i<size; i++)
    	{
    		for (int j=0; j<size; j++)
    		{
    			board[i][j]=settings[i][j];
    			restrict[i][j]=false;
    		}
    	}
    }

    file name: main.cpp

    #include <stdio.h>
    #include "board.h"
    #include "node.h"

    int main()
    {
    	Board B;
    	Coord start(0,3), end(3,1), temp(2,2), temp1(3,3);
    	B.setRestrict(temp);
    	B.setRestrict(temp1);
    	B.pathFinding(start, end);
    	B.displayPath();
    	return 0;
    }

    ¡¡

    The result is like following:

    ** 2 3 6
    ** 1 4 5
    ** 0 ** **
    ** ** ** **
    Press any key to continue