#include <allinc.h>
//this version finds inversions

bool kosher(apmatrix <double> &, apvector <int> &);
void initialize_a(apmatrix <double> &,int,int);
void main()
{
	int R=1; //rowcount
   int C=5; //colcount
	apmatrix <double> a(R*C,R*C,0);
   initialize_a(a,R,C); //set up the relationships between tiles, basically

   apvector <int> sol(R*C,-2);

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

		   if(kosher(a,sol))
		   {
	         target++;
	      }
		   else
	   	{
		      while(sol[abs(target)]==-1 && target>=0)
		      {
		      	sol[target]=-2;
		         target--;
		      }
	      }
	   }while(target>-1 && target<sol.length()); //run until an inversion is found
      if(target>-1)//display the inversion
   	{
			for(int i=0; i<sol.length(); i++)
         {
         	if(i%C==0)
            	cout<<endl;
            if(sol[i]==1)
            	cout<<"+";
            else if(sol[i]==0)
            	cout<<"o";
            else if(sol[i]==-1)
            	cout<<"-";
            else
            	cout<<"?";
         }
         cout<<endl;
         getch();
      }
      target--;//get target in range
      //advance the tree- will occur automatically unless final term is -1, so check
	   while(sol[abs(target)]==-1 && target>=0)
      {
		 	sol[target]=-2;
		   target--;
		}
   }while(target>-1);
   cout<<"done"; getch();
}

bool kosher(apmatrix <double> &a, apvector <int> &sol)
//tells if current situation can possibly contain a solution
{
	bool iskosher=true;
   for(int i=0; i<a.numrows(); i++)
   {
   	int neighbor=0,pos=0,zero=0,neg=0;//counts of neighbors, and determined tiles
   	for(int j=0; j<a.numcols(); j++)
      {
      	if(a[i][j]==1)
         {
         	neighbor++;
            if(sol[j]==1)
            	pos++;
            else if(sol[j]==0)
            	zero++;
            else if(sol[j]==-1)
            	neg++;
         }
      }
      if(abs(pos-neg)>neighbor-pos-zero-neg)//if tile cannot be set to zero, not kosher
	     	iskosher=false;

   }
   return iskosher;
}


void initialize_a(apmatrix <double> &a, int R, int C)
{
	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;
			}
		}
	}
}