import java.util.Scanner;
import java.io.*;

public class Solver
{
	public int[][] puzzle;
	public Constraint[] constraints;
	public int size;
	public Solver(String filename)
	{
		parsePuzzle(filename);
		/*puzzle = new int[3][3];
		constraints = new Constraint[5];

		Position[] p1 = new Position[1];
		p1[0] = new Position(0,0);
		constraints[0] = new Constraint(3," ",p1);

		Position[] p2 = new Position[2];
		p2[0] = new Position(1,0);
		p2[1] = new Position(1,1);
		constraints[1] = new Constraint(6,"*",p2);

		Position[] p3 = new Position[2];
		p3[0] = new Position(2,0);
		p3[1] = new Position(2,1);
		constraints[2] = new Constraint(2,"/",p3);

		Position[] p4 = new Position[2];
		p4[0] = new Position(0,1);
		p4[1] = new Position(0,2);
		constraints[3] = new Constraint(2,"/",p4);

		Position[] p5 = new Position[2];
		p5[0] = new Position(1,2);
		p5[1] = new Position(2,2);
		constraints[4] = new Constraint(2,"-",p5);

		size = puzzle.length;
		*/
		System.out.println("Everything parsed, data is:");
		System.out.println("Puzzle:");
		printArray(puzzle);
		System.out.println("Constraints:");
		printArray(constraints);
		System.out.println("size: " + size);
	}
	private void parsePuzzle(String filename)
	{
		Scanner s = null;
		try
		{
			s = new Scanner(new FileInputStream(filename));
		}
		catch (Exception e)
		{
			System.out.println("Something went terribly wrong!\n" + e);
		}
		size = Integer.parseInt(s.nextLine().replaceAll("\n",""));

		puzzle = new int[size][size];

		constraints = new Constraint[Integer.parseInt(s.nextLine().replaceAll("\n",""))];

		//System.out.println("Puzzle size: " + size + " Cages: " + p.length);
		for(int i = 0; s.hasNextLine();i++)
		{
			String t1 = s.nextLine();
			System.out.println("Praseing: " + t1);
			String[] t2 = t1.split(",");
			System.out.println("Parts length: " + t2.length);
			if(t2.length > 1)
			{
				Position[] allcells = new Position[Integer.parseInt(t2[2])];
				for(int j = 0; j < Integer.parseInt(t2[2]);j++)
				{
					String[] coords = s.nextLine().split(",");
					allcells[j] = new Position(Integer.parseInt(coords[1]),Integer.parseInt(coords[0]));
				}
				constraints[i] = new Constraint(Integer.parseInt(t2[0]),t2[1],allcells);
				System.out.println("Created new constraint(" + Integer.parseInt(t2[0]) + "," + t2[1] + ",");
				printArray(allcells);
				/*
				for(Position c : allcells)
				{
					constraints[i] = new Constraint(Integer.parseInt(t2[0]),t2[1],allcells);
				}
				*/
				//p[i] = new KCage(Integer.parseInt(t2[0]),getOp(t2[1]),allcells);
				//System.out.println("Created " + p[i]);
			}
		}
	}
	public void put(int x, int y, int num)
	{
		puzzle[x][y] = num;
	}
	public int remove(int x, int y)
	{
		int num = puzzle[x][y];
		puzzle[x][y] = 0;
		return num;
	}
	public boolean[] getPossibilities(int x, int y)
	{
		boolean[] row = getPossibilitiesByRow(y);
		boolean[] col = getPossibilitiesByCol(x);
		boolean[] cage = getPossibilitiesByCage(x,y);
		boolean[] output = new boolean[size];
		System.out.println("By row:");
		printArray(row);
		System.out.println("By col:");
		printArray(col);
		System.out.println("By cage:");
		printArray(cage);
		for(int i = 0; i < size; i++)
		{
			if(row[i] && col[i] && cage[i])
			{
				output[i] = true;
			}
		}
		System.out.println("Possibilities for (" + x + "," + y + ") are ");
		printArray(output);
		return output;
	}
	public boolean[] getPossibilitiesByRow(int row)
	{
		boolean[] possibs = new boolean[size];
		for(int j = 0; j < size; j++)
		{//Set all places is possibs to true
			possibs[j] = true;
		}
		//Find all the possibilities
		for(int j = 0; j < size; j++)
		{ //For every other place
			if(puzzle[j][row] != 0)
			{
				//System.out.println("Setting (" + j + "," + row + "): " + puzzle[j][row] + " to false");
				possibs[puzzle[j][row]-1] = false;
			}
		}
		return possibs;
	}
	public boolean[] getPossibilitiesByCol(int col)
	{
		boolean[] possibs = new boolean[size];
		for(int j = 0; j < size; j++)
		{//Set all places is possibs to true
			possibs[j] = true;
		}
		//Find all the possibilities
		for(int j = 0; j < size; j++)
		{ //For every other place
			if(puzzle[col][j] != 0)
			{
				//System.out.println("Setting (" + col + "," + j + "): " + puzzle[col][j] + " to false");
				possibs[puzzle[col][j]-1] = false;
			}
		}
		return possibs;
	}
	public boolean[] getPossibilitiesByCage(int x, int y)
	{
		//System.out.println("Finding cage possibilities on (" + x + "," + y + ")");
		for(Constraint c : constraints)
		{
			//System.out.println("Testing a constraint: " + c.op);
			for(Position p : c.positions)
			{
				//System.out.println("Found a position in this constraint: (" + p.x + "," + p.y + ")");
				if(p.x == x && p.y == y)
				{
					System.out.println("Found cell being talked about.");
					//We found the cage that's being talked about
					if(c.op.equals("+"))
					{
						System.out.println("Found op: +");
						return getPossibilitiesByCageAdd(c);
					}
					else if(c.op.equals("-"))
					{
						System.out.println("Found op: -");
						return getPossibilitiesByCageSub(c);
					}
					else if(c.op.equals("*"))
					{
						System.out.println("Found op: *");
						return getPossibilitiesByCageMul(c);
					}
					else if(c.op.equals("/"))
					{
						System.out.println("Found op: /");
						return getPossibilitiesByCageDiv(c);
					}
					else if(c.op.equals(" "))
					{
						System.out.println("Found op: (NONE)");
						boolean[] output = new boolean[size];
						output[c.targNumber-1] = true;
						//System.out.println("Returning:");
						//printArray(output);
						return output;
					}
					else
					{
						System.out.println("Bad operator: (" + c.op + ")");
						return null;
					}
				}
			}
		}
		System.out.println("Something has gone wrong in getPossibilitiesByCage");
		return null;
	}
	private boolean[] getPossibilitiesByCageAdd(Constraint c)
	{
		System.out.println("Getting possibilities for add cage");
		//Try the numbers 1 to size for every square
		boolean[] output = new boolean[size];
		int targ = c.targNumber;
		//If any of the numbers are already in, subtract them from targ
		for(Position p : c.positions)
		{
			targ -= puzzle[p.x][p.y];
		}
		//possibilities are targnumber - 1*# of positions to fill
		int numcells = c.positions.length;
		int max = targ - numcells;
		int min = 1;
		for(int i = min; i < max; i++)
		{
			output[i-1] = true;
		}
		return output;
	}
	private boolean[] getPossibilitiesByCageMul(Constraint c)
	{
		//Numbers can be from 1 to size for this one
		//If the target number is odd, only an odd* an odd will work
		int targ = c.targNumber;
		System.out.println("Getting mul cage possibs:");
		System.out.println("Cage: (" + c.targNumber + "," + c.op);
		printArray(c.positions);
		//If any of the numbers are already in, divide the target by that.
		for(Position p : c.positions)
		{
			if(puzzle[p.x][p.y] != 0)
			{
				System.out.println("Found a number, useing division shortcut");
				targ /= puzzle[p.x][p.y];
			}
		}
		boolean[] output = new boolean[size];
		if(c.targNumber % 2 == 1)
		{
			System.out.println("Found an odd number, useing odd numbers shortcut");
			for(int i = 1; i < size+1; i+= 2)
			{
				System.out.println("Setting " + i + " to true");
				output[i-1] = true;
			}
			System.out.println("Returning ");
			printArray(output);
			return output;
		}
		for(int i = 1; i < size+1; i++)
		{
			output[i-1] = true;
		}
		return output;
	}
	private boolean[] getPossibilitiesByCageSub(Constraint c)
	{
		//If one of the items is already in it, find what the other value must be
		boolean[] output = new boolean[size];
		int x1 = c.positions[0].x;
		int y1 = c.positions[0].y;
		int x2 = c.positions[1].x;
		int y2 = c.positions[1].y;
		if(puzzle[x1][y1] != 0)
		{
			int onlypossib = 0;
			if(c.targNumber > puzzle[x1][y1])
			{
				onlypossib = c.targNumber-puzzle[x1][y1];
			}
			else if(c.targNumber < puzzle[x1][y1])
			{
				onlypossib = puzzle[x1][y1] - c.targNumber;
			}
			output[onlypossib-1] = true;
			return output;
		}
		if(puzzle[x2][y2] != 0)
		{
			int onlypossib = 0;
			if(c.targNumber>puzzle[x2][y2])
			{
				onlypossib = c.targNumber-puzzle[x2][y2];
			}
			else if(c.targNumber < puzzle[x2][y2])
			{
				onlypossib = puzzle[x2][y2] - c.targNumber;
			}
			output[onlypossib-1] = true;
			return output;
		}
		//Otherwise, values can be from 1 to targnumber - 2
		for(int i = 1; i < c.targNumber-2; i++)
		{
			output[i-1] = true;
		}
		return output;
	}
	private boolean[] getPossibilitiesByCageDiv(Constraint c)
	{
		//If one of the items is already in it, find what the other value must be
		boolean[] output = new boolean[size];
		int x1 = c.positions[0].x;
		int y1 = c.positions[0].y;
		int x2 = c.positions[1].x;
		int y2 = c.positions[1].y;
		if(puzzle[x1][y1] != 0)
		{
			int onlypossib = c.targNumber/puzzle[x1][y1];
			output[onlypossib-1] = true;
			return output;
		}
		if(puzzle[x2][y2] != 0)
		{
			int onlypossib = c.targNumber/puzzle[x2][y2];
			output[onlypossib-1] = true;
			return output;
		}
		//Otherwise, values can be from 1 to targnumber
		for(int i = 1; i < c.targNumber+1; i++)
		{
			output[i-1] = true;
		}
		return output;
	}
	public boolean isSolved()
	{
		boolean tr = testRows();
		boolean tc = testCols();
		boolean ta = testCages();
		System.out.println("Checking for solution(Rows: " + tr + ")(Cols: " + tc + ")(Cages: " + ta+"):");
		printArray(puzzle);
		if(!testRows() || !testCols() || !testCages())
		{
			return false;
		}
		return true;
	}
	private boolean testCages()
	{
		for(Constraint c : constraints)
		{
			if(!testConstraint(c))
			{
				return false;
			}
		}
		return true;
	}
	private boolean testConstraint(Constraint c)
	{
		if(c.op.equals("+"))
		{
			int sum = 0;
			for(Position p : c.positions)
			{
				if(puzzle[p.x][p.y] != 0)
				{
					sum += puzzle[p.x][p.y];
				}
				else
				{
					return false;
				}
			}
			if(sum == c.targNumber)
			{
				return true;
			}
			else
			{
				System.out.println("Failed on constraint:("+c.targNumber+","+c.op+",");
				printArray(c.positions);
				return false;
			}
		}
		else if(c.op.equals("-"))
		{
			Position p1 = c.positions[0];
			Position p2 = c.positions[1];
			if(puzzle[p1.x][p1.y] != 0 && puzzle[p2.x][p2.y] != 0)
			{
				int num1 = puzzle[p1.x][p1.y];
				int num2 = puzzle[p2.x][p2.y];
				if(num1 - num2 == c.targNumber)
				{
					return true;
				}
				if(num2 - num1 == c.targNumber)
				{
					return true;
				}
			}
			else
			{
				System.out.println("Failed on constraint:("+c.targNumber+","+c.op+",");
				printArray(c.positions);
				return false;
			}
			return false;
		}
		else if(c.op.equals("*"))
		{
			int product = 1;
			for(Position p : c.positions)
			{
				if(puzzle[p.x][p.y] != 0)
				{
					product *= puzzle[p.x][p.y];
				}
				else
				{
					return false;
				}
			}
			if(product == c.targNumber)
			{
				return true;
			}
			else
			{
				System.out.println("Failed on constraint:("+c.targNumber+","+c.op+",");
				printArray(c.positions);
				System.out.println("Product is " + product);
				return false;
			}
		}
		else if(c.op.equals("/"))
		{
			Position p1 = c.positions[0];
			Position p2 = c.positions[1];
			if(puzzle[p1.x][p1.y] != 0 && puzzle[p2.x][p2.y] != 0)
			{
				double num1 = puzzle[p1.x][p1.y];
				double num2 = puzzle[p2.x][p2.y];
				if(num1 / num2 == c.targNumber)
				{
					return true;
				}
				if(num2 / num1 == c.targNumber)
				{
					return true;
				}
			}
			else
			{
				System.out.println("Failed on constraint:("+c.targNumber+","+c.op+",");
				printArray(c.positions);
				return false;
			}
			return false;
		}
		else if(c.op.equals(" "))
		{
			int x = c.positions[0].x;
			int y = c.positions[0].y;
			if(puzzle[x][y] == c.targNumber)
			{
				return true;
			}
			else
			{
				return false;
			}
		}
		System.out.println("Something went wrong in testConstraint");
		return false;
	}
	private boolean testCols()
	{
		for(int i = 0; i < size; i++)
		{
			boolean[] uniqueCols = new boolean[size];
			for(int j = 0; j < size; j++)
			{
				if(puzzle[i][j] == 0)
				{
					return false;
				}
				uniqueCols[puzzle[i][j]-1] = true;
			}
			for(int j = 0; j < uniqueCols.length; j++)
			{
				if(!uniqueCols[j])
				{
					return false;
				}
			}
		}
		//System.out.println("Something went wrong in testCols!");
		return true;
	}
	private boolean testRows()
	{
		for(int i = 0; i < size; i++)
		{
			boolean[] uniqueRows = new boolean[size];
			for(int j = 0; j < size; j++)
			{
				if(puzzle[j][i] == 0)
				{
					return false;
				}
				uniqueRows[puzzle[j][i]-1] = true;
			}
			for(int j = 0; j < uniqueRows.length; j++)
			{
				if(!uniqueRows[j])
				{
					return false;
				}
			}
		}
		//System.out.println("Something went wrong in testRows");
		return true;
	}
	public int[][] implyByRows()
	{
		//System.out.println("Implying by rows...");
		int[][][] output = new int[size][4][size];
		int numImplyed = 0;
		for(int i = 0; i < size; i++)
		{
			//System.out.println("Calling imply row helper on row " + i);
			output[i] = implyByRowsHelper(i);
			if(output[i].length > 0)
			{
				numImplyed++;
			}
		}
		int[][] realoutput = new int[numImplyed][4];
		int j = 0;
		for(int i = 0; i < numImplyed;i++)
		{
			if(output[i].length > 0)
			{
				realoutput[j] = output[i][0];
				j++;
			}
		}
		return realoutput;
	}
	public int[][] implyByCols()
	{
		//System.out.println("Implying by cols...");
		int[][][] output = new int[size][4][size];
		int numImplyed = 0;
		for(int i = 0; i < size; i++)
		{
			//System.out.println("Calling imply col helper on col " + i);
			output[i] = implyByColsHelper(i);
			if(output[i].length > 0)
			{
				numImplyed++;
			}
		}
		int[][] realoutput = new int[numImplyed][4];
		int j = 0;
		for(int i = 0; i < numImplyed;i++)
		{
			if(output[i].length > 0)
			{
				realoutput[j] = output[i][0];
				j++;
			}
		}
		return realoutput;
	}
	public int[][] implyByCages()
	{
		//System.out.println("Implying by cages");
		int[][][][] output = new int[size][size][4][size];
		int numImplyed = 0;
		//We should only be implying ONE number max!
		for(int x = 0; x < size; x++)
		{
			for(int y = 0; y < size; y++)
			{
				//Scan for a num that has only 1 possibility
				output[x][y] = implyByCagesHelper(x,y);
				//System.out.println("Attempted to imply by cages on (" + x + "," + y + "):");
				//printArray(output[x][y]);
				if(output[x][y].length == 1)
				{
					//numImplyed++;
					//System.out.println("Implything by cage. returning:");
					//printArray(output[x][y]);
					return output[x][y];
				}
				else
				{
					//System.out.println("Unable to imply");
				}
			}
		}
		//System.out.println("Unable to imply ANYTHING");
		int[][] realoutput = new int[0][0];
		return realoutput;
		/*
		int[][] realoutput = new int[1][4];
		int track = 0;
		if(output.length == 1)
		{
			realoutput[0] = output[x][y][0];
			return realoutput;
		}
		*/
	}
	public int[][] implyByCagesHelper(int x, int y)
	{
		int[][] realoutput = new int[size][4];
		//System.out.println("Implying on cage(" + x + "," + y + ")");
		int[][] output = new int[size][4];
		if(puzzle[x][y] != 0)
		{
			//This square already has a number in it.
		}
		else
		{
			boolean[] possibs = getPossibilitiesByCage(x,y);
			//System.out.println("Got possibilities:");
			//printArray(possibs);
			int j = 0;
			int numtrue = 0;
			for(boolean b : possibs)
			{
				if(b)
				{
					numtrue++;
				}
			}
			if(numtrue == 1)
			{
				for(int i = 0; i < possibs.length;i++)
				{
					if(possibs[i])
					{
						realoutput = new int[1][4];
						puzzle[x][y] = i+1;
						realoutput[j][0] = 0;
						realoutput[j][1] = x;
						realoutput[j][2] = y;
						realoutput[j][3] = i;
						return realoutput;
					}
				}
			}
		}
		return realoutput;
	}
	private int[][] implyByRowsHelper(int row)
	{
		//System.out.println("Implying on row " + row);
		//boolean[] places = new boolean[size];
		//Outputs all numbers that should go on the stack, each number is in the form (0,x,y,num)
		//this method may output more than 1 implyed number.
		int[][] output = new int[size][4];
		int numImplyed = 0;
		for(int i = 0; i < size; i++)
		{ //For each square
			//This place already has something
			if(puzzle[i][row] != 0)
			{
				//System.out.println("(" + i + "," + row + ") already has " + puzzle[i][row]);
			}
			else
			{
				boolean[] possibs = getPossibilitiesByRow(row);
				//System.out.println("Possibilities for (" + i + "," + row + ") are:");
				printArray(possibs);
				//Find out how many possibilites for this place is true
				int numtrue = 0;
				int lasttrue = 0;
				for(int j = 0; j < size;j++)
				{
					if(possibs[j])
					{
						numtrue++;
						lasttrue = j+1;
					}
				}
				if(numtrue == 1)
				{
					puzzle[i][row] = lasttrue;
					output[numImplyed][0] = 0;
					output[numImplyed][1] = i;
					output[numImplyed][2] = row;
					output[numImplyed][3] = lasttrue;
					numImplyed++;
				}
			}
		}
		//System.out.println("First output is : ");
		//printArray(output);
		int[][] realoutput = new int[numImplyed][4];
		for(int i = 0; i < numImplyed; i++)
		{
			realoutput[i] = output[i];
		}
		//System.out.println("Real output is : ");
		//printArray(realoutput);
		return realoutput;
	}
	private int[][] implyByColsHelper(int col)
	{
		//		System.out.println("Implying on row " + row);
		//boolean[] places = new boolean[size];
		//Outputs all numbers that should go on the stack, each number is in the form (0,x,y,num)
		//this method may output more than 1 implyed number.
		int[][] output = new int[size][4];
		int numImplyed = 0;
		for(int i = 0; i < size; i++)
		{ //For each square
			//This place already has something
			if(puzzle[col][i] != 0)
			{
				//System.out.println("(" + i + "," + row + ") already has " + puzzle[i][row]);
			}
			else
			{
				boolean[] possibs = getPossibilitiesByCol(col);
				//System.out.println("Possibilities for (" + col + "," + i + ") are:");
				//printArray(possibs);
				//Find out how many possibilites for this place is true
				int numtrue = 0;
				int lasttrue = 0;
				for(int j = 0; j < size;j++)
				{
					if(possibs[j])
					{
						numtrue++;
						lasttrue = j+1;
					}
				}
				if(numtrue == 1)
				{
					puzzle[col][i] = lasttrue;
					output[numImplyed][0] = 0;
					output[numImplyed][1] = col;
					output[numImplyed][2] = i;
					output[numImplyed][3] = lasttrue;
					numImplyed++;
				}
			}
		}
		//System.out.println("First output is : ");
		//printArray(output);
		int[][] realoutput = new int[numImplyed][4];
		for(int i = 0; i < numImplyed; i++)
		{
			realoutput[i] = output[i];
		}
		//System.out.println("Real output is : ");
		//printArray(realoutput);
		return realoutput;
	}
	public void printPuzzle()
	{
		for(int y = 0; y < puzzle.length; y++)
		{
			for(int x = 0; x < puzzle[y].length; x++)
			{
				System.out.print(puzzle[x][y] + " ");
			}
			System.out.print("\n");
		}
	}
	public void printArray(int[] arr)
	{
		if(arr.length == 0)
		{
			System.out.println("[]");
			return;
		}
		System.out.print("[" + arr[0]);
		for(int i = 1; i < arr.length; i++)
		{
			System.out.print("," + arr[i]);
		}
		System.out.print("]\n");
	}
	public void printArray(int[][] arr)
	{
		if(arr.length == 0)
		{
			System.out.println("[[]]");
			return;
		}
		System.out.print("[\t");
		printArray(arr[0]);
		for(int i = 1; i < arr.length; i++)
		{
			System.out.print("\t");
			printArray(arr[i]);
		}
		System.out.print("]\n");

	}
	public void printArray(boolean[] arr)
	{
		if(arr.length == 0)
		{
			System.out.println("[]");
			return;
		}
		System.out.print("[" + arr[0]);
		for(int i = 1; i < arr.length; i++)
		{
			System.out.print("," + arr[i]);
		}
		System.out.print("]\n");
	}
	public void printArray(Position[] arr)
	{
		if(arr.length == 0)
		{
			System.out.println("[]");
			return;
		}
		System.out.print("[(" + arr[0].x + "," + arr[0].y + ")");
		for(int i = 1; i < arr.length; i++)
		{
			System.out.print(",(" + arr[i].x + "," + arr[i].y + ")");
		}
		System.out.print("]\n");
	}
	public void printArray(Constraint[] arr)
	{
		if(arr.length == 0)
		{
			System.out.println("[[]]");
			return;
		}
		System.out.print("[\t");
		printArray(arr[0]);
		for(int i = 1; i < arr.length; i++)
		{
			System.out.print("\t");
			printArray(arr[i]);
		}
		System.out.print("]\n");
	}
	public void printArray(Constraint c)
	{
		System.out.print("(" + c.op + "," + c.targNumber + ",");
		printArray(c.positions);
	}
}