//<body bgcolor=000000 text=00ff00><pre>
#pragma warning(disable:4786)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
typedef vector<int> vint;
int pos(int n,int m)    ////compute the number on the point (a,b);

{
	if(n==0) return m-1;
	else if(n==1) return m+2;
	else if(n==2) return m+7;
	else if(n==3) return m+14;
	else if(n==4) return m+21;
	else if(n==5) return 26+m;
	else if(n==6) return 29+m;
	return 0;
}

bool solution(int board[7][7],int n,vint& result)///put the result in the 
                                                 ///"result";
{
	int i,j,sum=0;
	for(j=0;j<n;j++)for( i=0;i<n;i++)
	{
		if(board[j][i]==1) sum+=1;////compute the number ofleftover
	}

	if(sum==1) return(1);//only one left;(reached the lower bound) add &&board.at(0) fix the point
	for(i=0;i<n;i++)        
	for(j=0;j<n;j++)
	if(abs(i-3)<2||abs(j-3)<2)
	if(board[i][j]==1)
	{

		if((abs(i+2-3)<2||abs(j-3)<2)&&i+2<n){if(board[i+1][j]==1&&board[i+2][j]==0)
			{
				board[i][j]=0;board[i+1][j]=0;board[i+2][j]=1;
				if(solution(board,n, result))
				{result.push_back(pos(i+2,j));result.push_back(pos(i,j));return 1;}
				else
				{
					board[i][j]=1;board[i+1][j]=1;board[i+2][j]=0;
		}}
		}if((abs(i-2-3)<2||abs(j-3)<2)&&i-2>0){if(board[i-1][j]==1&&board[i-2][j]==0)
			{
				board[i][j]=0;board[i-1][j]=0;board[i-2][j]=1;
				if(solution(board,n, result))
				{result.push_back(pos(i-2,j));result.push_back(pos(i,j));return 1;}
				else
				{
					board[i][j]=1;board[i-1][j]=1;board[i-2][j]=0;
		}}
		}if((abs(i-3)<2||abs(j+2-3)<2)&&j+2<n){if(board[i][j+1]==1&&board[i][j+2]==0)
			{
				board[i][j]=0;board[i][j+1]=0;board[i][j+2]=1;
				if(solution(board,n, result))
				{result.push_back(pos(i,j+2));result.push_back(pos(i,j));return 1;}
				else
				{
					board[i][j]=1;board[i][j+1]=1;board[i][j+2]=0;
		}}
		}if((abs(i-3)<2||abs(j-2-3)<2)&&j-2>0){if(board[i][j-1]==1&&board[i][j-2]==0)
			{
				board[i][j]=0;board[i][j-1]=0;board[i][j-2]=1;
				if(solution(board,n, result))
				{result.push_back(pos(i,j-2));result.push_back(pos(i,j));return 1; }
				else
				{
					board[i][j]=1;board[i][j-1]=1;board[i][j-2]=0;
				}
		}}

	}

	return 0;
}

int main()
{
	int i,j,n=1;
	int board[7][7];
	vint record;
	record.clear();
	ofstream ii("result");
	for(j=0;j<7;j++)
	{
		for(i=0;i<7;i++)
		{
		if(abs(i-3)<2||abs(j-3)<2)board[j][i]=1;
		else board[j][i]=0;
		}
	}
	board[3][3]=0;
	if(solution(board,7,record))
	{
		cout<<endl;
		ii<<endl;
		while(!record.empty())
		{
			cout<<record.back();ii<<record.back();
			cout<<" to ";ii<<" to ";
			record.pop_back();
			cout<<record.back();ii<<record.back();
			record.pop_back();
			ii<<endl;cout<<endl;
		}
	}
	else cout<<"\n Sorry,there is no solution!\n\n\n";
	return 0;

}

