import java.util.Scanner;
import java.io.*;
import javax.swing.JFileChooser;

public class Sudoku {

	static int baseSize;			//the side length of a box, usually 3
	static int gridSideLength;      //the side length of the grid, usually 9
	static int[][] grid;            //the Sudoko board or grid
	static int guesses = 0;         //number of guesses made

	/**
	 * Read a file with the starting Sudoku grid. The first int is the base (box) side length. 
	 */
	static void readFile() {	    
	    File file = null;
	    JFileChooser fileopen = new JFileChooser();

	    // Ask the user to select a puzzle file
	    int ret = fileopen.showDialog(null, "Select puzzle file to open");

	    if (ret == JFileChooser.APPROVE_OPTION) {
	      file = fileopen.getSelectedFile();
	      System.out.println("Input puzzle selected: " + file);
	    }
    
	    // Open the file and read in the puzzle
	    try {
	      Scanner scanner = new Scanner(file);

		  baseSize = scanner.nextInt(); 
		  gridSideLength = baseSize *baseSize; 
	      grid = new int [gridSideLength] [gridSideLength];

	      for (int row = 0;row <gridSideLength;row++)
	         for (int col = 0; col < gridSideLength; col++) 
	            grid[row][col] = scanner.nextInt(); 

	      scanner.close();
	   } catch (FileNotFoundException e) {
		   System.out.println("Puzzle file not found");
	       e.printStackTrace();}
	}

	/**
	 * Solve the puzzle for location i,j by finding a legal value for cell i,j and then solving the from i+1,j 
	 * recursively. This method assumes that all cells on rows above and to the left of the current location 
	 * have been solved already. It skips over any cells that were filled on input and moves to the next row when 
	 * the row has been completed.
	 */
	static boolean solve(int i, int j) {
		
	    if (i == gridSideLength) {   // at end of row
	        i = 0; ++j;              // set to next row first column
	        if (j == gridSideLength) //at end of row and col (ie. end of puzzle)
	            return true;
	    }
	    if (grid[i][j] != 0)         // skip cells that are already filled 
	        return solve(i+1,j);
	
	    for (int val = 1; val <= gridSideLength; ++val) { //for each possible digit
	        if (legal(i,j,val)) {                         //check if val could be put at i,j
	            grid[i][j] = val;                         //put val at i,j
	            if (solve(i+1,j))                         //and solve the remainder
	                return true;
	        }
	    }
	    grid[i][j] = 0;                                   // since no digit worked at i,j reset it to 0 and return false
	    return false;
	}

	
	/**
	 * Return true if val can be placed at cell i,j legally (ie. without violating the row, col, or box constraints
	 */
	static boolean legal(int i, int j, int val) {
		
		++guesses;                                //count the number of guesses (ie. calls to legal())
		
		//Check the row constraint
	    for (int k = 0; k < gridSideLength; ++k)  // check for duplicates in the row
	        if (val == grid[k][j])
	            return false;                     //duplicate found, return false
	
	    //Check the col constraint
	    for (int k = 0; k < gridSideLength; ++k)  // check for duplicates in the col
	        if (val == grid[i][k])
	            return false;                     //duplicate found, return false
	
	    //Check the 3x3 box constraint
	    int boxRowOffset = (i / baseSize)*baseSize;  //Find the top left corner of the baseSize * baseSize box
	    int boxColOffset = (j / baseSize)*baseSize;
	    for (int k = 0; k < baseSize; ++k)           // check the rows and cols of the box for duplicates
	        for (int m = 0; m < baseSize; ++m)
	            if (val == grid[boxRowOffset+k][boxColOffset+m])
	                return false;                 //duplicate found, return false
	
	    return true; // no violations, so it's legal
	}
	
	/**
	 * Display the Grid
	 */
	static void writeGrid() {
	    for (int i = 0; i < gridSideLength; ++i) {
	        if (i % baseSize == 0)
	            System.out.println(" -----------------------");
	        for (int j = 0; j < gridSideLength; ++j) {
	            if (j % baseSize == 0) System.out.print("| ");
	            System.out.print(grid[i][j] == 0
	                             ? " "
	                             : Integer.toString(grid[i][j]));
	
	            System.out.print(' ');
	        }
	        System.out.println("|");
	    }
	    System.out.println(" -----------------------");
	}
	
	public static void main(String[] args) {
	    readFile();         //read the puzzle file
	    writeGrid();        //display the grid
	    
	    if (solve(0,0)){    // solve starting the the top left corner
	        writeGrid();    // Solve succeeded so display the result
	        System.out.println("Solved in " + guesses + " guesses.");
	    }
	    else                //Solve failed
	        System.out.println("No Solution. Tried " + guesses + " guesses.");
	        
	}
}