import jdk.internal.util.xml.impl.Pair;

import javax.swing.*;
import java.util.*;
import java.util.function.Consumer;

import static java.lang.Integer.highestOneBit;
import static java.lang.Integer.min;
import static java.util.Collections.sort;

/*
 * 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());
	}


	/**
	 * Instance variables
	 */

	private int[] maskInRows;
	private int[] maskInCols;
	private int[] maskInSmlSqueares;
	private int[][] grid;
	private ArrayList<Spot> spots;
	private long timeSpentOnSolving;
	private String solutionText;


	/**
	 * Sets up based on the given ints.
	 */
	public Sudoku(int[][] ints) {
		solutionText = "";
		timeSpentOnSolving = 0;

		spots = new ArrayList<>();
		maskInCols = new int[SIZE];
		maskInRows = new int[SIZE];
		maskInSmlSqueares = new int[SIZE];
		grid = new int[SIZE][SIZE];


		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				Spot curSpot = new Spot(i, j);
				curSpot.set(ints[i][j]);
				if (curSpot.getValue() == 0)
					spots.add(curSpot);
				grid[i][j] = ints[i][j];
			}
		}

		sort(spots);
	}

	/**
	 * @param st
	 */
	public Sudoku(String st) {
		this(textToGrid(st));
	}

	/**
	 *
	 */
	private void fillSolutionText() {
		int[][] ans = new int[SIZE][SIZE];

		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				ans[i][j] = grid[i][j];
			}
		}

		for (Spot item : spots) {
			ans[item.getRow()][item.getColumn()] = item.getValue();
		}
		solutionText = gridToText(ans);
	}

	/**
	 * @param ind
	 * @return
	 */
	private int getAns(int ind) {
		if (ind >= spots.size()) {
			if (solutionText.length() == 0) {
				fillSolutionText();
			}
			return 1;
		}
		int ans = 0;
		Spot curSpot = spots.get(ind);
		for (int canPut : curSpot) {
			curSpot.set(canPut);
			ans = ans + getAns(ind + 1);
			curSpot.set(0);
			if (ans >= MAX_SOLUTIONS) return MAX_SOLUTIONS;
		}
		return ans;
	}

	/**
	 *
	 * @param gr
	 * @return
	 */
	private String gridToText(int[][] gr) {
		StringBuilder res = new StringBuilder();
		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				res.append(gr[i][j] + (j < SIZE - 1 ? " " : "\n"));
			}
		}
		return res.toString();
	}

	/**
	 * Solves the puzzle, invoking the underlying recursive search.
	 */
	public int solve() {
		long beforeRecursion = System.currentTimeMillis();
		int counter = getAns(0);
		long afterRecursion = System.currentTimeMillis();
		timeSpentOnSolving = afterRecursion - beforeRecursion;
		return counter;
	}

	public String getSolutionText() {
		return solutionText;
	}

	public long getElapsed() {
		return timeSpentOnSolving;
	}

	/**
	 * @return
	 */
	@Override
	public String toString() {
		return gridToText(grid);
	}

	/**
	 * This is private Spot class, which is responsible on
	 * Every 81 board cell
	 * I't has his tests in SpotTest, but it must be modified
	 * As public static
	 */
	private class Spot implements Iterable<Integer>, Comparable {
		private int x;
		private int y;
		private int value;

		public static final int markAll = 0x3FE;

		/**
		 * @param x
		 * @param y
		 */
		public Spot(int x, int y) {
			this.x = x;
			this.y = y;
		}

		/**
		 * @return
		 */

		public int getRow() {
			return x;
		}

		/**
		 * @return
		 */

		public int getColumn() {
			return y;
		}

		/**
		 * @return
		 */

		public int getSmallSquare() {
			int smallRow = getRow() / Sudoku.PART;
			int smallColl = getColumn() / Sudoku.PART;
			return smallRow * Sudoku.PART + smallColl;
		}

		/**
		 * @param value
		 */
		private void fillMasks(int value) {
			maskInRows[getRow()] ^= (1 << value);
			maskInCols[getColumn()] ^= (1 << value);
			maskInSmlSqueares[getSmallSquare()] ^= (1 << value);

		}

		/**
		 * @param value
		 */
		public void set(int value) {
			if (this.value > 0)
				fillMasks(this.value);
			this.value = value;
			if (this.value > 0)
				fillMasks(this.value);
		}

		/**
		 * @return
		 */
		public int getValue() {
			return value;
		}

		/**
		 * @return
		 */
		public int getMarked() {
			int ans = maskInRows[getRow()] | maskInCols[getColumn()] | maskInSmlSqueares[getSmallSquare()];
			return ans;
		}

		/**
		 * @return
		 */
		@Override
		public Iterator iterator() {
			Iterator it = new Iterator() {
				private Integer mask = getMarked() ^ markAll;

				@Override
				public boolean hasNext() {
					return Integer.bitCount(mask) > 0;
				}

				@Override
				public Object next() {
					Integer ans = 0;
					ans = Integer.numberOfTrailingZeros(mask);
					int prevMask = mask;
					mask = mask ^ (1 << ans);
					return ans;
				}
			};
			return it;
		}

		/**
		 * @param o
		 * @return
		 */
		@Override
		public int compareTo(Object o) {
			int othr = ((Spot) o).getMarked();
			int mine = this.getMarked();

			if (Integer.bitCount(mine) < Integer.bitCount(othr)) return 1;
			if (Integer.bitCount(mine) > Integer.bitCount(othr)) return -1;
			return 0;
		}
	}

}