Dancing Links (“dlx”) solver for the exact cover problem, written in Rust. Can be used to create a sudoku solver.

Overview

Dancing Links “dlx”

Dancing Links solver for “algorithm X” by Knuth

This solver solves the exact cover problem using “algorithm X”, implemented using Dancing Links (“Dlx”). The most common example problem solved by an exact cover solver is sudokus, and that's included here too.

The Dlx data structure structure corresponds to a sparse binary matrix and it uses two-dimensional doubly linked and circular lists.

See Knuth for papers about this structure and about “algorithm X”.

Node layout in DLX:

           ..    ..    ..
           ||    ||    ||
:> Head <> C1 <> C2 <> C3 <> ... <:    (Head and column heads)
           ||    ||    ||
        :> R1  <    >  R2  <       ..  (Row items)
           ||    ||          ||
              :> R3  <    >  R4  < ..
                 ||          ||
                 ..          ..

  etc.
  where || are a Up/Down links and <> Prev/Next links.

Head is only linked to the column row. Note that R1 links directly to R2 and so on, the matrix is sparse.

The lists are doubly linked and circular, in two dimensions: Prev, Next and Up, Down.

Building

Using stable Rust, at least version Rust 1.53

Running

You can try this, to build and run the sudoku solver that uses dancing links:

cargo build
cargo run < examples/hard_sudoku.txt

License

dlx and sudoku crates for Rust Copyright (C) 2021 Ulrik Sverdrup "bluss"

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see <https://www.gnu.org/licenses/>.

You might also like...
minimalistic command launcher in rust
minimalistic command launcher in rust

rrun Note: Apart from the occasional fix, this project is not actively developed anymore. rrun works fine and should run/compile for the time being on

Yet another fancy watcher. (Rust)

funzzy Yet another fancy watcher. (Inspired by antr / entr) Configure execution of different commands using semantic yaml. # .watch.yaml # list here a

A more intuitive version of du in rust
A more intuitive version of du in rust

Dust du + rust = dust. Like du but more intuitive. Why Because I want an easy way to see where my disk is being used. Demo Install Cargo cargo install

Fuzzy Finder in rust!
Fuzzy Finder in rust!

Life is short, skim! Half of our life is spent on navigation: files, lines, commands… You need skim! It is a general fuzzy finder that saves you time.

A library to listen to global hotkeys in Rust

Rust Hotkey A library to listen to global hotkeys in Rust How to use See the examples folder for how to use this library. OS Support This lib aims to

🔮 Futuristic take on hexdump, made in Rust.
🔮 Futuristic take on hexdump, made in Rust.

hex (hx) Futuristic take on hexdump. hx accepts a file path as input and outputs a hexadecimal colorized view to stdout. $ hx tests/files/alphanumeric

Cross-platform Rust rewrite of the GNU coreutils

uutils coreutils uutils is an attempt at writing universal (as in cross-platform) CLI utilities in Rust. This repository is intended to aggregate GNU

A rust layered configuration loader with zero-boilerplate configuration management.

salak A layered configuration loader with zero-boilerplate configuration management. About Features Placeholder Key Convension Cargo Features Default

Untrusted IPC with maximum performance and minimum latency. On Rust, on Linux.

Untrusted IPC with maximum performance and minimum latency. On Rust, on Linux. When is this Rust crate useful? Performance or latency is crucial, and

Owner
bluss
bluss
A tool for quickly switching between different file configurations, using symbolic links.

config-loader A tool for quickly switching between different file configurations, using symbolic links. Usage To use it, download the latest release f

Zacchary Dempsey-Plante 3 Aug 22, 2022
A modern replacement for ps written in Rust

procs procs is a replacement for ps written in Rust. Documentation quick links Features Platform Installation Usage Configuration Features Output by t

null 3.6k Jan 5, 2023
Blazing 💥 fast terminal-ui for git written in rust 🦀

Blazing fast terminal client for git written in Rust Features Fast and intuitive keyboard only control Context based help (no need to memorize tons of

Stephan Dilly 11.8k Jan 5, 2023
A simple and fast download accelerator, written in Rust

zou A simple and fast download accelerator, written in Rust Zou is a Snatch fork by @k0pernicus. Snatch is a fast and interruptable download accelerat

Antonin Carette 173 Dec 4, 2022
A bash-like Unix shell written in Rust

Cicada Unix Shell Cicada is a simple Unix shell written in Rust. Documents Install cicada Environment Variables Cicada Builtins Completion RC File His

Hugo Wang 921 Dec 28, 2022
Performs distributed command execution, written in Rust w/ Tokio

Concurr: Distributed and Concurrent Command Execution, in Rust This project is dual licensed under MIT and Apache 2.0. Originally inspired by the GNU

Michael Murphy 93 Dec 18, 2022
A TUI system monitor written in Rust

NO LONGER MAINTAINED. For a similar program, check out https://github.com/ClementTsang/bottom. ytop Another TUI based system monitor, this time in Rus

Caleb Bassi 2.1k Jan 3, 2023
A non-root version of traceroute written in Rust

tracepath-rs A non-root version of traceroute written in Rust for Linux.

Peter Malmgren 9 Dec 30, 2022
A system handler to get information and interact with processes written in Rust

A system handler to get information and interact with processes written in Rust

Guillaume Gomez 1.1k Jan 3, 2023
LeftHK - A hotkey daemon written in Rust

LeftHK LeftHK - A hotkey daemon written in Rust THIS IS BETA SOFTWARE The configuration file should be created in ~/.config/lefthk/ and called config.

null 15 Oct 12, 2022