Rohan's blog
Solving Sudoku Puzzles with Rust

Solving Sudoku Puzzles with Rust

Rohan's photo
Rohan
·

4 min read

Sudoku puzzles are an excellent exercise for both logic and programming skills. In this blog post, I'll walk you through how to create a Sudoku solver in Rust, a powerful and efficient systems programming language. By the end of this guide, you'll have a deeper understanding of Rust's syntax and how to apply it to solve complex problems like Sudoku.

Introduction

Sudoku is a popular logic-based puzzle game where the goal is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids contain all of the digits from 1 to 9. Solving Sudoku puzzles programmatically involves using techniques like backtracking and constraint satisfaction to find a valid solution.

Setting Up the Environment

Before diving into the code, make sure you have Rust installed on your system. You can install Rust by following the instructions on the official Rust website.

Understanding the Code

use std::process;

fn display(matrix: &Vec<Vec<i32>>) {
    for i in 0..matrix.len() {
        if i != 0 && i % 3 == 0 {
            println!("---------------------");
        }
        for j in 0..matrix[0].len() {
            if j != 0 && j % 3 == 0 {
                print!("|");
            }
            print!("{} ", matrix[i][j]);
        }
        println!();
    }
}

fn is_safe_place(matrix: &Vec<Vec<i32>>, row: usize, col: usize, data: i32) -> bool {
    for i in 0..9 {
        if matrix[i][col] == data {
            return false;
        }
        if matrix[row][i] == data {
            return false;
        }
    }
    let nrow = (row / 3) * 3;
    let ncol = (col / 3) * 3;
    for i in 0..3 {
        for j in 0..3 {
            if matrix[nrow + i][ncol + j] == data {
                return false;
            }
        }
    }
    true
}

fn sudoku(matrix: &mut Vec<Vec<i32>>, idx: usize) {
    if idx == 81 {
        display(matrix);
        process::exit(200);
    }

    let row = idx / 9;
    let col = idx % 9;
    if matrix[row][col] == 0 {
        for i in 1..=9 {
            if is_safe_place(matrix, row, col, i) {
                matrix[row][col] = i;
                sudoku(matrix, idx + 1);
                matrix[row][col] = 0;
            }
        }
    } else {
        sudoku(matrix, idx + 1);
    }
}

fn main() {
    // The World's hardest Sudoku Puzzle
    let mut matrix = vec![
        vec![1, 0, 0, 0, 0, 7, 0, 9, 0],
        vec![0, 3, 0, 0, 2, 0, 0, 0, 8],
        vec![0, 0, 9, 6, 0, 0, 5, 0, 0],
        vec![0, 0, 5, 3, 0, 0, 9, 0, 0],
        vec![0, 1, 0, 0, 8, 0, 0, 0, 2],
        vec![6, 0, 0, 0, 0, 4, 0, 0, 0],
        vec![3, 0, 0, 0, 0, 0, 0, 1, 0],
        vec![0, 4, 0, 0, 0, 0, 0, 0, 7],
        vec![0, 0, 7, 0, 0, 0, 3, 0, 0],
    ];
    display(&matrix);
    println!("OutPut =>");
    sudoku(&mut matrix, 0);
}

Let's break down the Rust code for solving Sudoku puzzles step by step:

  1. display(matrix): This function prints the Sudoku grid to the console, making it easier to visualise the puzzle.

  2. is_safe_place(matrix, row, col, data): This function checks if it's safe to place a given digit (data) at a specific position (row, col) in the Sudoku grid (matrix). It verifies whether the digit already exists in the same row, column, or 3x3 subgrid.

  3. sudoku(matrix, idx): This is the main recursive function that implements the Sudoku solving algorithm using backtracking. It tries different digits at each empty cell until a valid solution is found.

  4. main(): In the main function, we define the Sudoku puzzle grid and call the display function to print the initial state of the puzzle. Then, we invoke the sudoku function to solve the puzzle.

Running the Code

After understanding the code, save it to a Rust source file (e.g., sudoku_solver.rs). Compile and run the code using the following commands:

$ cargo run

You'll see the initial Sudoku puzzle grid printed to the console, followed by the solved puzzle.

Conclusion

In this blog post, we've explored how to create a Sudoku solver in Rust. By leveraging Rust's powerful features like pattern matching, recursion, and mutability control, we've implemented an efficient algorithm to solve Sudoku puzzles programmatically. Feel free to experiment with the code and adapt it to solve other logic-based puzzles or optimisation problems.

Stay tuned for more Rust programming tutorials and happy coding!

Github Repository: https://github.com/rohanchauhan02/suduko_solver

RustDSA