// Sudoku solver as presented in the book (use Main class to test it)
import java.util.HashSet;
import java.util.Set;

public class Sudoku {
    private int[][] grid;
    private Set<Integer>[][] candidates;
    
    
    // constructor
    @SuppressWarnings("unchecked")
    public Sudoku(int[][] grid) {
        // Check if the input grid is valid
        if (grid.length != 9 || grid[0].length != 9) {
            throw new IllegalArgumentException("Grid must be a 9x9 array.");
        }
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (grid[i][j] < 0 || grid[i][j] > 9) {
                    throw new IllegalArgumentException("Grid values must be between 0 and 9.");
                }
            }
        }
        
        // Initialize the grid
        this.grid = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                this.grid[i][j] = grid[i][j];
            }
        }
        
        // Initialize the candidates array
        this.candidates = new HashSet[9][9];
        initializeCandidates();
    }
    
    // Method to initialize candidates with numbers 1 to 9
    private void initializeCandidates() {
        for (int row = 0; row < 9; row++) {
            for (int column = 0; column < 9; column++) {
                this.candidates[row][column] = new HashSet<>();
                if (grid[row][column] == 0) {
                    for (int number = 1; number <= 9; number++) {
                        this.candidates[row][column].add(number);
                    }
                }
            }
        }
    }
    
    // Solve the Sudoku puzzle
    public boolean solve() {
        int n;
        do {
            n = 0;
            n += fillSingleEmptyInRow();
            n += fillSingleEmptyInColumn();
            n += fillSingleEmptyInBlock();
            updateCandidates();
            n += fillCellsWithSingleCandidate();
            System.out.println("Filled " + n + " cells.");
        } while (n > 0);
        
        if (countEmptyCells()==0) {
            System.out.println("Sudoku puzzle solved!");
            return true;
        }
        
        System.out.println("Could not solve the puzzle.");
        printSudokuWithSpaces();
        return false;
    }
    
    // Fill in a single empty cell in each row
    private int fillSingleEmptyInRow() {
        int cellsFilled = 0;
        for (int row = 0; row < 9; row++) {
            int emptyCount = 0;
            int emptyColumn = -1;
            
            for (int column = 0; column < 9; column++) {
                if (grid[row][column] == 0) {
                    emptyCount++;
                    emptyColumn = column;
                }
            }
            
            if (emptyCount == 1) {
                boolean[] present = new boolean[10];
                for (int column = 0; column < 9; column++) {
                    present[grid[row][column]] = true;
                }
                
                for (int number = 1; number <= 9; number++) {
                    if (!present[number]) {
                        grid[row][emptyColumn] = number;
                        cellsFilled++;
                        break;
                    }
                }
            }
        }
        return cellsFilled;
    }
    
    // Fill in a single empty cell in each column
    private int fillSingleEmptyInColumn() {
        int cellsFilled = 0;
        for (int column = 0; column < 9; column++) {
            int emptyCount = 0;
            int emptyRow = -1;
            
            for (int row = 0; row < 9; row++) {
                if (grid[row][column] == 0) {
                    emptyCount++;
                    emptyRow = row;
                }
            }
            
            if (emptyCount == 1) {
                boolean[] present = new boolean[10];
                for (int row = 0; row < 9; row++) {
                    present[grid[row][column]] = true;
                }
                
                for (int number = 1; number <= 9; number++) {
                    if (!present[number]) {
                        grid[emptyRow][column] = number;
                        cellsFilled++;
                        break;
                    }
                }
            }
        }
        return cellsFilled;
    }
    
    // Fill in a single empty cell in each block
    private int fillSingleEmptyInBlock() {
        int cellsFilled = 0;
        for (int blockRow = 0; blockRow < 3; blockRow++) {
            for (int blockColumn = 0; blockColumn < 3; blockColumn++) {
                int emptyCount = 0;
                int emptyRow = -1;
                int emptyColumn = -1;
                
                boolean[] present = new boolean[10];
                for (int row = 0; row < 3; row++) {
                    for (int column = 0; column < 3; column++) {
                        int value = grid[blockRow * 3 + row][blockColumn * 3 + column];
                        if (value == 0) {
                            emptyCount++;
                            emptyRow = blockRow * 3 + row;
                            emptyColumn = blockColumn * 3 + column;
                        } else {
                            present[value] = true;
                        }
                    }
                }
                
                if (emptyCount == 1) {
                    for (int number = 1; number <= 9; number++) {
                        if (!present[number]) {
                            grid[emptyRow][emptyColumn] = number;
                            cellsFilled++;
                            break;
                        }
                    }
                }
            }
        }
        return cellsFilled;
    }
    
    // Update the candidate set for each cell
    private void updateCandidates() {
        for (int row = 0; row < 9; row++) {
            for (int column = 0; column < 9; column++) {
                // Skip cells that are already filled
                if (grid[row][column] != 0) {
                    candidates[row][column].clear();
                    continue;
                }
    
                // Remove numbers present in the same row
                for (int col = 0; col < 9; col++) {
                    if (grid[row][col] != 0) {
                        candidates[row][column].remove(grid[row][col]);
                    }
                }
    
                // Remove numbers present in the same column
                for (int r = 0; r < 9; r++) {
                    if (grid[r][column] != 0) {
                        candidates[row][column].remove(grid[r][column]);
                    }
                }
    
                // Remove numbers present in the same 3x3 block
                int startRow = (row / 3) * 3;
                int startCol = (column / 3) * 3;
                for (int r = startRow; r < startRow + 3; r++) {
                    for (int col = startCol; col < startCol + 3; col++) {
                        if (grid[r][col] != 0) {
                            candidates[row][column].remove(grid[r][col]);
                        }
                    }
                }
            }
        }
    }
    
    // Fill cells with a single candidate
    private int fillCellsWithSingleCandidate() {
        int cellsSolved = 0;
    
        for (int row = 0; row < 9; row++) {
            for (int column = 0; column < 9; column++) {
                // Check if the cell is empty
                if (grid[row][column] == 0) {
                    Set<Integer> candidateSet = candidates[row][column];
                    
                    // Check if there is exactly one candidate
                    if (candidateSet.size() == 1) {
                        int candidate = candidateSet.iterator().next();
                        grid[row][column] = candidate;
                        cellsSolved++;
                        
                        // Clear the candidate set as it's no longer needed
                        candidateSet.clear();
                    }
                }
            }
        }
    
        return cellsSolved;
    }

    // Count the number of empty cells in the grid
    private int countEmptyCells() {
        int emptyCount = 0;
        for (int row = 0; row < 9; row++) {
            for (int column = 0; column < 9; column++) {
                if (grid[row][column] == 0) {
                    emptyCount++;
                }
            }
        }
        return emptyCount;
    }
    
    // Print the Sudoku puzzle
    private void printSudokuWithSpaces() {
        for (int row = 0; row < 9; row++) {
            for (int column = 0; column < 9; column++) {
                if (grid[row][column] == 0) {
                    System.out.print("  "); // Two spaces for better formatting
                } else {
                    System.out.print(grid[row][column] + " ");
                }
            }
            System.out.println();
        }
    }
    
}
