#include<iostream> using namespace std; const int N=100; bool q[16],visited[16]; int path[N]; void printpath(int count) { static int cnt=0; printf("Solution %d:/n",cnt++); for(int i=0;i<count;i++) printf("(%d,%d,%d,%d)/n",(path[i]&8)>>3,(path[i]&4)>>2,(path[i]&2)>>1,path[i]&1); printf("/n"); } void fmr(int count,int f,int w,int s,int v) { int tmp=f*8+w*4+s*2+v; if(tmp==15){ path[count++]=15; printpath(count); } if(q[tmp]&&!visited[tmp])//valid state and has not been visited { visited[tmp]=true; path[count++]=tmp; fmr(count,(~f)&1,w,s,v); fmr(count,(~f)&1,(~w)&1,s,v); fmr(count,(~f)&1,w,(~s)&1,v); fmr(count,(~f)&1,w,s,(~v)&1); visited[tmp]=false; } } int main() { memset(path,0,sizeof(path)); memset(visited,false,sizeof(visited)); //Set state. for(int i=0;i<16;i++) q[i]=true; q[3]=false; q[6]=false; q[7]=false; q[8]=false; q[9]=false; q[12]=false; //0 represents right side and 1 represents the other. fmr(0,0,0,0,0); return 0; }
