public class Solver
{
	private int x;
	private int y;
	private KStack stack;
	public Solver()
	{
		stack = new KStack();
		x = 0;
		y = 0;
	}
	public void solve(KPuzzle puz)
	{
		puz.printPossibilities();
		boolean[] b = puz.getPossibilities(x,y);
		int numlen = 0;
		int lastplace = -1;
		System.out.println("looking for possibility in (" + x + "," + y + ")");
		for(for int i = 0; i < b.length; i++)
		{
			if(ba)
			{
				numlen++;
				lastplace = i;
			}
		}
		if(numlen == 1)
		{
			imply(x,y,lastplace)
		}
		else
		{
			for(int i = 0; i < b.length; i++)
			{
				System.out.println("Scanning: " + (i+1) + " : " + b[i]);
				if(b[i])
				{
					guess(x,y,i+1);
					puz.putNumber(x,y,i+1);
					x++;
					if(x > puz.size)
					{
						y++;
						x = 0;
					}
					solve(puz);
					int[] arr = stack.pop();
					puz.takeNumber(arr[1],arr[2]);
				}
				if(numlen == 0)
				{
					System.out.println("Exhausted possibilities, backtracking");
					return;
				}
			}
		}
		if(numlen == 1)
		{
			System.out.println("implying " + lastplace + " in (" + x + "," + y + ")");
			imply(x,y,lastplace);
			puz.putNumber(x,y,lastplace);
		}
		else if(numlen == 0)
		{
			//Pop everything to the last guess
			System.out.println("Found a cell with no possibilitys, backtracking");
			while(stack.peek()[0] == 1 && stack.getLength() > 1);
			{
				int[] arr = stack.pop();
				puz.removePossibility(arr[1],arr[2],arr[3]);
			}
		}
		else
		{
			System.out.println("Guessing " + lastplace + " in (" + x + "," + y + ")");
			guess(x,y,lastplace);
			puz.putNumber(x,y,lastplace);
			b[lastplace] = false;
		}
	}
	private void guess(int x, int y, int num)
	{
		int[] item = new int[4];
		item[0] = 1;
		item[1] = x;
		item[2] = y;
		item[3] = num;
		stack.push(item);
	}
	private void imply(int x, int y, int num)
	{
		int[] item = new int[4];
		item[0] = 0;
		item[1] = x;
		item[2] = y;
		item[3] = num;
		stack.push(item);
	}
	public class KStack
	{
		private KNode head;
		private int length;
		public KStack()
		{
			length = 0;
		}
		public int[] peek()
		{
			return head.getData();
		}
		public int[] pop()
		{
			int[] output = head.getData();
			head = head.getNext();
			length--;
			return output;
		}
		public void push(int[] i)
		{
			head = new KNode(i,head);
			length++;
		}
		public boolean hasNext()
		{
			return head != null;
		}
		public int getLength()
		{
			return length;
		}
		public String toString()
		{
			String output = "";
			for(KNode tmp = head; tmp != null; tmp=tmp.getNext())
			{
				output += tmp.getData() + " ";
			}
			return output;
		}
		/*public int[] toArray()
		{
			int[] output = new int[length];
			int i = length-1;
			for(KNode tmp = head; tmp != null; tmp = tmp.getNext())
			{
				output[i] = tmp.getData();
				i--;
			}
			return output;
		}*/

	}
	public class KNode
	{
		private KNode next = null;
		private int[] data;
		public KNode(int[] d, KNode n)
		{
			data = d;
			next = n;
		}
		public int[] getData()
		{
			return data;
		}
		public KNode getNext()
		{
			return next;
		}
	}
}