import java.util.Scanner;
import java.io.*;
import java.awt.*;
import javax.swing.*;
public class kenkensolver
{
	public static boolean done = false;
	public static void main(String args[]) throws IOException
	{
		String puzzlefile = "";
		System.out.println("Enter file:");
		Scanner scanner = new Scanner(new InputStreamReader(System.in));
		while(puzzlefile.equals(""))
		{
			String input = scanner.nextLine();
			File f = new File(input);
			if(f.exists() && !f.isDirectory())
			{
				puzzlefile = input;
			}
			else
			{
				System.out.println("Could not find file, please try again:");
			}
		}
		Solver s = new Solver("3x3_1.txt");
		//s.printPuzzle();
		KStack stack = new KStack();
		//int[][] implied = s.implyByRows();
		solve(s,stack);
		//System.out.println();
		//s.printPuzzle();
		JFrame frame = new JFrame();
		KenKenComponent kc = new KenKenComponent(puzzlefile, frame);
		kc.setNumber(s.puzzle);
	}
	public static void solve(Solver s, KStack k)
	{
		//System.out.println("Attempting to solve:");
		//s.printArray(s.puzzle);
		//System.out.println("Stack is:");
		//s.printArray(k.toArray());
		if(s.isSolved())
		{
			System.out.println("Done!");
			done = true;
			return;
		}
		else 
		{
			int[][] rows = s.implyByRows();
			if(rows.length > 0)
			{
				//System.out.println("Implying by rows because imply returned ");
				//s.printArray(rows);
				for(int[] i : rows)
				{
					k.push(i);
				}
				solve(s,k);
				return;
			}
			else
			{
				int[][] cols = s.implyByCols();
				if(cols.length > 0)
				{
					for(int[] i : cols)
					{
						k.push(i);
					}
					solve(s,k);
					return;
				}
				else
				{
					int[][] cage = s.implyByCages();
					if(cage.length > 0)
					{
						for(int[] i : cage)
						{
							k.push(i);
						}
						solve(s,k);
						return;
					}
					else
					{//We have implyed by rows, cols, and cages, now we just have to guess.
						//Fist, find the first(from top left) spot in the puzzle that's still 0
						int lastx = -1;
						int lasty = -1;
						search:
						for(int x = 0; x < s.size; x++)
						{
							for(int y = 0; y < s.size;y++)
							{
								if(s.puzzle[x][y] == 0)
								{
									lastx = x;
									lasty = y;
									//System.out.println("Attempting to guess number for (" + x + "," + y + ")");
									break search;
								}
							}
						}
						if(lastx != -1 && lasty != -1)
						{
							int[] guess = new int[4];
							boolean[] possibilities = s.getPossibilities(lastx,lasty);
							for(int i = 0; i < possibilities.length && !done; i++)
							{
								//System.out.println("Unable to imply a solution for (" + lastx + "," + lasty + ") guessing:");
								//s.printArray(possibilities);
								if(possibilities[i])
								{
									if(i == possibilities.length-1)
									{
										guess[0] = 0;
									}
									else
									{
										guess[0] = 1;
									}	
									guess[1] = lastx;
									guess[2] = lasty;
									guess[3] = i+1;
									k.push(guess);
									s.put(lastx,lasty,i+1);
									solve(s,k);
								}
							}
						}
						else
						{
							//We have exhusted all possibilities for this square
							//System.out.println("\nExhausted possibilities.. backtracking\n");
							while(k.getLength() > 0 && k.peek()[0] == 0 && !done) //While implied stuff is still on top
							{
								int[] thisitem = k.pop();
								//System.out.println("Removeing:");
								//s.printArray(thisitem);
								s.remove(thisitem[1],thisitem[2]);
							}
							//And pop the last guess
							int[] lastguess = k.pop();
							//System.out.println("Removeing:");
							//s.printArray(lastguess);
							s.remove(lastguess[1],lastguess[2]);
							//System.out.println("Done backtracking");
							return;
						}
					}
				}
			}
		}
		//System.out.println("Something has gone horribly wrong!");
	}
}