package assign3;

import java.util.*;

/*
 * Encapsulates a Sudoku grid to be solved.
 * CS108 Stanford.
 */
public class Sudoku {
	// Provided grid data for main/testing
	// The instance variable strategy is up to you.

	// Provided easy 1 6 grid
	// (can paste this text into the GUI too)
	public static final int[][] easyGrid = Sudoku.stringsToGrid(
	"1 6 4 0 0 0 0 0 2",
	"2 0 0 4 0 3 9 1 0",
	"0 0 5 0 8 0 4 0 7",
	"0 9 0 0 0 6 5 0 0",
	"5 0 0 1 0 2 0 0 8",
	"0 0 8 9 0 0 0 3 0",
	"8 0 9 0 4 0 2 0 0",
	"0 7 3 5 0 9 0 0 1",
	"4 0 0 0 0 0 6 7 9");


	// Provided medium 5 3 grid
	public static final int[][] mediumGrid = Sudoku.stringsToGrid(
	 "530070000",
	 "600195000",
	 "098000060",
	 "800060003",
	 "400803001",
	 "700020006",
	 "060000280",
	 "000419005",
	 "000080079");

	// Provided hard 3 7 grid
	// 1 solution this way, 6 solutions if the 7 is changed to 0
	public static final int[][] hardGrid = Sudoku.stringsToGrid(
	"3 7 0 0 0 0 0 8 0",
	"0 0 1 0 9 3 0 0 0",
	"0 4 0 7 8 0 0 0 3",
	"0 9 3 8 0 0 0 1 2",
	"0 0 0 0 4 0 0 0 0",
	"5 2 0 0 0 6 7 9 0",
	"6 0 0 0 2 1 0 4 0",
	"0 0 0 5 3 0 9 0 0",
	"0 3 0 0 0 0 0 5 1");


	public static final int SIZE = 9;  // size of the whole 9x9 puzzle
	public static final int PART = 3;  // size of each 3x3 part
	public static final int MAX_SOLUTIONS = 100;

	// Provided various static utility methods to
	// convert data formats to int[][] grid.

	/**
	 * Returns a 2-d grid parsed from strings, one string per row.
	 * The "..." is a Java 5 feature that essentially
	 * makes "rows" a String[] array.
	 * (provided utility)
	 * @param rows array of row strings
	 * @return grid
	 */
	public static int[][] stringsToGrid(String... rows) {
		int[][] result = new int[rows.length][];
		for (int row = 0; row<rows.length; row++) {
			result[row] = stringToInts(rows[row]);
		}
		return result;
	}


	/**
	 * Given a single string containing 81 numbers, returns a 9x9 grid.
	 * Skips all the non-numbers in the text.
	 * (provided utility)
	 * @param text string of 81 numbers
	 * @return grid
	 */
	public static int[][] textToGrid(String text) {
		int[] nums = stringToInts(text);
		if (nums.length != SIZE*SIZE) {
			throw new RuntimeException("Needed 81 numbers, but got:" + nums.length);
		}

		int[][] result = new int[SIZE][SIZE];
		int count = 0;
		for (int row = 0; row<SIZE; row++) {
			for (int col=0; col<SIZE; col++) {
				result[row][col] = nums[count];
				count++;
			}
		}
		return result;
	}


	/**
	 * Given a string containing digits, like "1 23 4",
	 * returns an int[] of those digits {1 2 3 4}.
	 * (provided utility)
	 * @param string string containing ints
	 * @return array of ints
	 */
	public static int[] stringToInts(String string) {
		int[] a = new int[string.length()];
		int found = 0;
		for (int i=0; i<string.length(); i++) {
			if (Character.isDigit(string.charAt(i))) {
				a[found] = Integer.parseInt(string.substring(i, i+1));
				found++;
			}
		}
		int[] result = new int[found];
		System.arraycopy(a, 0, result, 0, found);
		return result;
	}


	// Provided -- the deliverable main().
	// You can edit to do easier cases, but turn in
	// solving hardGrid.
	public static void main(String[] args) {
		Sudoku sudoku;
		sudoku = new Sudoku(hardGrid);

//		System.out.println(sudoku); // print the raw problem
		int count = sudoku.solve(0);
		System.out.println("da pasuxiaaa: "+count);
//		System.out.println("solutions:" + count);
//		System.out.println("elapsed:" + sudoku.getElapsed() + "ms");
//		System.out.println(sudoku.getSolutionText());
	}

	private Spot[][] base;
	private ArrayList<Spot> spotList;
	private int[][] resultGrid;

	/**
	 * Sets up based on the given ints.
	 */
	public Sudoku(int[][] ints) {
		base = new Spot[SIZE][SIZE];
		spotList = new ArrayList<Spot>();
		for(int i=0; i<SIZE; i++) {
			for(int j=0; j<SIZE; j++) {
				base[i][j] = new Spot(i, j, ints[i][j]);
				if(base[i][j].value==0)
					spotList.add(base[i][j]);
			}
		}
		for(int i=0; i<SIZE; i++) {
			for(int j=0; j<SIZE; j++) {
				int currVar = getValidList(i, j).size();
				base[i][j].setVariance(currVar);
			}
		}
		Collections.sort(spotList, new sortByVariance());
	}

	class sortByVariance implements Comparator<Spot> {
		public int compare(Spot first, Spot second) {
			return first.compareByVariance(second);
		}
	}

	/**
	 * Solves the puzzle, invoking the underlying recursive search.
	 */
	public int solve(int index) {
		if(index==spotList.size()) {
			if(resultGrid == null) {
				resultGrid = new int[SIZE][SIZE];
				for(int i=0; i<SIZE; i++) {
					for(int j=0; j<SIZE; j++) {
						resultGrid[i][j] = base[i][j].getValue();
					}
				}
			}
			return 1;
		}
		Spot curr = spotList.get(index);
		ArrayList<Integer> variances = getValidList(curr.getRow(), curr.getColumn());
		int result = 0;
		for(int i=0; i<variances.size(); i++) {
			curr.setValue(variances.get(i));
			result += solve(index+1);
		}
		curr.setValue(0);
		return result;
	}

	public String getSolutionText() {
		return ""; // YOUR CODE HERE
	}

	public long getElapsed() {
		return 0; // YOUR CODE HERE
	}

	private class Spot {
		private int value;
		private int column;
		private int row;
		private int variance;

		public Spot(int row, int column, int value) {
			this.value = value;
			this.column = column;
			this.row = row;
		}

		public void setValue(int value) {
			this.value = value;
		}

		public int getValue() {
			return value;
		}

		public int getRow() {
			return row;
		}

		public int getColumn() {
			return column;
		}

		public void setVariance(int variance) {
			this.variance = variance;
		}

		public int getVariance() {
			return variance;
		}

		public int compareByVariance(Spot second) {
			return second.variance-this.variance;
		}
	}
	public ArrayList<Integer> getValidList(int row, int column){
		ArrayList<Boolean> check = new ArrayList<Boolean>();
		for(int i=0; i<SIZE; i++) {
			check.add(false);
		}
		checkSquare(check, row, column);
		checkColumn(check, row, column);
		checkRow(check, row, column);
		ArrayList<Integer> result = new ArrayList<Integer>();
		for(int i=0; i<check.size(); i++) {
			if(!check.get(i)) result.add(i+1);
		}
		return result;
	}
	private void checkSquare(ArrayList<Boolean> arr, int row, int column) {
		for(int i=0; i<PART; i++) {
			int currRow = row-row%PART+i;
			for(int j=0; j<PART; j++) {
				int currCol = column-column%PART+j;
				int currValue = base[currRow][currCol].value;
				if(currValue!=0) arr.set(currValue-1, true);
			}
		}
	}
	private void checkRow(ArrayList<Boolean> arr, int row, int column) {
		int bound = row-row%PART;
		for(int i=0; i<bound; i++) {
			int currValue = base[i][column].value;
			if(currValue!=0)
				arr.set(currValue-1, true);
		}
		for(int i=bound+PART; i<SIZE; i++) {
			int currValue = base[i][column].value;
			if(currValue!=0)
				arr.set(currValue-1, true);
		}
	}
	private void checkColumn(ArrayList<Boolean> arr, int row, int column) {
		int bound = column-column%PART;
		for(int i=0; i<bound; i++) {
			int currValue = base[row][i].value;
			if(currValue!=0)
				arr.set(currValue-1, true);
		}
		for(int i=bound+PART; i<SIZE; i++) {
			int currValue = base[row][i].value;
			if(currValue!=0)
				arr.set(currValue-1, true);
		}
	}

}