failure

15Puzzle (This is a failure)

    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

    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--;
    	}

    }
    */

    The result is like following:

    failure!!!!