package mapPass;
import stack.*;
public class MapPass 
{
    Stack s;
    int map[][]=new int[10][10];
    public MapPass(){}
    public boolean match(int nx,int ny)
    {
        if((nx==1&&ny==2)||(nx==1&&ny==4)||(nx==1&&ny==8)||(nx==2&&ny==1)
        ||(nx==2&&ny==3)||(nx==2&&ny==5)||(nx==2&&ny==7)||(nx==2&&ny==8)
        ||(nx==2&&ny==9)||(nx==2&&ny==10)||(nx==3&&ny==2)||(nx==3&&ny==4)
        ||(nx==3&&ny==5)||(nx==3&&ny==6)||(nx==3&&ny==9)||(nx==4&&ny==1)
    	||(nx==4&&ny==3)||(nx==4&&ny==5)||(nx==4&&ny==6)||(nx==5&&ny==2)
    	||(nx==5&&ny==3)||(nx==5&&ny==4)||(nx==5&&ny==6)||(nx==5&&ny==7)
    	||(nx==6&&ny==3)||(nx==6&&ny==4)||(nx==6&&ny==5)||(nx==7&&ny==2)
    	||(nx==7&&ny==5)||(nx==8&&ny==1)||(nx==8&&ny==2)||(nx==8&&ny==4)
    	||(nx==8&&ny==9)||(nx==8&&ny==10)||(nx==9&&ny==2)||(nx==9&&ny==3)
    	||(nx==9&&ny==4)||(nx==9&&ny==8)||(nx==9&&ny==10)||(nx==10&&ny==2)
    	||(nx==10&&ny==8)||(nx==10&&ny==9))return true;
    	else return false;
    }
    public boolean matchConstraint(int i,int j)
    {
    	MapElement test=(MapElement)s.peek();
        int number=test.number;
        int color=test.color;
    	for(int c=1;c<=s.getLength();c++)
    	{
    		if(j!=color) 
    		{
    			test=(MapElement)s.getNext();
    			if(c==s.getLength()) break;
    			return true;
    		}
    		else 
    		{
    			if(c==s.getLength()) return true;
    			if(this.match(number,i)) continue;
    			else break;
    		}
    	}
    	return false;
    }
    public Stack backtrack()
    {
    	s=new ArrayStack(10);
    	int i=1,j=1;
    	do
    	{
    		while(!(j>4)&&!(i>=this.map.length))
    		{
    			if(!matchConstraint(i,j))j++;
    			else break;
    		}
    		if(!(j>4))
    		{
    			this.map[i][i]=j;
    			MapElement element=new MapElement(i,j);
    			s.push(element);
    			i++;
    			j=1;
    		}
    		else if(!s.isEmpty())
    		{
    			MapElement element=(MapElement)s.peek();
    			i=element.number;
    			j=element.color;
    			s.pop();
    			j++;
    		}
    		else
    		{
    			System.out.println("Stack is empty!");
    		}
    	}while(i==10);
    	return s;
    }
    public static void main(String[] args) 
	{
        System.out.println("Have a test!");
        MapPass map=new MapPass();
        System.out.println(map.backtrack());
	}
}