//Eva Belmont
// The "SudokuLabShell5" class.
/*I added another couple methods that increase the number of answers it can 
get before guessing.  Also, I put a loop around the fillInAllDefinites method 
that allows it to get answers near the beginning  forced by numbers it gets
 near the end of the method.
*/
import java.awt.*;
import hsa.*;
import java.util.*;
import java.lang.*;


public class SudokuLabShellEva
{
    public static Random rand = new Random ();
    public static boolean debug = false;

    public static void main (String[] args)
    {
	System.out.println ("Do you want all debug data printed? (y or n)");
	String ans = Stdin.readString ();
	if (ans.equals ("y") || ans.equals ("Y"))
	    debug = true;

	int[] [] grid = getGrid (); // 9x9 array filled with single digit ints;
	// 0 represents a blank
	if (debug)
	    printGrid (grid);
	Set[] [] choice = createChoiceGrid (grid);  // all unknown numbers are
	//stored a a zero
	int numCorrect = fillInMoreForcedNums (grid, choice); // changes grid by adding
	//all definite #s
	// returns # of definites (max=81)
	boolean completed;
	if (numCorrect == 81)
	    completed = true;
	else
	    completed = false;

	//if (debug)
	//printGrid (grid);
	// all definite spots have been filled in.

	Set[] [] tempChoice = new Set [9] [9];  // creating an array where each
	// element is a set of possible ints that might work
	int[] [] tempGrid = new int [9] [9];
	boolean noError = true;
	if (numCorrect == 100)
	    noError = false;
	if (debug)
	    System.out.println ("Ready to start trial and error");
	long guessCounter = 0;
	long backToStartGuessCounter = 0;
	if (completed)
	{
	    printGrid (grid);
	    System.out.println ("No guesses needed");
	    return;
	}

	/*this is the big trial and error loop. Computer finds
	the spot with fewest possible ints (but
	not definite) which might work. It guesses, then fills in
	 all "definites" based on that guess. It repeats this
	process until the puzzle is correct or a deaend is reached.
	 If it's a deadend, the computer starts
	again at the "real definites" and begins to guess again.
	*/
	while (!completed)
	{
	    for (int row = 0 ; row < 9 ; row++)   // nested loop creates temp 2d arrays
		//for trial and error
		for (int col = 0 ; col < 9 ; col++)
		{
		    tempChoice [row] [col] = choice [row] [col];
		    tempGrid [row] [col] = grid [row] [col];
		}
	    backToStartGuessCounter++;
	    if (backToStartGuessCounter % 10000 == 0)
		System.out.print (backToStartGuessCounter + " ");
	    if (backToStartGuessCounter % 100000 == 0)
		System.out.println (guessCounter + "   ");
	    if (debug)
		System.out.println ("backToStartGuessCounter=" + backToStartGuessCounter);
	    noError = true; // will become true if there are no valid choices for a box

	    while (!completed) // goes thru 2D array repeatedly , making guesses if necessary
	    {
		noError = findChoiceSpotAndAssignRandomly (tempGrid, tempChoice);
		guessCounter++;
		if (debug)
		    System.out.println ("GuessCounter=" + guessCounter);
		tempChoice = createChoiceGrid (tempGrid);
		if (noError)
		{
		    tempChoice = createChoiceGrid (tempGrid);
		    int numRight = fillInMoreForcedNums (tempGrid, tempChoice);
		    if (numRight == 81)
			completed = true;
		    else if (numRight == 100) // method returns 100 to inicate an error
			noError = false;
		}
		if (!noError)
		    break;
	    }
	}
	printGrid (tempGrid);
	System.out.println ("Total guesses was " + guessCounter + "Back to start guesses ="
		+ backToStartGuessCounter);
    } // main method


    public static boolean findChoiceSpotAndAssignRandomly (int[] [] tempGrid, Set[] [] tempChoice)
	//pre: receives grid and choice grid
	//post: finds the with a choice with fewest possibilities, and chooses randomly -
	// returns true if that is done
	//and false if there are no valid choices
    {

	int guessedNum;
	int lowest = 10;
	int lowRow = 0; // row coordinate of the unknown spot in grid with fewest possibilities
	int lowCol = 0; // col coordinate of the unknown spot in grid with fewest possibilities
	int lowestValue = 9;
	for (int r = 0 ; r < 9 ; r++)
	    for (int c = 0 ; c < 9 ; c++)
	    {
		if (tempChoice [r] [c].size () < lowestValue && tempChoice [r] [c].size () > 1)
		{
		    lowestValue = tempChoice [r] [c].size ();
		    lowRow = r;
		    lowCol = c;
		} //if
		if (lowestValue == 0)
		    return false;
	    } //for

	//use your text to determine the size of a Set
	// your code here will set lowRow,lowCol to the coordintates of the choice grid
	// which have the fewest possibilities from the unknown spots in the grid


	guessedNum = randomChoice (tempChoice [lowRow] [lowCol]);
	resetTempChoice (tempChoice [lowRow] [lowCol], guessedNum);
	tempGrid [lowRow] [lowCol] = guessedNum;
	if (debug)
	    System.out.println ("First choice is at spot " + lowRow + "," + lowCol +
		    " and guess is " + guessedNum);
	return true;
    }


    public static void resetTempChoice (Set set, int guessedNum)
    {
	//pre: receives a set
	// post: eliminates all but the guessed number from that set

	for (int i = 1 ; i < 10 ; i++)
	    if (i != guessedNum)
		set.remove (new Integer (i));
	return;
    }


    public static boolean fillInAllDefinites (int[] [] grid, Set[] [] choice)
    {
	// pre: receives grid and choice grid
	//post: returns number of correct responses; if inError, returns 100
	if (debug)
	    System.out.println ("Entering FillInAllDefinites");

	int counter = countNumsInGrid (grid);
	int oldCounter = counter - 1;
	boolean changedSomething = true;
	boolean changedSomething2 = false;
	boolean inError = false;
	while (countNumsInGrid (grid) != 81 && changedSomething == true)
	{
	    changedSomething = false;
	    while (oldCounter != counter && !inError) //fills in definites until
		// done or hits a deadend
		{
		    oldCounter = counter;
		    if (debug)
			System.out.println ("oldCounter=" + oldCounter);
		    for (int row = 0 ; row < 9 && !inError ; row++)
		    {
			if (inError)
			    break;
			for (int col = 0 ; col < 9 && !inError ; col++)
			    if (choice [row] [col].size () == 1 && grid [row] [col] == 0)
			    {

				int num = getSingleValue (choice [row] [col]);
				if (!isPossibility (num, row, col, grid))  // could conflict
				    //with other new single value
				    {
					choice [row] [col].remove (new Integer (num));
					grid [row] [col] = 10; // indicates an error
					if (debug)
					    System.out.println ("trying to assign a number" +
						    " which creates a conflict");
					inError = true;
					break;
				    }
				else
				{
				    counter++;
				    changedSomething = true;
				    changedSomething2 = true;
				    grid [row] [col] = num;
				    if (debug)
					System.out.println ();
				    if (debug)
					System.out.println ("Placing " + num + " in grid at spot "
						+ row + "," + col);
				}
			    }
		    }
		    choice = createChoiceGrid (grid);
		}
	} //while
	if (debug)
	{
	    System.out.println ("tempGrid after filling in definites:");
	    printGrid (grid);
	}
	//if (inError)
	// return 100;
	//else
	//return counter;
	return changedSomething2;

    }


    public static int fillInMoreForcedNums (int[] [] grid, Set[] [] choice)
	//pre: receives the grid of nums and the choice grid
	//post: returns the number of nums in the grid that are not zero
	//post: if inError, return 100
    {
	boolean changed1 = true;
	boolean changed2 = true;
	while ((changed1 == true || changed2 == true) && countNumsInGrid (grid) != 81)
	{
	    for (int r = 0 ; r < 9 ; r++)
		for (int c = 0 ; c < 9 ; c++)
		    if (grid [r] [c] == 10)
			return 100;
	    changed1 = fillInAllDefinites (grid, choice);
	    if (countNumsInGrid (grid) == 81)
	    {
		return 81;
	    } //if
	    changed2 = fillInForcedNums (grid, choice);
	    if (debug)
		System.out.println ("fillInMoreForcedNums");
	    choice = createChoiceGrid (grid);
	} //while


	return countNumsInGrid (grid);
    } //fillInForcedNums method


    public static boolean fillInForcedNums (int[] [] grid, Set[] [] choice)
	//pre: receives the Set grid and the grid of filled-in numbers
	//post: fills in nums in the int grid by seeing if a given num (1-9)
	//post: can only go in one spot in a row, column, or box
    {
	if (debug)
	    System.out.println ("fillInForcedNums");
	boolean changedSomething = false;
	for (int c = 0 ; c < 9 ; c++)
	    for (int num = 1 ; num <= 9 ; num++)
	    {
		int possibleRow = numAppearsOnceInColumn (choice, c, num);
		if (possibleRow != -1 && grid [possibleRow] [c] == 0)
		{
		    changedSomething = true;
		    if (debug)
			System.out.println ("changedSomething");
		    grid [possibleRow] [c] = num;
		} //if
	    } //for
	for (int r = 0 ; r < 9 ; r++)
	    for (int num = 1 ; num <= 9 ; num++)
	    {
		int possibleCol = numAppearsOnceInRow (choice, r, num);
		if (possibleCol != -1 && grid [r] [possibleCol] == 0)
		{
		    changedSomething = true;
		    if (debug)
			System.out.println ("changedSomething");
		    grid [r] [possibleCol] = num;
		} //if
	    } //for
	for (int r = 0 ; r < 9 ; r += 3)
	    for (int c = 0 ; c < 9 ; c += 3)
	    {
		for (int num = 1 ; num <= 9 ; num++)
		{
		    int[] coordinates = numAppearsOnceInBox (choice, r, c, num);
		    if (coordinates [0] != -1 && grid [r] [c] == 0)
		    {
			int rowKnown = coordinates [0];
			int colKnown = coordinates [1];
			grid [rowKnown] [colKnown] = num;
			if (debug)
			    System.out.println ("changedSomething");
			changedSomething = true;
		    } //if
		} //for
	    } //for
	return changedSomething;
    } //fillInForcedNums method



    public static int numAppearsOnceInColumn (Set[] [] choice, int c, int x)
	//pre: receives choice grid and a num
	//post: returns the column if appears only once in all the sets in the row, -1 otherwise
    {
	Integer integer = new Integer (x);
	int numTimes = 0;
	int rowFound = 0;
	for (int r = 0 ; r < 9 ; r++)
	{
	    if (choice [r] [c].contains (integer))
	    {
		rowFound = r;
		numTimes++;
	    } //if
	} //for
	if (numTimes == 1)
	    return rowFound;
	else
	    return -1;
    } //numApprearsOnceInColumn method


    public static int[] numAppearsOnceInBox (Set[] [] choice, int r, int c, int x)
	//pre: receives choice grid, the coordinates of the top-left corner of the 3x3 box, and a number
	//post: returns the column if appears only once in all the sets in the row, -1 otherwise
    {
	Integer integer = new Integer (x);
	int numTimes = 0;
	int rowFound = 0;
	int colFound = 0;
	for (int row = r ; row < r + 3 ; row++)
	    for (int col = c ; col < c + 3 ; col++)
	    {
		if (choice [r] [c].contains (integer))
		{
		    rowFound = r;
		    colFound = c;
		    numTimes++;
		} //if
	    } //for
	int[] coordinates = { - 1, -1};
	if (numTimes == 1)
	{
	    coordinates [0] = rowFound;
	    coordinates [1] = colFound;
	} //if
	return coordinates;
    } //numApprearsOnceInBox method


    public static int numAppearsOnceInRow (Set[] [] choice, int r, int x)
	//pre: receives choice grid, num
	//post: returns the column if appears only once in all the sets in the row, -1 otherwise
    {
	Integer integer = new Integer (x);
	int numTimes = 0;
	int colFound = 0;
	for (int c = 0 ; c < 9 ; c++)
	{
	    if (choice [r] [c].contains (integer))
	    {
		colFound = c;
		numTimes++;
	    } //if
	} //for
	if (numTimes == 1)
	    return colFound;
	else
	    return -1;
    } //numApprearsOnceInRow method



    public static int randomChoice (Set set)
    { //pre: receives a Set
	//post: returns a random value from that set
	int randNum = rand.nextInt (set.size ());
	Iterator iter = set.iterator ();
	Integer integerValue = (Integer) iter.next ();
	for (int i = 0 ; i < randNum ; i++)
	{
	    integerValue = (Integer) iter.next ();
	}


	return integerValue.intValue ();
    }


    public static int countNumsInGrid (int[] [] g)
	// pre: receievs the answer grid
	// returns number of definite values (1-9) in the grid (non-zeros)
    {

	int counter = 0;
	for (int r = 0 ; r < 9 ; r++)
	    for (int c = 0 ; c < 9 ; c++)
		if (g [r] [c] != 0)
		    counter++;
	return counter;
    }



    public static int getSingleValue (Set singleSet)
    { //pre: receives a Set with one value in in
	//post: returns that single value

	for (int i = 0 ; i < 10 ; i++)
	    if (singleSet.contains (new Integer (i)))
		return i;
	if (debug)
	    System.out.println ("error in getSingleValue()");
	return -1;
    }


    public static Set[] [] createChoiceGrid (int[] [] grid)
    {
	// pre: receives grid of all definite nums (0 if empty)
	//post: returns a grid where each object holds a set of possible
	// values (only 1 if definite, 0 if impossible)
	Set[] [] s = new Set [9] [9];
	for (int row = 0 ; row < 9 ; row++)
	    for (int col = 0 ; col < 9 ; col++)
	    {
		/*if (debug)
		    System.out.println ();
		if (debug)
		    System.out.print ("spot " + row + " " + col + " could be:");*/
		s [row] [col] = new HashSet ();
		if (grid [row] [col] != 0)
		{
		    s [row] [col].add (new Integer (grid [row] [col]));
		    //if (debug)
		    // System.out.print (" " + grid [row] [col] + " (already in grid) ");
		}
		else
		{
		    for (int i = 1 ; i < 10 ; i++)
			if (isPossibility (i, row, col, grid))
			{
			    s [row] [col].add (new Integer (i));
			    //if (debug)
			    //System.out.print (" " + i + " ");
			}
		}

	    }


	return s;
    }


    public static boolean isPossibility (int num, int r, int c, int[] [] grid)
	//pre: receives the grid, a spot and a guess
	//post: returns true if that # does not violate the rules of "no multiples
	// in a row, column or 3x3 square" and false otherwise
    {
	if (!isInThreeByThreeBox (num, r, c, grid) && !inColumn (num, c, grid) &&
		!inRow (num, r, grid))
	    return true;
	else
	    return false;
    }


    public static boolean inColumn (int x, int col, int[] [] grid)
	// pre: receives a value, a column and the grid
	// returns true if the guess is in the given column, false otherwise
    {
	for (int row = 0 ; row < grid.length ; row++)
	    if (grid [row] [col] == x)
		return true;
	return false;
    }


    public static boolean inRow (int x, int row, int[] [] grid)
	// pre: receives a value, a row and the grid
	// returns true if the guess is in the given row, false otherwise
    {

	for (int col = 0 ; col < grid.length ; col++)
	    if (grid [row] [col] == x)
		return true;
	return false;
    }


    public static boolean isInThreeByThreeBox (int x, int r, int c, int[] [] grid)
	//pre: receives a value, coordinates of the top-left
	// corner of one of the 3x3 squares
	// returns true if the guess is in the given 3x3 with r,c as the top left,
	// returns false otherwise
    {
	while (r % 3 != 0)
	    r -= 1;
	while (c % 3 != 0)
	    c -= 1;
	for (int row = r ; row < (r + 3) ; row++)
	    for (int col = c ; col < (c + 3) ; col++)
	    {
		if (grid [row] [col] == x)
		    return true;
	    }


	return false;
    }



    public static int[] [] getGrid ()
	//post: returns a 9x9 puzzle grid supplied by the user
    {
	/* ask the user if they want to get the grid from a file or the user. If a file,
	prompt the user for the file name. Read 81 integers into grid, left-to-right, top-to-bottom.
	File consistes of 9 rows of 9 ints (0-9)

	If not from a file, read the 81 user-supplied ints into the grid in the same way.
	If this option is selected, print the grid at the end and ask the user if that is
	correct. Allow the user to edit spots in the grid until it is correct.
	*/
	int[] [] array = new int [9] [9];
	System.out.print ("Do you want to get the grid from a file (y or n): ");
	String ans = Stdin.readString ();
	if (ans.equalsIgnoreCase ("y"))
	{
	    System.out.println ("What file do you want to read from?");
	    String filename = Stdin.readString ();
	    TextInputFile table = new TextInputFile (filename);
	    for (int r = 0 ; r < 9 ; r++)
	    {
		for (int c = 0 ; c < 9 ; c++)
		    array [r] [c] = table.readInt ();
	    } //for
	    return array;
	} //if


	else
	{
	    System.out.println ("Type in 81 numbers, 0 for blank spaces.");
	    for (int r = 0 ; r < 9 ; r++)
		for (int c = 0 ; c < 9 ; c++)
		    array [r] [c] = Stdin.readInt ();
	    printGrid (array);
	    System.out.println ("correct?");
	    String ans1 = Stdin.readString ();
	    if (ans1.equalsIgnoreCase ("n"))
		array = getGrid ();
	    System.out.println ("here");
	    return array;
	} //else
    } //getGrid method


    public static void printGrid (int[] [] grid)
    { // post: prints the grid so that it looks like a puzzle in 9 3x3
	//squares, using  --- and |
	for (int r = 0 ; r < 9 ; r++)
	{
	    if (r % 3 == 0)
		System.out.println ("---------------------");
	    for (int c = 0 ; c < 9 ; c++)
	    {
		if (c % 3 == 0)
		    System.out.print ("|");
		if (grid [r] [c] == 0)
		    System.out.print ("  ");
		else
		    System.out.print (grid [r] [c] + " ");
	    } //for
	    System.out.println ("|");
	} //for


	System.out.println ("---------------------");
    } //printGrid method
} // Sudoku5 class