# Rust based Sudoku solver using backtracking

I've just started learning rust and have written a basic sudoku solver, however it seems to run much slower than I expected. So I'm looking for any possible performance improvements as well as any other general feedback.

fn main() {
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],
];
solve_sudoku(initial_grid);
}

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!();
}
}

## 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();
});
}