fn example_grid() -> [[i32; 9]; 9] {
    [
        [1, 0, 0, 0, 0, 7, 0, 9, 0],
        [0, 3, 0, 0, 2, 0, 0, 0, 8],
        [0, 0, 9, 6, 0, 0, 5, 0, 0],
        [0, 0, 5, 3, 0, 0, 9, 0, 0],
        [0, 1, 0, 0, 8, 0, 0, 0, 2],
        [6, 0, 0, 0, 0, 4, 0, 0, 0],
        [3, 0, 0, 0, 0, 0, 0, 1, 0],
        [0, 4, 0, 0, 0, 0, 0, 0, 7],
        [0, 0, 7, 0, 0, 0, 3, 0, 0],
    ]
}

fn pretty_print_grid(grid: &[[i32; 9]; 9]) {
    println!("--------------");
    for row in grid {
        for &val in row {
            print!("{} ", val);
        }
        println!();
    }
}

fn check(grid: &[[i32; 9]; 9]) -> bool {
    for i in 0..9 {
        let mut row_check = [false; 9];
        let mut col_check = [false; 9];
        let mut square_check = [false; 9];

        for j in 0..9 {
            let row_val = grid[i][j];
            let col_val = grid[j][i];
            let sq_val = grid[(i / 3) * 3 + j / 3][(i % 3) * 3 + j % 3];

            if row_val != 0 {
                if row_check[(row_val - 1) as usize] {
                    return false;
                }
                row_check[(row_val - 1) as usize] = true;
            }

            if col_val != 0 {
                if col_check[(col_val - 1) as usize] {
                    return false;
                }
                col_check[(col_val - 1) as usize] = true;
            }

            if sq_val != 0 {
                if square_check[(sq_val - 1) as usize] {
                    return false;
                }
                square_check[(sq_val - 1) as usize] = true;
            }
        }
    }
    true
}

fn deepcopy(grid: &[[i32; 9]; 9]) -> [[i32; 9]; 9] {
    *grid
}

fn solve(grid: &[[i32; 9]; 9], guess_depth: u32) -> (bool, [[i32; 9]; 9], u32) {
    if !check(grid) {
        return (false, *grid, guess_depth);
    }

    // Check for forced cells first (naked singles)
    for i in 0..9 {
        for j in 0..9 {
            if grid[i][j] == 0 {
                let mut valid_vals = vec![];
                for k in 1..=9 {
                    let mut copied = deepcopy(grid);
                    copied[i][j] = k;
                    if check(&copied) {
                        valid_vals.push(k);
                    }
                }
                if valid_vals.len() == 0 {
                    return (false, *grid, guess_depth); // dead end
                }
                if valid_vals.len() == 1 {
                    // Forced — fill and continue, depth unchanged
                    let mut copied = deepcopy(grid);
                    copied[i][j] = valid_vals[0];
                    return solve(&copied, guess_depth);
                }
            }
        }
    }

    // No forced cell — must guess. Find first empty cell and branch.
    for i in 0..9 {
        for j in 0..9 {
            if grid[i][j] == 0 {
                let mut max_depth_seen = guess_depth;
                for k in 1..=9 {
                    let mut copied = deepcopy(grid);
                    copied[i][j] = k;
                    let (finished, solved, depth) = solve(&copied, guess_depth + 1);
                    if depth > max_depth_seen {
                        max_depth_seen = depth;
                    }
                    if finished {
                        return (true, solved, max_depth_seen);
                    }
                }
                return (false, *grid, max_depth_seen);
            }
        }
    }

    // No empty cells and check passed
    (true, *grid, guess_depth)
}

fn main() {
    let example = example_grid();
    let (finished, solved, max_depth) = solve(&example, 0);
    if finished {
        pretty_print_grid(&solved);
        println!("Max guess depth needed: {}", max_depth);
    } else {
        println!("No solution found.");
    }
}
