Rust数独生成：回溯算法生成3X3区域含重复数字的错误棋盘

我是Rust新手，将数独生成器作为首个项目开发，遵循《如何生成唯一解数独棋盘》算法，但生成的棋盘3X3区域内总是出现重复数字。怀疑is_safe函数或数字混排逻辑存在问题，恳请帮忙找出错误所在。

use std::{fmt::{Debug, Formatter, Error, Display}, ops::Deref};

use rand::Rng;
use termion::color;

const POSITIONS: [i32; 10] = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    0
];


#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Slot {
    pub val: i32
}

#[derive(Clone, Debug)]
pub struct SlotGrid {
    pub data: Vec<Vec<Slot>>
}

pub struct Board {
    data: SlotGrid,
    solved: SlotGrid,
    pub game_data: SlotGrid
}

impl Slot {
    pub fn new(val: i32) -> Self {
        if !POSITIONS.to_vec().contains(&val) {
            panic!("Invalid value");
        }

        Self { val: val }
    }
}

// TODO: custom size support
impl SlotGrid {
    pub fn new() -> Self {
        let d1: Vec<Vec<i32>> = vec![
            vec![1, 2, 3, 4, 5, 6, 7, 8, 9],
            vec![4, 5, 6, 7, 8, 9, 1, 2, 3],
            vec![7, 8, 9, 1, 2, 3, 4, 5, 6],
            vec![2, 3, 1, 5, 6, 4, 8, 9, 7],
            vec![5, 6, 4, 8, 9, 7, 2, 3, 1],
            vec![8, 9, 7, 2, 3, 1, 5, 6, 4],
            vec![3, 1, 2, 6, 4, 5, 9, 7, 8],
            vec![6, 4, 5, 9, 7, 8, 3, 1, 2],
            vec![9, 7, 8, 3, 1, 2, 6, 4, 5]
        ];

        let mut d2: Vec<Vec<Slot>> = Vec::new();

        for row in d1 {
            let mut row2: Vec<Slot> = Vec::new();
                
            for item in row {
                row2.push(Slot::new(item));
            }

            d2.push(row2);
        }

        Self { data: d2 }
    }

    pub fn set(&mut self, x: usize, y: usize, val: i32) {
        self.data[y][x].val = val;
    }

    pub fn get(&self, x: usize, y: usize) -> Slot {
        self.data[y][x]
    }

    fn swap_slots(&mut self, n1: i32, n2: i32) {
        for y in 0 .. 8 {
            for x in 0 .. 8 {
                if self.get(x, y).val == n1 {
                    self.set(x, y, n2);
                    continue;
                }
                
                if self.get(x, y).val == n2 {
                    self.set(x, y, n1);
                }
            }
        }   
    }

    fn swap_rows(&mut self, y1: usize, y2: usize) {
        let first: Vec<Slot> = self.data[y1].clone();
        let second: Vec<Slot> = self.data[y2].clone();

        self.data[y2] = first;
        self.data[y1] = second;
    }

    fn swap_cols(&mut self, x1: usize, x2: usize) {
        for y in 0 .. 8 {
            let first = self.data[y][x1];
            let second = self.data[y][x2];

            self.data[y][x1].val = second.val;
            self.data[y][x2].val = first.val;
        }
    }

    fn swap_3x3_rows(&mut self, y1: usize, y2: usize) {
        for i in 0 .. 2 {
            self.swap_rows(y1 * 3 + i, y2 * 3 + i);
        }
    }

    fn swap_3x3_cols(&mut self, x1: usize, x2:usize) {
        for i in 0 .. 2 {
            self.swap_cols(x1 * 3 + i, x2 * 3 + i);
        }
    }

    pub fn shuffle_rows(&mut self) {
        let mut rng = rand::thread_rng();
        let mut num: usize;
                    
        for i in 0 .. 8 {
            let rand = rng.gen::<usize>() % 3;
            num = i / 3;
            self.swap_rows(i, num * 3 + rand);
        }
    }

    pub fn shuffle_cols(&mut self) {
        let mut rng = rand::thread_rng();
        let mut num: usize;

        for i in 0 .. 0 {
            let rand = rng.gen::<usize>() % 3;
            num = i / 3;
            self.swap_cols(i, num * 3 + rand);
        }
    }

    pub fn shuffle_nums(&mut self) {
        let mut rng = rand::thread_rng();
        
        for i in 0 .. 8 {
            let num = rng.gen::<usize>() % 9;

            self.swap_slots(i, num.try_into().unwrap());
        }
    }

    pub fn shuffle_3x3_rows(&mut self) {
        let mut rng = rand::thread_rng();
        
        for i in 0 .. 2 {
            let num = rng.gen::<usize>() % 3;
            
            self.swap_3x3_rows(i, num);
        }
    }

    pub fn shuffle_3x3_cols(&mut self) {
        let mut rng = rand::thread_rng();
        
        for i in 0 .. 2 {
            let num = rng.gen::<usize>() % 3;

            self.swap_3x3_cols(i, num);
        }
    }
}

impl Board {
    pub fn new(cmplx: usize) -> Self {
        let mut data = SlotGrid::new();
        let mut rng = rand::thread_rng();

        data.shuffle_rows();
        data.shuffle_cols();
        data.shuffle_3x3_rows();
        data.shuffle_3x3_cols();

        let old_data = data.clone();
        let mut out: SlotGrid = data.clone(); 

        let mut i = 0;

        loop {
            // remove until usolvable and go back 1

            let x = rng.gen::<usize>() % 9;
            let y = rng.gen::<usize>() % 9;

            data.set(x, y, 0);
        
            if !back_track(&mut (data.clone()), 0, 0) && i >= cmplx {
                break;
            }
            
            i += 1;
            out = data.clone();
        }

        Self { data: out.clone(), solved: old_data, game_data: out }
    }

    pub fn is_solved(&self) -> bool {
        for i in 0 .. self.data.data.len() - 1 {
            for j in 0 .. self.data.data[i].len() - 1 {
                if self.data.data[i][j] != self.solved.data[i][j] {
                    return false;
                }
            }
        }

        true
    }
}

impl Display for Board {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
        let mut s = String::new();

        let mut i = 10;
        for row in &self.data.data {
            i -= 1;
            
            s.push_str(color::Fg(color::Magenta).to_string().deref());
            s.push_str(i.to_string().deref());
            s.push_str(" | ");
            s.push_str(color::Fg(color::Reset).to_string().deref());
            
            let mut j = 0;
            for slot in row {
                j += 1;

                let val = if slot.val == 0 {
                    "_".to_string()
                } else {
                    slot.val.to_string()
                };
                
                s.push_str(colorify(j, 9 - i, val).deref());
                s.push(' ');
            }

            s.push_str("\n");
            print!("\n");
        }
        
        s.push_str(color::Fg(color::Red).to_string().deref());
        s.push_str("    A B C D E F G H I");
        s.push_str(color::Fg(color::Reset).to_string().deref());

        write!(f, "{}", s)
    }
}

fn colorify(x: usize, y: usize, s: String) -> String {
    let x2 = x - 1;

    let corners: String = if (0 .. 3).contains(&x2) || (6 .. 9).contains(&x2) {
        color::Fg(color::LightCyan).to_string()
    } else {
        color::Fg(color::Green).to_string()
    };

    let mut out = String::new();

    if (0 .. 3).contains(&y) {
        out.push_str(corners.deref());
    }
    else if (3 .. 6).contains(&y) {
        if (3 .. 6).contains(&x2) {
            out.push_str(color::Fg(color::LightCyan).to_string().deref());
        }
        else {
            out.push_str(color::Fg(color::Green).to_string().deref());
        }
    }
    else if (6 .. 9).contains(&y) {
        out.push_str(corners.deref());
    }

    out.push_str(s.deref());
    out.push_str(color::Fg(color::Reset).to_string().deref());

    out
}

fn back_track(data: &mut SlotGrid, mut x: usize, mut y: usize) -> bool {
    if x == 8 && y == 8 {
        return true;
    }

    if x == 8 {
        y += 1;
        x = 0;
    }

    if data.get(x, y).val > 0 {
        return back_track(data, x + 1, y);
    }

    for i in 1 .. 8 {
        if is_safe(&data, x, y, i) {
            data.set(x, y, i.try_into().unwrap());
        
            if back_track(data, x + 1, y) {
                return true;
            }
        }

        data.set(x, y, 0);
    }

    return false;
}

pub fn is_safe(data: &SlotGrid, x: usize, y: usize, val: usize) -> bool {
    println!("ran is_safe");
    for y2 in 0 .. 8 {
        if data.get(x, y2).val == val.try_into().unwrap() {
            drop(data);
            println!("A");
            return false;
        }
    }

    for x2 in 0 .. 8 {
        if data.get(x2, y).val == val.try_into().unwrap() {
            drop(data);
            println!("B");
            return false;
        }
    }

    let start_row = y - (y % 3);
    let start_col = x - (x % 3);

    for i in 0 .. 2 {
        for j in 0 .. 2 {
            if data.get(i + start_row, j + start_col).val == val.try_into().unwrap() {
                drop(data);
                println!("C");
                return false;
            }
        }
    }

    drop(data);
    return true;
}

核心错误点解析 #

1. is_safe函数的3X3区域遍历范围错误 #

检查3X3宫格时，代码使用0 .. 2的循环范围，仅覆盖宫格内4个格子，遗漏第3行和第3列，无法检测区域内完整的重复数字。同时行列遍历范围0..8也遗漏了第9个格子。

修正代码：

pub fn is_safe(data: &SlotGrid, x: usize, y: usize, val: usize) -> bool {
    // 检查整列
    for y2 in 0..9 {
        if data.get(x, y2).val == val.try_into().unwrap() {
            return false;
        }
    }

    // 检查整行
    for x2 in 0..9 {
        if data.get(x2, y).val == val.try_into().unwrap() {
            return false;
        }
    }

    // 检查完整3X3宫格
    let start_row = y - (y % 3);
    let start_col = x - (x % 3);

    for i in 0..3 {
        for j in 0..3 {
            if data.get(start_col + j, start_row + i).val == val.try_into().unwrap() {
                return false;
            }
        }
    }

    true
}

2. back_track函数的数字遍历与终止条件错误 #

原代码只遍历1-7的数字，完全跳过8和9，破坏数独规则；终止条件仅判断x==8&&y==8，会遗漏最后一个格子后的收尾逻辑。

修正代码：

fn back_track(data: &mut SlotGrid, mut x: usize, mut y: usize) -> bool {
    // 列遍历到末尾，切换到下一行开头
    if x == 9 {
        y += 1;
        x = 0;
    }

    // 所有行处理完成，返回成功
    if y == 9 {
        return true;
    }

    // 当前格子已有值，直接处理下一个
    if data.get(x, y).val > 0 {
        return back_track(data, x + 1, y);
    }

    // 遍历1-9所有有效数字
    for i in 1..=9 {
        if is_safe(data, x, y, i) {
            data.set(x, y, i.try_into().unwrap());
        
            if back_track(data, x + 1, y) {
                return true;
            }
        }

        data.set(x, y, 0);
    }

    false
}

3. shuffle_cols函数循环范围无效 #

循环写为for i in 0 .. 0，导致列混排逻辑完全不执行，初始棋盘列未被打乱。

修正代码：

pub fn shuffle_cols(&mut self) {
    let mut rng = rand::thread_rng();
    let mut num: usize;

    for i in 0..9 {
        let rand = rng.gen::<usize>() % 3;
        num = i / 3;
        self.swap_cols(i, num * 3 + rand);
    }
}

4. swap_3x3_rows和swap_3x3_cols遍历范围错误 #

使用0..2循环仅交换3X3块内前2行/列，遗漏第3行/列，导致块内交换不完整。

修正代码：

fn swap_3x3_rows(&mut self, y1: usize, y2: usize) {
    for i in 0..3 {
        self.swap_rows(y1 * 3 + i, y2 * 3 + i);
    }
}

fn swap_3x3_cols(&mut self, x1: usize, x2:usize) {
    for i in 0..3 {
        self.swap_cols(x1 * 3 + i, x2 * 3 + i);
    }
}

5. shuffle_nums函数数值范围错误 #

原代码循环0..8会交换0-7的数字，遗漏8和9，还错误包含空值0，可能导致空值被替换。

修正代码：

pub fn shuffle_nums(&mut self) {
    let mut rng = rand::thread_rng();
    // 生成1-9的随机排列进行交换
    let mut nums: Vec<i32> = (1..=9).collect();
    rng.shuffle(&mut nums);
    
    for (original, new_val) in (1..=9).zip(nums) {
        self.swap_slots(original,