//Written By Timothy VanAusdal in an attempt to see if concepts from linear algebra could be used to solve Sudoku

package Sudoku;

import java.awt.Point;
import java.io.File;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * 
 * @author Timothy VanAusdal
 * 
 * This project was written in an attempt to see if concepts from linear algebra 
 * could be applied in order to solve a sudoku puzzle (either 9x9 or 4x4). This 
 * project will allow the user to input a puzzle with either the correct value
 * at a certain position or a 0 to represent it being missing assuming that
 * the puzzle in inputted on one line.
 * 
 * This puzzle
 * 
 * 	1040
 *	0003
 *	0004
 *	0200
 *
 *would be inputted as 1 0 4 0 0 0 0 3 0 0 0 4 0 2 0 0
 *
 * From every sudoku puzzle you can gain a lot of information from analyzing the relationships
 * and our goal was to use that information to solve them. For example, knowing that in a 
 * typical 9x9 sudoku puzzle there will be 9 entries with one 1, one 2, and so on means that
 * every box, column, and/ or row will add up to 45. We took in an inputted sudoku puzzle,
 * charted these relationships in a matrix with size dimension*dimension (if 9x9 81, if 4x4 16) by
 * dimension*3 (if9x9 27, if 4x4 12) and then reduced that matrix and printed the relationships.
 * 
 * I attempted to actually solve the puzzle using these simplified relationships and the inherent
 * relationships and constraints from the puzzle itself (for example, if r1c1+r4c4=10 and we can learn that 
 * the only valid combination is where r1c1 = 9 and r4c4 = 1 or something we can solve this) but came to 
 * the conclusion that it wouldn't be viable and this is unfinished and unnused. 
 *
 *We found that the relationships produced were valid and that they could be used in aiding or guiding an
 *attempt at solving sudoku.
 */
public class SudokuMain {

	private static int col, row;
	
	//the sudoku puzzle in it's base form with either 0's or the value
	private static int[][] puzzle;
	private static int[][] puzzleSolver;
	
	private static int[] solved;
	
	private static int dimension;
	//a matrix meant to represent all relationship equations
	/**
	 * col, row
	 */
	private static int[][] matrix;
	
	private static int[][] redMatrix;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		
		System.out.println("input the desired size (if 2x2 for each box put 4 if 3x3 input 9");
		Scanner Length = new Scanner(System.in);
		
		dimension = Length.nextInt();
		
		col = dimension;
		row = dimension;
		
		solved = new int[dimension*dimension];
		System.out.println(dimension);
		puzzle = new int[col][row];
		
		System.out.println("input the sudoku puzzle");
		String input = "";
		
		
		Scanner S = new Scanner(System.in);
	
		
		
		
		for(int row = 0; row < dimension; row++)
		{
			for(int col = 0; col < dimension; col ++)
			{
				
				puzzle[col][row] = S.nextInt();
				
			}
			for(int col = 0; col < dimension; col++){
				input += puzzle[col][row];
				
			}
			System.out.println(input);
			input = "";
		}
		
		System.out.println("");
		System.out.println("");
		makeMatrix();
		
		printMatrix();
		
		System.out.println("");
		System.out.println("");
		printMapleMatrix();
		System.out.println("");
		System.out.println("");
		reduceMatrix();
		
		printRedMatrix();
		
		printRelationships();
		String current = relationships.get(0);
		ArrayList<Point> point = parseRelat(0);
		System.out.println("");
	}
	
	public static void makeMatrix()
	{
		
		
		matrix = new int[dimension*dimension+1][dimension*3];
		
		rowRelations();
		colRelations();
		boxRelations();
		
		
	}
	
	public static void rowRelations()
	{
		int total = 0;
		for(int row = 0; row < dimension; row++)
		{
			for(int col = 0; col < dimension; col++)
			{
				if(puzzle[col][row]!=0)
				{
					total+= puzzle[col][row];
					
				}
				else{
					matrix[matrixLoc(col,row)][row] = 1;
				}
			}
			matrix[dimension*dimension][row]=totalSum(dimension)-total;
			total = 0;
		}
	}
	
	public static void colRelations()
	{
		int total = 0;
		
		
		
		for(int col = 0; col < dimension; col++)
		{
			
			for(int row = 0; row < dimension; row++)
			{
				if(puzzle[col][row]!=0)
				{
					total+= puzzle[col][row];
					
				}
				
				else{
					matrix[matrixLoc(col,row)][col+dimension] = 1;
				}
			}
			matrix[dimension*dimension][col+dimension]=totalSum(dimension)-total;
			total = 0;
		}
	}
	
	public static void boxRelations()
	{
		int total = 0;
		int reps = (int) Math.sqrt(dimension);
		
		int currentRow = dimension*2;
		for(int curBoxRow = 0; curBoxRow < dimension; curBoxRow+=reps)
		{
			for(int curBoxCol = 0; curBoxCol < dimension; curBoxCol+=reps)
			{
				for(int row = 0; row < reps; row++){
					
					for(int col = 0; col < reps; col++){
						if(puzzle[col+curBoxCol][row+curBoxRow]!=0)
						{
							total+=puzzle[col+curBoxCol][row+curBoxRow];
							
						}
						else{
							matrix[matrixLoc(col+curBoxCol, row+curBoxRow)][currentRow]= 1;
						}
						
					}
					
					
					
				}
				currentRow++;
				
				int curLoc = curBoxRow+curBoxCol/reps+dimension*2;
				matrix[dimension*dimension][curLoc]=totalSum(dimension)-total;
				total = 0;
				
			}
		}
	}
	
	public static int matrixLoc(int col, int row)
	{
		
		int returnable = (row)*dimension+col;
		
		return returnable;
	}
	
	public static Point puzzlePoint(int matrixLoc)
	{
		Point returnable = new Point();
		returnable.x = matrixLoc%dimension;
		returnable.y = matrixLoc/dimension;
		return returnable;
	}
	
	public static String puzzleLoc(int matrixLoc)
	{
		Point loc = puzzlePoint(matrixLoc);
		
		String returnable = "r" + loc.y + "c" + loc.x;
		
		return returnable;
	}
	
	/**
	 * all of the items in a certain row, column, or box will add up to a certain number depending on the dimensions. this returns that number.
	 * @param current
	 * @return
	 */
	public static int totalSum(int current)
	{
		if(current == 1)
		{
			return 1;
		}
		else
		{
			return current+totalSum(current-1);
		}
	}
	
	
	/**
	 * prints the matrix in a visually pleasing format
	 */
	public static void printMatrix()
	{
		String current = "";
		
		
		for(int row = 0; row < dimension*3;row++)
		{
			for(int col = 0; col < dimension*dimension+1; col++)
			{
				int val = matrix[col][row];
				if(val>=0)
				{
					current+= "  " + matrix[col][row];
				}
				else
				{
					current+= " " + matrix[col][row];
				}
			}
			System.out.println(current);
			current = "";
		}
	}
	
	
	/**
	 * prints the reduced matrix in a visually pleasing format
	 */
	public static void printRedMatrix()
	{
		System.out.println("");
		System.out.println("");
		redMatrix = matrix;
		String current = "  ";
		String concise = "";
		
		for(int row = 1; row < dimension*dimension+1;row++)
		{
			int first = row/dimension+1;
			int second = row%dimension;
			if(second == 0){
				first--;
				second = dimension;
			}
			current += "r"+ first+ "c" + second + " ";
		}
		
		current += " ans";
		System.out.println(current);
		current = "";
		
		for(int row = 0; row < dimension*3;row++)
		{
			for(int col = 0; col < dimension*dimension+1; col++)
			{
				int val = redMatrix[col][row];
				if(val>=0)
				{
					current+= "    " + redMatrix[col][row];
					
				}
				else
				{
					current+= "   " + redMatrix[col][row];
				}
				
			}
			System.out.println(current);
			current = "";
		}
		System.out.println("");
		for(int row = 0; row < dimension*3;row++)
		{
			for(int col = 0; col < dimension*dimension+1; col++)
			{
				concise = concise + " "+ redMatrix[col][row];
				
			}
			System.out.println(concise);
			concise = "";
		}
		
		System.out.println("");
		System.out.println("");
		
	}
	/**
	 * prints a maple command to represent the matrix.
	 */
	public static void printMapleMatrix()
	{
		int size = dimension*dimension+2;
		System.out.println("interface(rtablesize="+size+");");
		String pLine = "Q:=<";
		for(int row = 0; row < dimension*3-1; row++)
		{
			pLine = pLine+ "<";
			for(int col = 0; col < dimension*dimension; col++)
			{
				pLine = pLine + matrix[col][row] + ", ";
			}
			pLine = pLine + matrix[dimension*dimension][row] + ">|";
		}
		
		int row = dimension*3-1;
		pLine = pLine+ "<";
		for(int col = 0; col < dimension*dimension; col++)
		{
			pLine = pLine + matrix[col][row] + ", ";
		}
		pLine = pLine + matrix[dimension*dimension][row] + ">>;";
		
		
		
		System.out.println(pLine);
		System.out.println("ReducedRowEchelonForm(Q);");
	}
	
	public static void reduceMatrix()
	{
		redMatrix = matrix;
		
		//try to reduce for every column
		for(int col = 0; col < dimension*dimension; col++)
		{
			
			
			for(int row = 0; row < dimension*3; row++)
			{
				if(redMatrix[col][row]!=0)
				{
					boolean hasPrev = false; 
					int start = 0;
					
					//see if any columns before this have a value
					while(start < col &&!hasPrev)
					{
						hasPrev = redMatrix[start][row]!=0;
						start++;
					}
					
					//if there are no previous and this is the first occurrence of the value
					if(!hasPrev)
					{
						for(int curRow = 0; curRow<dimension*3; curRow++){
							//reduce all occurrences.
							if((curRow!=row)&&(redMatrix[col][curRow]!=0))
							{
								if(redMatrix[col][curRow]<0)
								{
									for(int c = 0; c < dimension*dimension+1; c++)
									{
										redMatrix[c][curRow]= redMatrix[c][curRow]*-1;
									}
								}
								int oMultiplier = redMatrix[col][curRow];
								int curMultiplier = redMatrix[col][row];
								for(int curCol= 0; curCol < dimension*dimension+1; curCol++){
									
									int current = redMatrix[curCol][curRow]*curMultiplier;
									int subtractor = redMatrix[curCol][row]*oMultiplier;
									redMatrix[curCol][curRow] = current-subtractor;
								}
							}
						}
						
					
					}
					
				}
			}
		}
		
	}
	
	
	public static void resetPuzzleSolver()
	{
		for(int row = 0; row < dimension; row++){
			for(int col = 0; col < dimension; col++){
				puzzleSolver[col][row]=puzzle[col][row];
			}
		}
	}
	
	public static void solvePuzzle()
	{
		resetPuzzleSolver();
		
	}
	
	static ArrayList<String> relationships = new ArrayList<String>();
	
	
	public static void printRelationships()
	{
		String printable = "";
		
		for(int row = 0; row < dimension*3; row++)
		{
			for(int col = 0; col < dimension*dimension; col++)
			{
				if(redMatrix[col][row]!=0)
				{
					int ro = (col/dimension)+1;
					int co = (col%dimension)+1;
					if(redMatrix[col][row]==1)
					{
						if(printable.length()==0){
							printable = " ";
						}
						printable = printable + "r" + ro +"c" + co +"+";
					}
					else if(redMatrix[col][row]==-1)
					{
						if(printable.length()==0){
							printable = "=";
						}
						printable = printable.substring(0,printable.length()-1) + "-r" + ro +"c" + co +"+";
					}
					else{
						printable = printable + redMatrix[col][row] + "*r" + ro +"c" + co +"+";
					}
					
				}
			}
			
			if(!(printable.equals("")))
			{
				if(redMatrix[dimension*dimension][row]<0){
					printable = printable.substring(0, printable.length()-1) + "=" + redMatrix[dimension*dimension][row] ;
				}
				else{
					printable = printable.substring(0, printable.length()-1) + "= " + redMatrix[dimension*dimension][row] ;
				}
				
				relationships.add(printable);
				printable = "";
			}
		}
		for(int pos = 0; pos < relationships.size(); pos++)
		{
			System.out.println(relationships.get(pos));
		}
	}
	
	/**
	 * This method will attempt to solve the puzzle using
	 * only the matrix of relationships and the puzzle itself.
	 */
	public static void solveMatrix()
	{
		puzzleSolver= puzzle;
		for(int row = 0; row < dimension*3; row++)
		{
			int target = redMatrix[dimension*dimension][row];
			int members = 0;
			for(int col = 0; col < dimension*dimension; col++)
			{
				
				
				
			}
			
			
			
		}
	}
	
	/**
	 * Checks to see if a value can be inserted into a certain position.
	 * @param val
	 * @param row
	 * @param col
	 * @return
	 */
	public static boolean isValidPuzzle(int val, int row, int col){
		
		if(!isValidCol(val, row, col))
		{
			return false;
		}
		if(!isValidRow(val, row, col))
		{
			return false;
		}
		return isValidBox(val, row, col);
	}
	
	/**
	 * Checks to see if a value can be inserted into a certain position.
	 * @param val
	 * @param row
	 * @param col
	 * @return
	 */
	public static boolean isValidCol(int val, int row, int col){
		
		for(int curCol = 0; curCol < dimension; curCol++)
		{
			if(puzzleSolver[curCol][row]==val)
			{
				return false;
			}
		}
		return true;
	}
	
	/**
	 * Checks to see if a value can be inserted into a certain position.
	 * @param val
	 * @param row
	 * @param col
	 * @return
	 */
	public static boolean isValidRow(int val, int row, int col){
		
		for(int curRow = 0; curRow < dimension; curRow++)
		{
			if(puzzleSolver[col][curRow]==val)
			{
				return false;
			}
		}
		return true;
	}
	
	/**
	 * Checks to see if a value can be inserted into a certain position.
	 * @param val
	 * @param row
	 * @param col
	 * @return
	 */
	public static boolean isValidBox(int val, int row, int col){
		int boxRow = (int)(row/Math.sqrt((double)dimension));
		int boxCol= (int)(col/Math.sqrt((double)dimension));
		
		boxRow = boxRow*(int)(Math.sqrt((double)dimension));
		boxCol = boxCol*(int)(Math.sqrt((double)dimension));
		for(int rowReps = 0; rowReps < 3; rowReps++)
		{
			for(int colReps = 0; colReps < 3; colReps++)
			{
				if(puzzleSolver[boxCol+colReps][boxRow+rowReps]==val)
				{
					return false;
				}
			}
		}
		
		return true;
	}
	
	//represents the number of valid combinations. 
	static int validCombos;
	public static void findValidCombos()
	{
		int entries = 0;
		
	}
	
	public static ArrayList<Point> parseRelat(int index)
	{
		ArrayList<Point> returnable = new ArrayList<Point>();
		
		String relations = relationships.get(index).substring(0, relationships.get(index).length()-3);
		if(relations.charAt(relations.length()-1)=='='){
			relations = relations.substring(0, relations.length()-1);
		}
		
		
		int curRelation = 0;
		
		for(int rep = 0; rep < relations.length(); rep+=5){
			
			String x = relations.charAt(rep+2)+"";
			if(relations.charAt(rep)=='-'){
				x = "-" + x;
			}
			String y = relations.charAt(rep+4)+"";
			Point addable = new Point(Integer.parseInt(x), Integer.parseInt(y));
			
			returnable.add(addable);
		
		}
		
		String answer = relationships.get(index).substring(relationships.get(index).length()-2);
		
		Point answerPoint = new Point();
		answerPoint.y = 0;
		if(!(answer.charAt(0)=='-')){
			answer = answer.substring(1);
		}
		answerPoint.x = Integer.parseInt(answer);
		
		returnable.add(answerPoint);
		return returnable;
	}
	
	static String workingCombo = "";
	
	public static boolean findValid(){
		
		for(int rep = 0; rep < relationships.size(); rep++){
			validRelations = 0; 
			workingCombo = "";
			ArrayList<Point> currentPoints = parseRelat(rep);
			boolean bool = hasValid(currentPoints);
			if(validRelations == 1&&!(workingCombo.equals(""))){
				for(int cur = 0; cur < currentPoints.size()-1; cur++)
				{
					Point point = currentPoints.get(cur);
					puzzle[point.x][point.y] = workingCombo.charAt(cur*2);
				}
			}
		}
		return false; 
	}
	
	static int validRelations = 0;
	public static boolean hasValid(ArrayList<Point> points){
		
		if(points.size()!=2){
			boolean hadValid = false;
			for(int curVal = 1; curVal <= dimension; curVal++){
				
				if(isValidPuzzle(Math.abs(points.get(0).x), Math.abs(points.get(0).y), curVal)){
					ArrayList<Point> testingPoint = points;
					testingPoint.remove(0);
					Point answer = testingPoint.get(testingPoint.size()-1);
					
					
					if(points.get(0).x<0){
						answer.x = answer.x +curVal;
					}
					else{
						answer.x = answer.x -curVal;
					}
					testingPoint.remove(testingPoint.size()-1);
					testingPoint.add(answer);
					
					hasValid(testingPoint);
				}
			}
			return false;
		}
		else{
			Point only = points.get(0);
			int answer = points.get(1).x;
			
			if(only.x<0){
				answer = -1*answer;
				only.x = -1*only.x;
			}
			else if(only.y<0){
				answer = -1*answer;
				only.y = -1*only.y;
			}
			
			if(isValidPuzzle(only.x, only.y, answer)){
				validCombos++;
				return true;
			}
			
			else{
				return false;
			}
			
		}
		
		
	}
}