独立钻石.cpp

独立砖石求解算法独立砖石求解算法独立砖石求解算法独立砖石求解算法

//jason 2006.05.06---diamode
//dfs 
//didn't do some pruning... it will take long time if there is much chestmans 
#include<iostream>
using namespace std;

char solve[20][9][9]; // save the path
char map[9][9];        // the map of the diamond
int step,             //
    numofsol;         // numbers of resolvent

void creat_map()
{
int i,j;

for(i=0;i<9;i++)
map[0][i]=map[i][0]=map[8][i]=map[i][8]=' '; // verge

for(i=1;i<8;i++)
  for(j=1;j<8;j++) map[i][j]='.';        // '.' mean that you can go

  for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
map[i][j]=map[i][j+5]=map[i+5][j]=map[i+5][j+5]=' '; //verge

//map[1][6]=map[1][8]='~';map[2][7]='@';   //funny..
                                                         //'0' is chessman
map[2][4]=map[3][3]=map[3][4]=map[3][5]=map[4][4]=map[5][4]='0';  //crisscross
step=0;numofsol=0;                                       //you can creat others

}

void print()                    //print the resolvent
{
int i,j,s;

cout<<"\n -------------\n";
cout<<"< "<<"the solves"<<++numofsol<<" >\n";
cout<<" -------------\n";

     for(s=0;s<=step;s++)
	 {    cout<<"\nthe step"<<s<<":"<<endl;
	      for(i=0;i<9;i++)
		  {
		     for(j=0;j<9;j++)
			   cout<<solve[s][i][j]<<" ";
		     cout<<endl;
		  }
	 }
}

void solvedfs(int count)       //dfs solve 
{int i,j;

     for(i=0;i<9;i++)
		 for(j=0;j<9;j++)
			 solve[step][i][j]=map[i][j];     //save the path;

	if(count==1)
	{  
		if(solve[step][4][4]=='0')           // at the end of step,the chessman is in the middle of map
		print();
	}
	else
	{
		for(i=1;i<8;i++)
			for(j=1;j<8;j++)

				if(map[i][j]=='0')    //check...
				{
					if(map[i][j+2]=='.'&&map[i][j+1]=='0')  //go right
					{
						map[i][j]=map[i][j+1]='.';map[i][j+2]='0';step++;
						solvedfs(count-1);
                         map[i][j]=map[i][j+1]='0';map[i][j+2]='.';step--;

					}
					if(map[i+2][j]=='.'&&map[i+1][j]=='0') //go down
					{
	                    map[i][j]=map[i+1][j]='.';map[i+2][j]='0';step++;	              
                         solvedfs(count-1);
                         map[i][j]=map[i+1][j]='0';map[i+2][j]='.';step--;
					}

                    if(map[i][j-2]=='.'&&map[i][j-1]=='0')  //go left
					{
	                    map[i][j]=map[i][j-1]='.';map[i][j-2]='0';step++;
						solvedfs(count-1);
                        map[i][j]=map[i][j-1]='0';map[i][j-2]='.';step--;
					}
                    if(map[i-2][j]=='.'&&map[i-1][j]=='0')  //go up
					{
	                    map[i][j]=map[i-1][j]='.';map[i-2][j]='0';step++;
						solvedfs(count-1);
                         map[i][j]=map[i-1][j]='0';map[i-2][j]='.';step--;
					}
                    
				}
			
	}


}

int main()
{
creat_map();
solvedfs(6);
return 0;
}