rust 数独生成回溯创建不正确的板

xoshrz7s  于 2023-01-21  发布在  其他
关注(0)|答案(1)|浏览(118)

我对Rust相当陌生,创建这个数独生成器是我的第一个项目之一。我正在跟踪algorithm - How to generate Sudoku boards with unique solutions,但它一直在生成每个3X3区域包含多个相同数字的板。
下面是我生成电路板的代码:

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;
}

看起来is_safe可能有问题,但是每个区域有多个数字意味着数字最初混合的方式有问题。我四处看了看,但没有发现任何异常(尽管我可能是盲人)。有人能帮我找出我在这里做错了什么吗?

kokeuurv

kokeuurv1#

就像@harold说的,解决方法是在我的代码中使用包含操作符,在我的主文件中仍然有一些错误需要修复,但是这个特定的问题已经解决了,所以我将结束这个问题。

相关问题