A. First Edition

This is only for version purpose and you can see I failed.

B.The problem

Do you know the problem? 4x4 board, 15 nodes with index number, scrambled, you need to move them around with

one space node so that the index number of each node  match its position index.

　

C.The idea of program

　

My problem is how to restrict the repeated loop. And I was wrong to only consider the loop of "space node". It is the entire 

15 nodes plus space to be considered! 

D.The major functions

There are few points to mention.

E.Further improvement

F.File listing
The result is like following:

failure!!!!

1. main.cpp (main)
  file name: main.cpp
			

				                 

#include <stdlib.h>
#include <iomanip>


using namespace std;

const MaxSearchDepth = 40;

const BoardSize = 4;

const ArraySize = 2000;

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

char dirStr[4]={'U', 'D' , 'L' , 'R'}; 

//int level=0;
Direction moves[ArraySize];
int cursor= 0;//the pointer to the records



struct Pos
{
	int row;
	int col;
}pos;

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

int current[BoardSize][BoardSize];

bool testCycle(Direction dir);

bool testMove(Direction dir);

void initialize();

void swap(Pos old);

bool generate(int level);

bool evaluate();

void advance(Direction dir);

//void restore(int mark);
void restore();

void display();



int main()
{
	initialize();
	generate(0);
	printf("the total level or cursor is:%d\n",cursor);
	for (int i=0; i<cursor; i++)
	{
		printf("%c, ", dirStr[moves[i]]);
	}
	printf("\n");

	return 0;
}


void initialize()
{
	for (int i=0; i<BoardSize; i++)
	{
		for (int j=0; j<BoardSize; j++)
		{
			current[i][j]=original[i][j];
			if (current[i][j]==0)
			{
				pos.row=i;
				pos.col=j;
			}
		}
	}
	cursor=0;
}


void display()
{
	for (int i =0; i <BoardSize; i++)
	{
		for (int j=0; j<BoardSize; j++)
		{
			//cout.setf(ios::left);			
			printf("%4d  ", current[i][j]);
		}
		printf("\n");
	}
}

bool evaluate()
{
	for (int i =0; i < BoardSize; i++)
	{
		for (int j=0; j<BoardSize; j++)
		{
			if (current[i][j]!=i*BoardSize+j)
			{
				return false;
			}
		}
	}
	return true;
}

bool testCycle(Direction dir)
{
	int r=0, c=0;
	int step=cursor;
	//int limit=(cursor-4>0)?cursor-4:0;
	Direction mov;
	moves[step]=dir;//pretend to write at end of array	
	while (step>=0)
	{
		mov=moves[step];
		switch (mov)
		{
		case U:
			r--;
			break;
		case D:
			r++;
			break;
		case R:
			c--;
			break;
		case L:
			c++;
			break;
		}
		if (r==0&&c==0)
		{
			return true;
		}
		step--;
	}
	return false;
}


bool testMove(Direction dir)
{
	Direction last=(Direction)-1;

	if (cursor>0)
	{
		last=moves[cursor-1];
	}
	
	switch (dir)
	{
	case U:
		if (last==D)
		{
			return false;
		}
		if (pos.row==0)
		{
			return false;
		}
		break;
	case D:
		if (last==U)
		{
			return false;
		}
		if (pos.row==BoardSize-1)
		{
			return false;
		}
		break;
	case R:
		if (last==L)
		{
			return false;
		}
		if (pos.col==BoardSize-1)
		{
			return false;
		}
		break;
	case L:
		if (last==R)
		{
			return false;
		}
		if (pos.col==0)
		{
			return false;
		}
		break;
	}

	return true;
}

void swap(Pos old)
{
	int temp;
	temp=current[old.row][old.col];
	current[old.row][old.col]=current[pos.row][pos.col];
	current[pos.row][pos.col]=temp;
}

void advance(Direction dir)
{
	Pos old;
	old.row=pos.row;
	old.col=pos.col;

	switch(dir)
	{
	case U:
		
		pos.row--;
		break;
	case D:
		pos.row++;
		break;
	case R:
		pos.col++;
		break;
	case L:
		pos.col--;
		break;
	}
	swap(old);
	moves[cursor++]=dir;
}

bool generate(int level)
{
	//bool isCycle;
	if (evaluate())
	{
		printf("\nfound it!\n");	
		return true;
	}	
	if (level==MaxSearchDepth)
	{
		return false;
	}
	//int mark;
	for (int i=0; i<4; i++)
	{		
		//mark=cursor;
		if (testMove((Direction)i))
		{
			//isCycle=testCycle((Direction)i);
			advance((Direction)i);
			/*
			if (isCycle&&!evaluate())
			{
				restore();
				continue;
			}
			*/

			
			printf("\nmoves[cursor] %c\n",dirStr[i]);
			//if (cursor%50==0)
			{
				display();
			}
						
			if (!generate(level+1))
			{
				restore();
				printf("\nafter restore \n");
				display();				
			}
			else
			{
				return true;
			}
		}
	}
	return false;
}


void restore()
{
	Pos old;
	Direction dir;
	old.row=pos.row;
	old.col=pos.col;
	dir=moves[--cursor];

	switch (dir)
	{
	case D:
		pos.row--;
		break;
	case U:
		pos.row++;
		break;
	case R:
		pos.col--;
		break;
	case L:
		pos.col++;
		break;
	}
	swap(old);
	//cursor--;
}


/*
void restore(int mark)
{
	Pos old;
	Direction dir;

	while (cursor>mark)
	{
		//cout<<"\nmoves[cursor] "<<dirStr[moves[cursor-1]]<<endl;
		//display();
		old.row=pos.row;
		old.col=pos.col;
		dir=moves[--cursor];

		switch (dir)
		{
		case D:
			pos.row--;
			break;
		case U:
			pos.row++;
			break;
		case R:
			pos.col--;
			break;
		case L:
			pos.col++;
			break;
		}
		swap(old);
		//cursor--;
	}

}
*/