1fn example_grid() -> [[i32; 9]; 9] {
  2    [
  3        [1, 0, 0, 0, 0, 7, 0, 9, 0],
  4        [0, 3, 0, 0, 2, 0, 0, 0, 8],
  5        [0, 0, 9, 6, 0, 0, 5, 0, 0],
  6        [0, 0, 5, 3, 0, 0, 9, 0, 0],
  7        [0, 1, 0, 0, 8, 0, 0, 0, 2],
  8        [6, 0, 0, 0, 0, 4, 0, 0, 0],
  9        [3, 0, 0, 0, 0, 0, 0, 1, 0],
 10        [0, 4, 0, 0, 0, 0, 0, 0, 7],
 11        [0, 0, 7, 0, 0, 0, 3, 0, 0],
 12    ]
 13}
 14
 15fn pretty_print_grid(grid: &[[i32; 9]; 9]) {
 16    println!("--------------");
 17    for row in grid {
 18        for &val in row {
 19            print!("{} ", val);
 20        }
 21        println!();
 22    }
 23}
 24
 25fn check(grid: &[[i32; 9]; 9]) -> bool {
 26    for i in 0..9 {
 27        let mut row_check = [false; 9];
 28        let mut col_check = [false; 9];
 29        let mut square_check = [false; 9];
 30
 31        for j in 0..9 {
 32            let row_val = grid[i][j];
 33            let col_val = grid[j][i];
 34            let sq_val = grid[(i / 3) * 3 + j / 3][(i % 3) * 3 + j % 3];
 35
 36            if row_val != 0 {
 37                if row_check[(row_val - 1) as usize] {
 38                    return false;
 39                }
 40                row_check[(row_val - 1) as usize] = true;
 41            }
 42
 43            if col_val != 0 {
 44                if col_check[(col_val - 1) as usize] {
 45                    return false;
 46                }
 47                col_check[(col_val - 1) as usize] = true;
 48            }
 49
 50            if sq_val != 0 {
 51                if square_check[(sq_val - 1) as usize] {
 52                    return false;
 53                }
 54                square_check[(sq_val - 1) as usize] = true;
 55            }
 56        }
 57    }
 58    true
 59}
 60
 61fn deepcopy(grid: &[[i32; 9]; 9]) -> [[i32; 9]; 9] {
 62    *grid
 63}
 64
 65fn solve(grid: &[[i32; 9]; 9], guess_depth: u32) -> (bool, [[i32; 9]; 9], u32) {
 66    if !check(grid) {
 67        return (false, *grid, guess_depth);
 68    }
 69
 70    // Check for forced cells first (naked singles)
 71    for i in 0..9 {
 72        for j in 0..9 {
 73            if grid[i][j] == 0 {
 74                let mut valid_vals = vec![];
 75                for k in 1..=9 {
 76                    let mut copied = deepcopy(grid);
 77                    copied[i][j] = k;
 78                    if check(&copied) {
 79                        valid_vals.push(k);
 80                    }
 81                }
 82                if valid_vals.len() == 0 {
 83                    return (false, *grid, guess_depth); // dead end
 84                }
 85                if valid_vals.len() == 1 {
 86                    // Forced — fill and continue, depth unchanged
 87                    let mut copied = deepcopy(grid);
 88                    copied[i][j] = valid_vals[0];
 89                    return solve(&copied, guess_depth);
 90                }
 91            }
 92        }
 93    }
 94
 95    // No forced cell — must guess. Find first empty cell and branch.
 96    for i in 0..9 {
 97        for j in 0..9 {
 98            if grid[i][j] == 0 {
 99                let mut max_depth_seen = guess_depth;
100                for k in 1..=9 {
101                    let mut copied = deepcopy(grid);
102                    copied[i][j] = k;
103                    let (finished, solved, depth) = solve(&copied, guess_depth + 1);
104                    if depth > max_depth_seen {
105                        max_depth_seen = depth;
106                    }
107                    if finished {
108                        return (true, solved, max_depth_seen);
109                    }
110                }
111                return (false, *grid, max_depth_seen);
112            }
113        }
114    }
115
116    // No empty cells and check passed
117    (true, *grid, guess_depth)
118}
119
120fn main() {
121    let example = example_grid();
122    let (finished, solved, max_depth) = solve(&example, 0);
123    if finished {
124        pretty_print_grid(&solved);
125        println!("Max guess depth needed: {}", max_depth);
126    } else {
127        println!("No solution found.");
128    }
129}