#include <allinc.h>
int maximumidiotrun;

int main2(int,int);
bool display(apmatrix <double> &,apvector <double> &,bool);
void main()
{
	randomize();
   ofstream ouf;
   ouf.open("zmatrix2Z.xls");
   ouf<<"COL\tROW\tTOTAL\tITER\tAVG\tMAX\n";
   for(int C=7; C<=7; C++)
   {
   	int R=C;
      cout<<"\nC="<<C<<" ";
	   double total=0;
	   int maximum=-1;
      int i;
      maximumidiotrun=0;
		for(i=0; i<30000; i++)
	   {
	   	int result=main2(C,R);
	      total+=result;
	      if(maximum<result)
	      	maximum=result;
	   }
      ouf<<C<<'\t'
         <<R<<'\t'
         <<total<<'\t'
         <<i<<'\t'
         <<total/i<<'\t'
         <<maximum<<'\n';
   }
   //getch();
}
int main2(int C, int R)
//returns number of steps taken by random board
{
   apvector <double> sol(R*C,-1);
	apmatrix <double> a(R*C,R*C+1,0);

	for(int A=1; A<=R; A++)// <-regular A, not [A]
	{
		for(int B=1; B<=C; B++)
		{
			if(B!=1)
				a[B-1+(A-1)*C-1][B+(A-1)*C-1]=1;
			if(B!=C)
				a[B+1+(A-1)*C-1][B+(A-1)*C-1]=1;

			if(A!=1)
			{
				a[B+(A-2)*C-1][B+(A-1)*C-1]=1;
				if(B!=1)
					a[B-1+(A-2)*C-1][B+(A-1)*C-1]=1;
				if(B!=C)
					a[B+1+(A-2)*C-1][B+(A-1)*C-1]=1;
			}

			if(A!=R)
			{
				a[B+(A)*C-1][B+(A-1)*C-1]=1;
				if(B!=1)
					a[B-1+(A)*C-1][B+(A-1)*C-1]=1;
				if(B!=C)
					a[B+1+(A)*C-1][B+(A-1)*C-1]=1;
			}
		}
	}
 	//RANDOM BOARD GENERATOR//
   apvector <double> hitlist(R*C);
   for(int i=0; i<hitlist.length(); i++)
   	hitlist[i]=rand()%2;
   for(int i=0; i<a.numrows(); i++)
   	for(int j=0; j<a.numcols()-1; j++)
      	a[i][a.numcols()-1]+=a[i][j]*hitlist[j];
   //END OF RANDOM BOARD GEN//

   int checkcount=0;
	int target=0;//index at which the program changes stuff -1 -> 1 -> 0 -> -1+stepback
   do
   {
   	if(sol[target]==-1) sol[target]=1;
   	else if(sol[target]== 1) sol[target]=0;

	   if(display(a,sol,0))
	   {
         target++;
      }
	   else
   	{
         int temp=0;
         while(hitlist[temp]==sol[temp])
         	temp++;
         if(target-temp==R*C-2)
         //if(target-temp>maximumidiotrun)
         //if(0)
         {
	         maximumidiotrun=target-temp;
            //cout<<maximumidiotrun<<" ";
            display(a,sol,1);
			   for(int i=0; i<hitlist.length(); i++)
			   	if(hitlist[i]!=-1)
				   	cout<<hitlist[i]<<"";
			      else
			      	cout<<"X"<<"";
			   cout<<endl<<"MIR="<<target-temp<<endl;
            getch();
         }

	      while(sol[abs(target)]==0 && target>=0)
	      {
	      	sol[target]=-1;
	         target--;
	      }
      }
      checkcount++;
   }while(target>-1 && target<sol.length());
   if(target!=sol.length())
   	cout<<"Board has no solution. "<<checkcount<<"steps.\n";

   bool notright=false;
   for(int i=0; i<sol.length(); i++)
   	if(sol[i]!=hitlist[i])
      	notright=true;
   if(notright)//show inverted field
   {
   	cout<<"\nInversion:";
      for(int i=0; i<sol.length(); i++)
      {
         if(i%C==0)
         	cout<<endl;      
      	if(sol[i]-hitlist[i]==1)
         	cout<<"+";
         else if(sol[i]-hitlist[i]==0)
         	cout<<"o";
         else
         	cout<<"-";
      }
      cout<<endl;
      //getch();
   }




   //cout<<checkcount<<" ";
   return checkcount;
}

bool display(apmatrix <double> &a, apvector <double> &sol, bool show)
//Use: displays board and its validity.
//Args: array of coeffs and status, current working solution, toggle for displaying
//Returns: boardisok = true if no anomalies are found, false if an impossibility is found
//Note: a board is invalid if any line contains more than [status] mines or [neighborcount-status] clears.
{
   if(show)
	   gotoxy(1,1);
	bool boardisok=true;
	int X=0;
   for(int i=0; i<a.numrows(); i++)
   {
   	int coeff=0, minecount=0, clearcount=0;
   	for(int j=0; j<a.numcols(); j++)
      {
         if(show)
	         cout<<setw(X)<<a[i][j]<<"";
         if(a[i][j]==1 && j!=a.numcols()-1)
         {
         	coeff++;
            if(sol[j]==1)
            	minecount++;
            if(sol[j]==0)
            	clearcount++;
         }
      }
      if(minecount>a[i][a.numcols()-1] || clearcount>coeff-a[i][a.numcols()-1])
      	boardisok=false;
      if(show)
			cout<<"("<<coeff<<" "<<minecount<<"/"<<a[i][a.numcols()-1]<<" "<<clearcount<<"/"<<coeff-a[i][a.numcols()-1]<<")"<<endl;
   }
   if(show)
   {
	   for(int i=0; i<sol.length(); i++)
	   	if(sol[i]!=-1)
		   	cout<<setw(X)<<sol[i]<<"";
	      else
	      	cout<<setw(X)<<"X"<<"";
	   cout<<endl;
   }
   return boardisok;
}