Sudoku Solver using bitmasks and bit-manipulation with Rust 🦀 and egui 🎨

Overview

sudoku-solver

Download

sudoku gif

This Rust application implements a very memory efficent algorithm to solve sudoku and lets the user know when a unique solution does not exist.

Algorithm

Source

I create an enum that holds my result type so I can tell the user what went wrong or if it successfully solved the puzzle.

pub enum SolveResult {
    Unique,
    NotUnique,
    Invalid,
}

I create 3 bitfields that I use to store the numbers that a row, column, or box contains

pub fn solve_grid(grid: &mut Vec<Vec<Square>>) -> SolveResult {
    // These are the bit fields that keep track of the numbers placed in each row, column, and box of the grid
    let mut row: u128 = 0;
    let mut col: u128 = 0;
    let mut boxes: u128 = 0;

    for r in 0..9 {
        for c in 0..9 {
            if !grid[r][c].value.is_empty() {

key is calculated by left-shifting the binary value of 1 by a value between 0 and 8, depending on the digit in the cell

            let key = 1 << grid[r][c].value.chars().next().unwrap() as usize - '1' as usize;

key is then used to update the corresponding bit in the bit fields

Example:

If key is 000001000 then we have the 6th bit and we will shift it r * 9 times and then use the OR bitwise operator to set that bit in row

                row |= key << r * 9;
                col |= key << c * 9;
                boxes |= key << (r / 3 * 3 + c / 3) * 9;
            }
        }
    }
   
    let mut count = 0;
    let old_grid = grid.clone();

    // We keep a solved_grid because we make sure that there is not a 2nd solution to the puzzle
    // If another solution doesn't exits then we set the grid equal to the solved_grid
    let mut solved_grid: Vec<Vec<Square>> = Vec::new();

    // Call the solving method recursively
    solve(&mut solved_grid, grid, &mut row, &mut col, &mut boxes, 0, &mut count);

    match count.cmp(&1) {
        Ordering::Equal => {
            *grid = solved_grid;
            SolveResult::Unique
        },
        Ordering::Greater => {
            *grid = old_grid;
            SolveResult::NotUnique
        }
        Ordering::Less => {
            *grid = old_grid;
            SolveResult::Invalid
        }
    }
}

fn solve(
    solved_grid: &mut Vec<Vec<Square>>, 
    grid: &mut Vec<Vec<Square>>,
    row: &mut u128,
    col: &mut u128,
    boxes: &mut u128,
    i: usize,
    count: &mut i32,
) -> bool {
    // If there is multiple solutions then automatically return true
    if *count > 1 {
        return true;
    }

    // If reached the end
    if i == 81 {
        // We need to save the grid in the case that we do not find another solution to the puzzle
        if *count == 0 {
            *solved_grid = grid.clone();
        }

        *count += 1;
        return false;
    }

Since we have a total sum, i, we use it to get the row, column, and later on, the box

    // Get the index of the row and column
    let (r, c) = (i / 9, i % 9);

    // If the cell is not empty then move to the next cell
    if !grid[r][c].value.is_empty() {
        return solve(solved_grid, grid, row, col, boxes, i + 1, count);
    }

    // Box index
    let b = (r / 3) * 3 + (c / 3);

mask is a bit mask that represents the numbers that are already present

We shift to the right to align each bits with the corresponding row, column, and box

    let mask = (*row >> r * 9) | (*col >> c * 9) | (*boxes >> b * 9);

We loop through each possible number

Using xmask we check to make sure that the bit has not been set in the row, column, or box.

If it equals 0 then we know that we can start trying to solve for that specific cell

    for x in 0..9 {
        let xmask = 1 << x;
        if mask & xmask != 0 {
            continue;
        }

Using the same concept from setting up row, col, and boxes we update the xth bit so we can begin to test

        // We update the bit at the current x value using xmask
        *row |= xmask << r * 9;
        *col |= xmask << c * 9;
        *boxes |= xmask << b * 9;

        // Since its 0-8 then we do x+1
        grid[r][c].value = std::char::from_digit(x + 1, 10).unwrap().to_string();
        grid[r][c].solved_cell = true;
        // Recursively call itself with the next cell to check if the value works
        if solve(solved_grid, grid, row, col, boxes, i + 1, count) {
            return true;
        }

If the value did not work then we undo the changes we made to the xth bit

        // If it didnt work then we reset the changes we did to the bit fields
        *row ^= xmask << r * 9;
        *col ^= xmask << c * 9;
        *boxes ^= xmask << b * 9;

        grid[r][c].value = String::new();
        grid[r][c].solved_cell = false;
    }
    
    false
}
You might also like...
Advent of Code 2021, also an attempt to practice a bit of Rust.

Advent of Code 2021 Advent of Code 2021 (my first one!), also an attempt to practice a bit of Rust. Running (Assuming that the respective inputs are i

An Intel HAXM powered, protected mode, 32 bit, hypervisor addition calculator, written in Rust.

HyperCalc An Intel HAXM powered, protected mode, 32 bit, hypervisor addition calculator, written in Rust. Purpose None 😏 . Mostly just to learn Rust

Fast conversion between linear float and 8-bit sRGB

fast-srgb8 Small crate implementing fast conversion between linear float and 8-bit sRGB. Includes API for performing 4 simultaneous conversions, which

CIEBII - Check if every bit is intact
CIEBII - Check if every bit is intact

CIEBII Checks If Every Byte Is Intact CIEBII is an image file format that checks if every single byte is intact. What does it do if it finds that a by

Stockbook embeds 1-bit raster images in your code at compile time

stockbook Stockbook embeds 1-bit raster images in your code at compile time. Designed primarily for #![no_std] usage, in embedded or other program-mem

A micro crate that simplifies a bit the use of the std macro thread_local!.

with-thread-local A micro crate that simplifies a bit the use of the std macro thread_local!. extern crate regex; use with_thread_local::with_thread_

Work to enable a Classic Mac (24-bit 68000) with ~16MB of RAM.

Apple SE FDHD ROM analysis In order to build a Mac clone that doesn't fully emulate the hardware (which is possible because the ROM abstracts hardware

A tiling layout engine for egui with drag-and-drop and resizing
A tiling layout engine for egui with drag-and-drop and resizing

egui_tiles Layouting and docking for egui. Supports: Horizontal and vertical layouts Grid layouts Tabs Drag-and-drop docking Trying it cargo r --examp

A fast nostr opengraph server, built on nostrdb and egui.
A fast nostr opengraph server, built on nostrdb and egui.

notecrumbs A nostr opengraph server build on nostrdb, egui, and skia. It renders notes using the CPU in around 50ms. Status WIP! Local note fetching w

Comments
  • Fix Clippy warnings

    Fix Clippy warnings

    Right now Clippy is pretty unhappy with this code. Most of these warnings are redundant or picky, but all of them could be easily be cleaned up or disabled: there doesn't appear to be anything too tricky there.

    opened by BartMassey 2
  • Separate the theme configuration from `update()`

    Separate the theme configuration from `update()`

    Right now set_theme() is being called on each frame in the update() loop. Would be better to do this only when the them is initially / subsequently set.

    opened by BartMassey 1
  • Attempt to solve puzzles requiring guessing

    Attempt to solve puzzles requiring guessing

    This is a big ask, but ideally the solver would give the puzzle a try even if it was incomplete. There are constraint-based algorithms that are floating around that do a reasonable job of solving underconstrained puzzles quickly.

    opened by BartMassey 1
  • Input puzzles in some standard format

    Input puzzles in some standard format

    It would be great to be able to load a puzzle in standard format to play with. Here is a list of some standard formats, most any of which would be fine: https://sudopedia.sudocue.net/index.php/Sudoku_Clipboard_and_File_Formats

    opened by BartMassey 0
Releases(1.0.0)
Owner
cameron
software engineer
cameron
A bit like tee, a bit like script, but all with a fake tty. Lets you remote control and watch a process

teetty teetty is a wrapper binary to execute a command in a pty while providing remote control facilities. This allows logging the stdout of a process

Armin Ronacher 259 Jan 3, 2023
This CLI utility facilitates effortless manipulation and exploration of TOML, YAML, JSON and RON files.

???????? This CLI utility facilitates effortless manipulation and exploration of TOML, YAML, JSON and RON files.

Moe 3 Apr 26, 2023
A library that allows for the arbitrary inspection and manipulation of the memory and code of a process on a Linux system.

raminspect raminspect is a crate that allows for the inspection and manipulation of the memory and code of a running process on a Linux system. It pro

Liam Germain 24 Sep 26, 2023
Fast DNA manipulation for Python, written in Rust.

quickdna Quickdna is a simple, fast library for working with DNA sequences. It is up to 100x faster than Biopython for some translation tasks, in part

Secure DNA 22 Dec 31, 2022
Provide types for angle manipulation in rust.

angulus Provides types for angle manipulation. Features serde : Serialization/deserialization support via serde. Example use angulus::{*, units::*};

Tristan Guichaoua 2 Sep 2, 2022
PNG manipulation library.

pngmanip A simple rust library for parsing and manipulating PNG images, primarily at the chunk level. The intended use case was for solving PNG based

Sam Leonard 1 Jan 7, 2022
Red-blue graph problem solver - Rust implementation

Red-blue graph problem solver - Rust implementation The problem is the following: In a directed graph, each node is colored either red or blue. Furthe

Thomas Prévost 2 Jan 17, 2022
🧮 Writing an Equation Solver

Writing an Equation Solver Writing an Equation Solver is a process that is made of: parsing, equating/unifying and rewriting. Equating: it's the step

Gabrielle Guimarães de Oliveira 16 Aug 7, 2023
An optimizing IK solver based on the Lie group of rigid transforms SE(3)

OptIK A fast inverse kinematics solver for arbitrary serial chains, providing Rust and Python programming interfaces. The implementation is similar to

Kyle Cesare 17 Oct 5, 2023
Bit fields and masks for rust!

ubits Bit fields and masks for rust! Provides a macro for generating bit field types complete with flags and some helpful trait implementations. Suppo

Adam Romano 2 Sep 16, 2022