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