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();
        System.out.println("solutions:" + count);
        System.out.println("elapsed:" + sudoku.getElapsed() + "ms");
        System.out.println(sudoku.getSolutionText());
    }

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



    /**
     * Sets up based on the given ints.
     */
    public Sudoku(int[][] ints) {
        base = ints;
        spotList = new ArrayList<Spot>();
        for(int i=0; i<SIZE; i++) {
            for(int j=0; j<SIZE; j++) {
                if(base[i][j]==0)
                    spotList.add(new Spot(i, j, base[i][j]));
            }
        }
        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() {
    	long startTime = System.currentTimeMillis();
    	mutableInt result = new mutableInt();
    	getSolveNum(0, result);
    	long endTime = System.currentTimeMillis();
    	usedTime = endTime-startTime;
    	return result.getValue();
    }

    public void getSolveNum(int index, mutableInt result) {
    	if(result.getValue()==100) return;
        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];
                    }
                }
            }
            result.setValue(result.getValue()+1);
            return;
        }
        Spot curr = spotList.get(index);
        ArrayList<Integer> variances = curr.getValidList();
        for(int i=0; i<variances.size(); i++) {
            base[curr.getRow()][curr.getColumn()] = variances.get(i);
            getSolveNum(index+1, result);
        }
        base[curr.getRow()][curr.getColumn()] = 0;
    }

    public String getSolutionText() {
    	if(resultGrid==null)	return "";
    	String result = "";
    	for(int i=0; i<SIZE; i++) {
    		for(int j=0; j<SIZE; j++) {
    			result += resultGrid[i][j]+" ";
    		}
    		result +="\n";
    	}
    	return result;
    }

    public long getElapsed() {
        return usedTime;
    }

    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 int getVariance() {
            return variance;
        }

        public ArrayList<Integer> getValidList(){
            ArrayList<Boolean> check = new ArrayList<Boolean>();
            for(int i=0; i<SIZE; i++) {
                check.add(false);
            }
            checkSquare(check);
            checkColumn(check);
            checkRow(check);
            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) {
            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];
                    if(currValue!=0) arr.set(currValue-1, true);
                }
            }
        }
        private void checkRow(ArrayList<Boolean> arr) {
            int bound = row-row%PART;
            for(int i=0; i<bound; i++) {
                int currValue = base[i][column];
                if(currValue!=0)
                    arr.set(currValue-1, true);
            }
            for(int i=bound+PART; i<SIZE; i++) {
                int currValue = base[i][column];
                if(currValue!=0)
                    arr.set(currValue-1, true);
            }
        }

        private void checkColumn(ArrayList<Boolean> arr) {
            int bound = column-column%PART;
            for(int i=0; i<bound; i++) {
                int currValue = base[row][i];
                if(currValue!=0)
                    arr.set(currValue-1, true);
            }
            for(int i=bound+PART; i<SIZE; i++) {
                int currValue = base[row][i];
                if(currValue!=0)
                    arr.set(currValue-1, true);
            }
        }

        public int compareByVariance(Spot second) {
            return this.variance-second.getVariance();
        }
    }


    private class mutableInt {
    	private int value;

    	public mutableInt() {
    		this.value = 0;
    	}

    	public mutableInt(int value) {
    		this.value = value;
    	}

    	public int getValue() {
    		return value;
    	}

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

}