#include <iostream>
#include <math.h>

#define FIL 7
#define COL 7

int m[FIL][COL] = {
    {0,1,0,0,0,0,0},
    {0,1,2,3,0,0,0},
    {0,3,4,4,0,0,0},
    {0,0,0,5,0,0,0},
    {0,0,0,7,6,0,0},
    {0,0,0,0,7,8,9},
    {0,0,0,0,8,9,0}
};

using namespace std;

void imprimir(int m[FIL][COL]);
void wait ( int seconds );

void determinar(int i, int j, int *c)
{ 
     int a = m[i][j];
     c[0] = *c + 1;
     imprimir (m);
     cout<<"BackTracking"<<endl;
     
     if(m[i][j]+1==m[i+1][j+1])
        {   
        determinar(i+1,j+1,c);
	    }
     if(m[i][j]+1==m[i][j+1])
        {
		determinar(i,j+1,c);
	    }
     if(m[i][j]+1==m[i+1][j])
	    {
		determinar(i+1,j ,c);
        }
     m[i][j]=a;

}

    
int main()
{
    int c=0;
    determinar(0, 0, &c);
    system("pause");
}

void wait ( int seconds )
{
    clock_t endwait;
    endwait = clock () + seconds * (CLOCKS_PER_SEC/2) ;
    while (clock() < endwait) {}
}

void imprimir(int m[FIL][COL])
{
	wait(1);
	cout<<"----------------------------"<<endl;
	for(int i = 0; i<FIL; i++)
	{
		cout<<"|";
		for(int j = 0; j<COL; j++)
		{
		if(m[i][j]+1==m[i+1][j+1]||m[i][j]+1==m[i][j+1]||m[i][j] == m[i][j]+1==m[i+1][j])
                cout<<" "<<"X"<<" |";
			else
                cout<<"   |";
		}
		cout<<endl;
	}
	cout<<"----------------------------"<<endl;
}