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

struct stack_item {
   int from;
   int to;
   int remove;
};
stack_item stack[13];
int start;
int board[16] = {     1,
		     1,1,
		    1,1,1,
		   1,1,1,1,
		  1,1,1,1,1};

int Start() {
int pos;
cout << "Where's the blank at? (1-15) : ";
cin >> pos;
return pos-1;
}

void Menu(int& from, int& to) {
cout << setiosflags (ios::right) << setw(19) << board[0] << endl;
cout << setw(18) << board[1] << ' ' << board[2] << endl;
cout << setw(17) << board[3] << ' ' << board[4] << ' ' << board[5] << endl;
cout << setw(16) << board[6] << ' ' << board[7] << ' '
		 << board[8] << ' ' << board[9] << endl;
cout << setw(15) << board[10] << ' ' << board[11] << ' ' << board[12] << ' '
		 << board[13] << ' ' << board[14] << endl << endl;
cout << "Move from (1 - 15, 0 to quit, -1 to backup) : ";
cin >> from;
if (from != 0 && from != -1) {
   cout << "Move to (1 - 15) : ";
   cin >> to;
   }
}

void Score(int pegs,int moves)
{
cout << pegs << " pegs left.  ";
switch (pegs) {
   case 1 : {cout << "Excellent!  You solved the puzzle!\n"; 
            ofstream fout("winners", ios::app);
            cout << "Enter your name : ";
            char name[80];
            cin.ignore (80,'\n');
            cin.getline (name,80,'\n');
            fout << name << endl;
            fout << "Blank was initially at : " << stack[0].to+1 << endl;
	    int i;
	    for (i=0; i<moves; i++) 
	       fout << "From : " << setw(2) << stack[i].from+1
		    << " To : " << setw(2) << stack[i].to+1 << endl;
            fout.close();
	    break;}
   case 2 : cout << "Very Good!  Keep on trying!\n"; break;
   case 3 : cout << "Not too bad...keep at it!\n"; break;
   case 4 : cout << "You need some work!  Play again!\n"; break;
   case 5 : cout << "Wow!  You really SUCK!\n"; break;
   case 6 : cout << "You must be drunk!\n"; break;
   case 7 : cout << "Hello? Kathy?\n"; break;
   case 8 : cout << "Hello? Kathy's Dad?\n"; break;
   case 9 : cout << "Wow!  Your score is less than Kathy's breast size!\n"; break;
   case 10: cout << "You scored Kathy's IQ!\n"; break;
   case 11: cout << "Number of pegs = Number of Kathy's credit cards!\n"; break;
   case 12: cout << "Man, you're worse than Kathy!\n"; break;
   case 13: cout << "What the hell is wrong with you?\n"; break;
   case 14: cout << "You're an idiot...seek help...even from Kathy!\n"; break;
   default: break;
   }
}

bool Check_Move(int from, int to, int& r)
{
int to2=to-1;
if (board[from-1] != 1) 
   return false;
if (board [to2] !=0)
   return false;
switch (from-1) {
   case 0 : if (((to2==3) || (to2==5)) && (board[to2/2]==1)) {
	       r = to2/2;
	       return true;
	       }
	    break;
   case 1 : if (((to2==6) || (to2==8)) && (board[(to2)/2]==1)) {
	       r = to2/2;
	       return true;
	       }
	    break;
   case 2 : if (((to2==7) || (to2==9)) && (board[(to2+1)/2]==1)) {
	       r = (to2+1)/2;
	       return true;
	       }
	    break;
   case 3 : if ((to2==0 && board[1]==1 && (r=1)) || 
		(to2==5 && board[4]==1 && (r=4)) ||
		(to2==10 && board[6]==1 && (r=6)) || 
		(to2==12 && board[7]==1 && (r=7)))
		   return true;
	    break;
   case 4 : if ((to2==11 && board[7]==1 && (r=7)) || 
		(to2==13 && board[8]==1 && (r=8)))
		   return true;
	    break;
   case 5 : if ((to2==0 && board[2]==1 && (r=2)) || 
		(to2==3 && board[4]==1 && (r=4)) ||
		(to2==12 && board[8]==1 && (r=8)) || 
		(to2==14 && board[9]==1 && (r=9)))
		   return true;
	    break;
   case 6 : if ((to2==1 && board[3]==1 && (r=3)) || 
		(to2==8 && board[7]==1 && (r=7)))
		   return true;
	    break;
   case 7 : if ((to2==2 && board[4]==1 && (r=4)) || 
		(to2==9 && board[8]==1 && (r=8)))
		   return true;
	    break;
   case 8 : if ((to2==1 && board[4]==1 && (r=4)) || 
		(to2==6 && board[7]==1 && (r=7)))
		   return true;
	    break;
   case 9 : if ((to2==2 && board[5]==1 && (r=5)) || 
		(to2==7 && board[8]==1 && (r=8)))
		   return true;
	    break;
   case 10: if ((to2==3 && board[6]==1 && (r=6)) || 
		(to2==12 && board[11]==1 && (r=11)))
		   return true;
	    break;
   case 11: if ((to2==4 && board[7]==1 && (r=7)) || 
		(to2==13 && board[12]==1 && (r=12)))
		   return true;
	    break;
   case 12: if ((to2==10 && board[11]==1 && (r=11)) || 
		(to2==14 && board[13]==1 && (r=13)) ||
		(to2==5 && board[8]==1 && (r=8)) || 
		(to2==3 && board[7]==1 && (r=7)))
		   return true;
	    break;
   case 13: if ((to2==11 && board[12]==1 && (r=12)) || 
		(to2==4 && board[8]==1 && (r=8)))
		   return true;
	    break;
   case 14: if ((to2==12 && board[13]==1 && (r=13)) || 
		(to2==5 && board[9]==1 && (r=9)))
		   return true;
	    break;
   default:return false; break;
   }
return false;
}

void Make_Move(int from, int to, int remove, int& moves, int& pegs)
{
board[from-1]=0;
board[to-1]=1;
board[remove]=0;
stack[moves].from = from-1;
stack[moves].to = to-1;
stack[moves].remove = remove;
moves++;
pegs--;
}

void backup (int& moves, int& pegs)
{
if (moves == 0) 
   return;
moves--;
pegs++;
board[stack[moves].to] = 0;
board[stack[moves].from] = 1;
board[stack[moves].remove] = 1;
}


int main() {
int from,to,remove;
start = Start() + 1;
board[start - 1] = 0;
int pegs = 14;
int moves = 0;
while (pegs > 1) {
   Menu(from, to);
   if (from == 0) {
      Score(pegs, moves);
      exit(1);
      }
   if (from == -1) 
      backup(moves,pegs);
   else 
      if (Check_Move(from, to, remove))
	 Make_Move(from, to,remove,moves,pegs);
      else
         cout << "Invalid move!\n";
   }   
Score(pegs, moves);
}