import java.io.*;
import java.lang.Integer.*;
import java.util.*;
import java.util.concurrent.CountDownLatch;

/** Solve Sudoku Puzzles ( See http://norvig.com/CQ )
 * TODO: Write a comment.
 * @author Peter Norvig
 **/

public class SudokuTimes {

    // Command line options
    boolean print = false;
    int nThreads = 4;
    int repeat = 1;

    /** Solve puzzles from all the files on command line.  Options:  
          -print (-noprint) : Print (or don't) each puzzle and solution
          -t<number> : Use <number> threads 
          -r<number> : Repeat each subsequent file <number> times 
        Default is "java Sudoku -noprint -t4 -r1". **/
    public static void main(String[] args) throws IOException {
	SudokuTimes s = new SudokuTimes();
	for (String arg : args) { 
	    if (!arg.startsWith("-")) s.solveList(s.readFile(arg));  
	    else if (arg.endsWith("print")) s.print = arg.equals("-print");
	    else if (arg.startsWith("-t")) s.nThreads = Integer.parseInt(arg.substring(2));
	    else if (arg.startsWith("-r")) s.repeat = Integer.parseInt(arg.substring(2));
	    else System.out.println("Unrecognized option: " + arg);
	}
    }

    /** Solve a list of puzzles in a single thread. **/
    void solveList(List<int[]> grids) {
	int[] puzzle = new int[N*N]; // Used to save a copy of the original grid
	int[][] gridpool = new int[N*N][N*N]; // Reuse grids during the search
	for (int[] grid : grids) {
	    long startTime = System.nanoTime();
	    System.arraycopy(grid, 0, puzzle, 0, grid.length); 
	    // All the real work is here:
	    int[] solution = search(initialize(grid), gridpool, 0);
	    long usecs = (System.nanoTime() - startTime) / 1000;
	    System.out.println(usecs);
	}
    }

    // Utility functions

    /** Return an array of ints {0, 1, ..., n-1} **/
    int[] range(int n) {
	int[] result = new int[n];
	for (int i=0; i<n; ++i) { result[i] = i; }
	return result;
    }

    /** Return an array of all squares in the intersection of these rows and cols **/
    int[] cross(int[] rows, int[] cols) {
	int[] result = new int[rows.length * cols.length];
	int i = 0;
	for (int r : rows) { 
	    for (int c : cols) { result[i++] = N * r + c; } 
	}
	return result;
    }

    /** Return true iff item is an element of array. **/
    boolean member(int item, int[] array) { return member(item, array, array.length); }

    /** Return true iff item is an element of array[0:end]. **/
    boolean member(int item, int[] array, int end) {
	for (int i=0; i<end; ++i) {
	    if (array[i] == item) { return true; }
	}
	return false;
    }

    // Constants

    static final int N = 9;

    final int[] DIGITS = {1<<0, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7, 1<<8};

    final int ALL_DIGITS = Integer.parseInt("111111111", 2);

    final int[] ROWS = range(N);

    final int[] COLS = ROWS;

    final int[] SQUARES = range(N*N);

    final int[][] BLOCKS = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}};

    final int[][] ALL_UNITS = new int[3*N][];

    final int[][][] UNITS = new int[N*N][3][N];

    final int[][] PEERS = new int[N*N][20];

    final int[] BIT_COUNT = new int[ALL_DIGITS+1];

    final int[] HIGHEST_ONE_BIT = new int[ALL_DIGITS+1];

    { 
	// Initialize ALL_UNITS[i] to be one of the 27 units.
	int i = 0;
	for (int r : ROWS) { ALL_UNITS[i++] = cross(new int[] {r}, COLS); }
	for (int c : COLS) { ALL_UNITS[i++] = cross(ROWS, new int[] {c}); }
	for (int[] rb : BLOCKS) { 
	    for (int[] cb : BLOCKS) { ALL_UNITS[i++] = cross(rb, cb); } 
	}

	// Initialize UNITS[s] to be an array of the 3 units for square s.
	for (int s : SQUARES) {
	    i = 0;
	    for (int[] u : ALL_UNITS) {
		if (member(s, u)) UNITS[s][i++] = u;
	    }
	}

	// Initialize PEERS[s] to be the 20 squares that are peers of square s.
	for (int s : SQUARES) {
	    i = 0;
	    for (int[] u : UNITS[s]) {
		for (int s2 : u) {
		    if (s2 != s && !member(s2, PEERS[s], i)) { PEERS[s][i++] = s2; }
		}
	    }
	}

	// Initialize BIT_COUNT[val] to be the number of 1 bits in val
	// and HIGHEST_ONE_BIT[val] to the highest bit set in the bitset val
	for (int val=0; val <= ALL_DIGITS; val++) { 
	    BIT_COUNT[val] = Integer.bitCount(val); 
	    HIGHEST_ONE_BIT[val] = Integer.highestOneBit(val);
	}
    }

    // Search algorithm

    /** Search for a solution to grid. If there is an unfilled square, select one
	and try--that is, search recursively--every possible digit for the square. **/
    int[] search(int[] grid, int[][] gridpool, int level) {
	if (grid == null) {return null;}
	int s = select_square(grid);
	if (s == -1) {return grid;} // No squares to select means we are done.
	for (int d : DIGITS) {
	    // For each possible digit d that could fill square s, try it
	    if ((d & grid[s]) > 0) {
		// Copy grid's contents into the gridpool to be used at the next level
		System.arraycopy(grid, 0, gridpool[level], 0, grid.length);
		int[] result = search(assign(gridpool[level], s, d), gridpool, level+1);
		if (result != null) {return result;}
	    }
	}
	return null;
    }

    /** Check if grid is a solution to the puzzle. **/
    boolean isSolution(int[] grid, int[] puzzle) {
	if (grid == null) {return false;}
	for (int s : SQUARES) {
	    // First check that all squares in grid have a single digit, and
	    // no filled square in the puzzle was changed in the solution.
	    if (BIT_COUNT[grid[s]] != 1 || (BIT_COUNT[puzzle[s]] == 1 && grid[s] != puzzle[s])) 
		return false; 
	}
	// Now check that each unit is a permutation of digits
	// Since we know each square has a single digit, we can check this by adding
	for (int[] u : ALL_UNITS) {
	    int sumunit = 0;
	    for (int s : u) {sumunit += grid[s]; }
	    if (sumunit != ALL_DIGITS) {
		return false;
	    }
	}
	return true;
    }

    /** Find an unfilled square. We choose one with the minimum number of possible values. 
        If all squares are filled, return -1. **/
    int select_square(int[] grid) {
	int square = -1;
	int min = 10;
	for (int s : SQUARES) {
	    int c = BIT_COUNT[grid[s]];
	    if (c < min & c > 1) {
		if (c == 2) {return s;}
		square = s; 
		min = c;
	    }
	}
	return square;
    }

    /** Assign grid[s] = d. If this leads to contradiction, return null. **/
    int[] assign(int[] grid, int s, int d) {
	if (grid == null) { return null; }
	if ((grid[s] & d) == 0) { return null; } // d is not possible for grid[s]
	grid[s] = d;
	for (int p : PEERS[s]) {
	    // If we can't consistently eliminate d from all peers of s, then fail
	    if (!eliminate(grid, p, d)) {return null;}
	}
	return grid;
    }

    /** Remove d from possibilities for grid[s]. If this is a contradiction return false. **/
    boolean eliminate(int[] grid, int s, int d) {
	if ((grid[s] & d) == 0) {return true;} // Already eliminated
	grid[s] -= d;
	return arc_consistent(grid, s) && dual_consistent(grid, s, d) && naked_pairs(grid, s);
    }

    /** Check if square s is ok: if it has multiple possible values, or if it has
	one value, which we can then consistently assign. **/
    boolean arc_consistent(int[] grid, int s) {
	int c = BIT_COUNT[grid[s]];
	return c >= 2 || (c == 1 && (assign(grid, s, grid[s]) != null));
    }

    /** After we eliminate d from possibilities for grid[s], check each unit of s
	and make sure there is some position in the unit where d can go.
	If there is only one possible place for d, assign it. **/
    boolean dual_consistent(int[] grid, int s, int d) {
	for (int[] u : UNITS[s]) {
	    int dPlaces = 0; // The number of possible places for d within unit u
	    int dplace = -1; // Try to find a place in the unit where d can go
	    for (int s2 : u) {
		if ((grid[s2] & d) > 0) { // s2 is a possible place for d
		    dPlaces++;
		    if (dPlaces > 1) break;
		    dplace = s2;
		}
	    }
	    if (dPlaces == 0 || (dPlaces == 1 && (assign(grid, dplace, d) == null))) {
		return false;
	    }
	}
	return true;
    }

    /** Look for two squares in a unit with the same two values. 
     For example, if s and s2 both have the value 8|9, then we know that 8 and 9
    must go in those two squares. We don't know which is which, but we can eliminate 
    8 and 9 from any other square s3 that is in the unit.**/
    boolean naked_pairs(int[] grid, int s) {
	int val = grid[s];
	if (BIT_COUNT[val] != 2) { return true; }
	for (int s2 : PEERS[s]) {
	    if (grid[s2] == val) {
		// s and s2 are a naked pair; find what unit(s) they share
		for (int[] u : UNITS[s]) {
		    if (member(s2, u)) {
			for (int s3 : u) { // s3 can't have any of the values in val (e.g. 8|9)
			    if (s3 != s && s3 != s2) {
				int d = HIGHEST_ONE_BIT[val];
				int d2 = val-d;
				if (!eliminate(grid, s3, d) || !eliminate(grid, s3, d2)) {
				    return false;
				}
			    }
			}
		    }
		}
	    }
	}
	return true;
    }

    // Input/Output

    /**  Read puzzles from a file, parse them, and return a list of them. **/
    List<int[]> readFile(String filename) throws IOException {
	BufferedReader in = new BufferedReader(new FileReader(filename));
	List<int[]> grids = new ArrayList<int[]>(1000);
	String gridstring;
	while ((gridstring = in.readLine()) != null) {
	    grids.add(parse(gridstring));
	}
	return grids;
    }

    /** Parse a gridstring into a grid. Use 0 for blank; a single bit for a digit. **/
    int[] parse(String gridstring) {
	int[] grid = new int[N*N];
	int s = 0;
	for (int i = 0; i < gridstring.length(); ++i) {
	    char c = gridstring.charAt(i);
	    if ('1' <= c && c <= '9') {
		grid[s++] = DIGITS[c - '1'];
	    } else if (c == '0' || c == '.') {
		grid[s++] = 0;
	    }
	}
	assert s == N*N;
	return grid;
    }

    /** Print a grid. **/
    void print(String annotation, int[] grid) {
	System.out.println(annotation);
	if (grid == null) {System.out.println("[no solution]"); return;}
	for (int s : SQUARES) {
	    System.out.format("%c %s", 
	      (BIT_COUNT[grid[s]] != 1) ? '.' : ('1' + Integer.numberOfTrailingZeros(grid[s])),
	      (s==26 || s==53) ? "\n------+-------+------\n" :
	      (s % 9 == 2 || s % 9 == 5) ? "| " :
	      (s % 9 == 8) ? "\n" : "");
	}
    }

    /** Set all the empty squares to 1|2|3|4|5|6|7|8|9 and assign the non-empty squares. **/
    int[] initialize(int[] puzzle) {
	int[] grid = new int[N*N];
	for (int s : SQUARES) { grid[s] = ALL_DIGITS; }
	for (int s : SQUARES) {
	    if (puzzle[s] != 0) { assign(grid, s, puzzle[s]); }
	}
	return grid;
    }
    
}