package sudoku;

/**
 * Sudoku Solver using back tracking algorithm
 * The missing value cells are denoted with value 0 
 * @author Winston Prakash
 */
public class SudokuSolver {
    int[][] cells;
    public  SudokuSolver(int[][] cells){
        this.cells = cells;
    }
    
    public void solve(){
        solveInline(0, 0);
    }
    
    private boolean solveInline(int row, int col) {
        if (col >= 9) {
            col = 0;
            if (++row >= 9)
                return true;
        }
        // Skip if the cell is already filled
        if (cells[row][col] != 0){
            return solveInline(row , col + 1);
        }
        
        for (int cellValue = 1; cellValue <= 9; cellValue++) {
            if (isValidValue(row, col, cellValue)) {
                cells[row][col] = cellValue;
                if (solveInline(row, col + 1)){
                    return true;
                }
            }
        }
        // Reset the cell value when backtrack
        cells[row][col] = 0; // reset on backtrack
        return false;
    }
    
    private boolean isValidValue(int row, int col, int cellValue) {
        // Check if valid in the row
        for (int i = 0; i < 9; i++){
            if (cellValue == cells[i][col]){
                return false;
            }
        }
        // Check if valid in the column
        for (int j = 0; j < 9; j++){
            if (cellValue == cells[row][j]){
                return false;
            }
        }
        
        //Check if valid in the sub box
        int rowOffset = (row / 3) * 3;
        int colOffset = (col / 3) * 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++){
                if (cellValue == cells[rowOffset + i][colOffset + j]){
                    return false;
                }
            }
        }
        // no violations, so it's legal
        return true;
    }
    
    
    public void display() {
        for (int i = 0; i < 9; i++) {
            if (i % 3 == 0)
                System.out.println("+-------+-------+-------+");
            for (int j = 0; j < 9; j++) {
                if (j % 3 == 0) {
                    System.out.print("| ");
                }
                if(cells[i][j] == 0){
                    System.out.print(" ");
                }else{
                  System.out.print(cells[i][j]);  
                }
                System.out.print(" ");
            }
            System.out.println("|");
        }
        System.out.println("+-------+-------+-------+");
    }
}