Goal
The goal is to optimize the program. I won't change the backtracking algorithm.
General feedback
Your code is good, but you should use structs and impls in this program, instead of passing grid: [[i8; 9]; 9] around. I show this in code below.
Idea
You check cell vacancy with many loops that check multiple cells. How about we kill many birds with one stone? That is, we can use small bitsets and bit operations to do work of a loop in one go.
Result
The gain is speed improvement by a factor of 150x.
test bench ... bench: 125,889,703 ns/iter (+/- 12,948,648)
test bench ... bench: 857,542 ns/iter (+/- 84,678)
Code
#![feature(test)]
extern crate test;
use test::Bencher;
fn sudoku() {
let initial_grid: Grid = Grid::new([
[0, 4, 3, 0, 0, 0, 0, 0, 9],
[0, 0, 0, 6, 0, 0, 0, 0, 5],
[0, 0, 0, 0, 0, 4, 1, 0, 0],
[9, 0, 1, 0, 5, 0, 0, 0, 0],
[0, 0, 0, 7, 2, 6, 0, 0, 0],
[0, 0, 8, 0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 7, 2, 0],
[7, 0, 0, 0, 0, 0, 0, 0, 0],
[2, 0, 0, 0, 0, 5, 0, 6, 0],
]);
let initial_grid = ::test::black_box(initial_grid);
let result = initial_grid.solve_sudoku();
::test::black_box(result);
}
const ALL_EMPTY: u16 = 0b111_111_111_0;
#[derive(Copy, Clone)]
struct Grid {
grid: [[i8; 9]; 9],
rows: [u16; 9],
cols: [u16; 9],
boxes: [[u16; 3]; 3],
}
impl Grid {
fn new(grid: [[i8; 9]; 9]) -> Self {
let mut result = Grid {
grid,
rows: [ALL_EMPTY; 9],
cols: [ALL_EMPTY; 9],
boxes: [[ALL_EMPTY; 3]; 3],
};
for row in 0..9 {
for col in 0..9 {
if result.grid[row][col] != 0 {
result.set_occupied(row, col, result.grid[row][col]);
}
}
}
result
}
fn set_occupied(&mut self, row: usize, col: usize, val: i8) {
self.grid[row][col] = val;
self.rows[row] &= !(1 << val as u8);
self.cols[col] &= !(1 << val as u8);
self.boxes[row / 3][col / 3] &= !(1 << val as u8);
}
fn set_vacant(&mut self, row: usize, col: usize) {
let val = self.grid[row][col];
self.rows[row] |= 1 << val as u8;
self.cols[col] |= 1 << val as u8;
self.boxes[row / 3][col / 3] |= 1 << val as u8;
self.grid[row][col] = 0;
}
fn find_empty(&self) -> (usize, usize) {
for row in 0..9 {
for col in 0..9 {
if self.grid[row][col] == 0 {
return (row, col)
}
}
}
print!("Done");
return (9,9)
}
fn solve_sudoku(mut self) -> bool {
let l: (usize, usize) = self.find_empty();
if l == (9, 9) {
self.print();
return true
}
for i in 1..10 {
if self.is_location_safe(l.0, l.1, i) {
self.set_occupied(l.0, l.1, i);
if self.solve_sudoku() {
return true;
}
self.set_vacant(l.0, l.1);
}
}
return false
}
fn is_location_safe(&self, row: usize, col: usize, num: i8) -> bool {
let box_vacancy = self.boxes[row / 3][col / 3];
let row_vacancy = self.rows[row];
let col_vacancy = self.cols[col];
box_vacancy & row_vacancy & col_vacancy & (1 << num as u8) != 0
}
fn print(&self) {
println!();
for row in self.grid {
for item in row {
print!("{:?} ", item);
}
println!();
}
}
}
#[bench]
fn bench(b: &mut Bencher) {
b.iter(|| {
sudoku();
});
}
#[test]
fn test_sudoku() {
sudoku();
}
Previous code (benched)
#![feature(test)]
extern crate test;
use test::Bencher;
fn sudoku() {
let initial_grid: [[i8; 9]; 9] = [
[0, 4, 3, 0, 0, 0, 0, 0, 9],
[0, 0, 0, 6, 0, 0, 0, 0, 5],
[0, 0, 0, 0, 0, 4, 1, 0, 0],
[9, 0, 1, 0, 5, 0, 0, 0, 0],
[0, 0, 0, 7, 2, 6, 0, 0, 0],
[0, 0, 8, 0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 7, 2, 0],
[7, 0, 0, 0, 0, 0, 0, 0, 0],
[2, 0, 0, 0, 0, 5, 0, 6, 0],
];
let result = solve_sudoku(::test::black_box(initial_grid));
::test::black_box(result);
}
fn find_empty(grid: [[i8; 9]; 9]) -> (usize, usize){
for row in 0..9{
for col in 0..9 {
if grid[row][col] == 0 {
return (row, col)
}
}
}
print!("Done");
return (9,9)
}
fn solve_sudoku(mut grid: [[i8; 9]; 9]) -> bool{
let l: (usize, usize) = find_empty(grid);
if l == (9, 9) {
print_grid(grid);
return true
}
for i in 1..10 {
if is_location_safe(grid, l.0, l.1, i) {
grid[l.0][l.1] = i;
if solve_sudoku(grid) {
return true;
}
grid[l.0][l.1] = 0;
}
}
return false
}
fn is_location_safe(grid: [[i8; 9]; 9], row: usize, col: usize, num: i8) -> bool {
return !used_in_col(grid, col, num) & !used_in_row(grid, row, num) & !used_in_box(grid, row, col, num)
}
fn used_in_box(grid: [[i8; 9]; 9], row: usize, col: usize, num: i8) -> bool {
let first_cell_row = row - (row%3);
let first_cell_column = col - (col%3);
for i in 0..3 {
for j in 0..3{
if grid[i+first_cell_row][j+first_cell_column] == num {
return true
}
}
}
return false
}
fn used_in_col(grid: [[i8; 9]; 9], col: usize, num: i8) -> bool {
for i in 0..8 {
if grid[i][col] == num {
return true;
}
}
return false;
}
fn used_in_row(grid: [[i8; 9]; 9], row: usize, num: i8) -> bool{
for i in grid[row] {
if i == num {
return true;
}
}
return false
}
fn print_grid(grid: [[i8; 9]; 9]) {
println!();
for row in grid {
for item in row{
print!("{:?} ", item);
}
println!();
}
}
#[bench]
fn bench(b: &mut Bencher) {
b.iter(|| {
sudoku();
});
}
