Простые судоку решатель в Русте


Это мой маленький судоку решатель в Русте. Он перебирает пустые ячейки и проверяет, какие цифры отсутствуют в соответствующую строку, столбец и Квадрат. Если есть еще один возможный кандидат, он заполняет в ответ и переходит к следующей пустой ячейке.

Очевидно, я должен читать из входного, а не жесткого кодирования головоломки. Какими еще способами я могу улучшить читабельность и сделать его более устойчивым?

type Cell = (usize, usize);

struct Grid {
    data: [[u8; 9]; 9],
    current: Cell,
}

impl Grid {
    // Search possible candidates for a given cell.
    // If one candidate exists, return it.
    fn check(&mut self, cell: Cell) -> Option<u8> {  
        let mut candidates = [true; 9];
        for i in 1..10 {
            candidates[i-1] &= self.check_row(cell, i as u8);
            candidates[i-1] &= self.check_column(cell, i as u8);
            candidates[i-1] &= self.check_square(cell, i as u8);
        }

        if candidates.iter().fold(0, |acc, &x| acc + x as i32) == 1 {
            return Some(candidates.iter()
                                  .position(|&x| x == true)
                                  .unwrap() as u8 + 1);
        }
        None
    }
    fn check_row(&self, cell: Cell, num: u8) -> bool {
        let row = self.data[cell.0];
        for i in row.iter() {
            if *i == num { return false; }
        }
        true
    }
    fn check_column(&self, cell: Cell, num: u8) -> bool {
        for row in self.data.iter() {
            if row[cell.1] == num { return false; }
        }
        true
    }
    fn check_square(&self, cell: Cell, num: u8) -> bool {
        let mut square: (usize, usize) = (cell.0 / 3, cell.1 / 3);

        square.0 *= 3;
        square.1 *= 3;

        for row in (square.0)..(square.0 + 3) {
            for column in (square.1)..(square.1 + 3) {
                if self.data[row][column] == num { return false; }
            }
        }
        true
    }
}

// Iterate through empty cells.
impl Iterator for Grid {
    type Item = Cell;

    fn next(&mut self) -> Option<Self::Item> {
        let starting_point = (self.current.0, self.current.1);
        loop {
            self.current.0 = (self.current.0 + 1)%9;
            if self.current.0 == 0 {
                self.current.1 = (self.current.1 + 1)%9;
            }
            if (self.current.0, self.current.1) == starting_point {
                return None;
            }
            if self.data[self.current.0][self.current.1] == 0 { break }
        }
        Some(self.current)
    }
}


fn main () {
    let mut grid = Grid {
        data: [ [1,6,4,0,0,0,0,0,2],
                [2,0,0,4,0,3,9,1,0],
                [0,0,5,0,8,0,4,0,7],
                [0,9,0,0,0,6,5,0,0],
                [5,0,0,1,0,2,0,0,8],
                [0,0,8,9,0,0,0,3,0],
                [8,0,9,0,4,0,2,0,0],
                [0,7,3,5,0,9,0,0,1],
                [4,0,0,0,0,0,6,7,9] ],
        current: (0, 0),
    };

    loop {
        if let None = grid.next() { break; }
        let empty_cell = grid.current;
        match grid.check(empty_cell) {
            Some(i) => {
                grid.data[empty_cell.0][empty_cell.1] = i;
            },
            None => continue,
        }
    }

    for row in grid.data.iter() {
        println!("{:?}", row);
    }
}


244
5
задан 29 января 2018 в 01:01 Источник Поделиться
Комментарии
1 ответ

Общие


  1. Запустить скрепка. Она будет автоматически скажет вам такие вещи, как:


    • проверка равенства по отношению к истинной ненужны

        --> src/main.rs:20:57
      |
      20 | return Some(candidates.iter().position(|&x| x == true).unwrap() as u8 + 1);
      | ^^^^^^^^^

    • это более идиоматические для перебора ссылок на контейнеры вместо использования явных методов итерации

        --> src/main.rs:26:18
      |
      26 | for i in row.iter() {
      | ^^^^^^^^^^ help: to write this more concisely, try: `&row`

    • избыточные шаблону, рассмотрите возможность использования is_none()

        --> src/main.rs:97:16
      |
      97 | if let None = grid.next() {
      | -------^^^^-------------- help: try this: `if grid.next().is_none()`


  2. Cell - это имя типа в стандартной библиотеке, так что я был немного смущен, чтобы начать с. Не уверена, что лучшего названия.

main


  1. Использовать while или while let вместо loop.

  2. В continue не полезно, это в конце блока. Перейти к if let вместо.

  3. Почему не возвращают стоимость вашего использовать итератор? Почему бы вам не использовать это вместо того, чтобы grid.current?

  4. Почему grid.current даже части сети в первую очередь?

Grid


  1. Если вы хотите, чтобы документировать функции, использовать ///не //.

  2. Не бросайте логические значения в виде числа. Я честно удивлен, это даже компилируется. Вместо этого, граф истинные ценности

  3. Запомнить все доступные методы итераторов. В этом случае any и all являются ценными.

Grid::check_square


  1. Нет необходимости указывать тип square.

  2. Я не думаю, что это полезно впихнуть square данные в кортеже. Вместо этого, расшевелить немного закрытия, чтобы выполнить ту же работу.

  3. Мне нравится модуле itertools. Здесь, я использую его cartesian_product.

extern crate itertools;

use itertools::Itertools;

type Cell = (usize, usize);

struct Grid {
data: [[u8; 9]; 9],
current: Cell,
}

impl Grid {
/// Search possible candidates for a given cell.
/// If one candidate exists, return it.
fn check(&mut self, cell: Cell) -> Option<u8> {
let mut candidates = [true; 9];
for i in 1..10 {
candidates[i - 1] &= self.check_row(cell, i as u8);
candidates[i - 1] &= self.check_column(cell, i as u8);
candidates[i - 1] &= self.check_square(cell, i as u8);
}

if candidates.iter().filter(|&&x| x).count() == 1 {
return Some(candidates.iter().position(|&x| x).unwrap() as u8 + 1);
}
None
}

fn check_row(&self, cell: Cell, num: u8) -> bool {
self.data[cell.0].iter().all(|&i| i != num)
}

fn check_column(&self, cell: Cell, num: u8) -> bool {
self.data.iter().all(|row| row[cell.1] != num)
}

fn check_square(&self, cell: Cell, num: u8) -> bool {
let truncated_range_of_3 = |x| {
let start = (x / 3) * 3;
start..start + 3
};

let rows = truncated_range_of_3(cell.0);
let cols = truncated_range_of_3(cell.1);

rows.cartesian_product(cols).all(|(row, col)| self.data[row][col] != num)
}
}

/// Iterate through empty cells.
impl Iterator for Grid {
type Item = Cell;

fn next(&mut self) -> Option<Self::Item> {
let starting_point = (self.current.0, self.current.1);
loop {
self.current.0 = (self.current.0 + 1) % 9;
if self.current.0 == 0 {
self.current.1 = (self.current.1 + 1) % 9;
}
if (self.current.0, self.current.1) == starting_point {
return None;
}
if self.data[self.current.0][self.current.1] == 0 {
break;
}
}
Some(self.current)
}
}

fn main() {
let mut grid = Grid {
data: [
[1, 6, 4, 0, 0, 0, 0, 0, 2],
[2, 0, 0, 4, 0, 3, 9, 1, 0],
[0, 0, 5, 0, 8, 0, 4, 0, 7],
[0, 9, 0, 0, 0, 6, 5, 0, 0],
[5, 0, 0, 1, 0, 2, 0, 0, 8],
[0, 0, 8, 9, 0, 0, 0, 3, 0],
[8, 0, 9, 0, 4, 0, 2, 0, 0],
[0, 7, 3, 5, 0, 9, 0, 0, 1],
[4, 0, 0, 0, 0, 0, 6, 7, 9],
],
current: (0, 0),
};

while let Some(_) = grid.next() {
let empty_cell = grid.current;

if let Some(i) = grid.check(empty_cell) {
grid.data[empty_cell.0][empty_cell.1] = i;
}
}

for row in &grid.data {
println!("{:?}", row);
}
}

Что unwrap беспокоит меня, но я не уверен, что это действительно яснее:

let mut x = candidates.iter().enumerate().filter_map(|(pos, &check)| {
if check { Some(pos as u8 + 1) } else { None }
}).fuse();

match (x.next(), x.next()) {
(Some(pos), None) => Some(pos),
_ => None,
}

Его можно сделать намного лучше, отказавшись от выбора вообще. Это экономит (чуть-чуть) стекового пространства, но и, вероятно, ускоряет программе (небольшое количество) — функция выходов, как только нашел вторую возможность:

fn check(&mut self, cell: Cell) -> Option<u8> {
let mut possibilities = (1..10)
.filter(|&i| self.check_row(cell, i))
.filter(|&i| self.check_column(cell, i))
.filter(|&i| self.check_square(cell, i))
.fuse();

match (possibilities.next(), possibilities.next()) {
(Some(pos), None) => Some(pos),
_ => None,
}
}

Хорошие новости! Моя версия код проходит каждый тестовый случай вам обеспечен!

3
ответ дан 3 февраля 2018 в 03:02 Источник Поделиться