QSolve

A command line tool and library for solving Queens puzzles

This command line tool and library is designed to solve Queens puzzles, with a few key characteristics:

• Human-understandable: Humans solve queens by iteratively eliminating and confirming squares. This library does the same process; it doesn't use and do any sort of search-algorithms to try and find the solution from afar.
• Fast: Within the bounds of the above, it tries to be as fast as possible. This means, for example, it uses bitfields rather than HashSets for efficient operations on small sets.
• Tested: While tracing code and error recovery means this library doesn't have 100% code coverage, it aspires to be as well-tested as possible. If cargo test passes, then we should be confident things work.
• Documented: The qsolve binary should have clear documentation available with --help for every subcommand. The qsolve library should have clear documentation (including doctests) for all public functionality.

Installation

qsolve can be installed from crates.io by running

cargo install qsolve

Alternately, the binary can be downloaded directly from Github releases.

Command line example

Basic usage of the command line tool looks something like this:

qsolve solve games/linkedin-1-empty.txt --share

which yields the following screenshot (throughout this README, screenshots will be used since the command line tool relies heavily on ANSI color strings to output Queens boards):

More compelling, though, is the animate subcommand, which doesn't just solve the puzzle, but walks you through the solution step by step.

li1-animate-delay.mov

Library Example

Basic usage of the library looks something like this:

use std::path::PathBuf;
use qsolve::heuristic::all_heuristics;
use qsolve::file::QueensFile;
use qsolve::solveiter::solve_iter;
use qsolve::solvestate::{SolveState, SolveStrategy};

fn solve() -> Result<(), Box<dyn std::error::Error>> {
    // Parse a text file containing a Queens puzzle.
    let queens_file = QueensFile::try_from_text_file(&PathBuf::from("games/linkedin-1-empty.txt"))?;

    // Generate the initial solve state and print it.
    let solve_state = SolveState::from(&queens_file);
    println!("{}", solve_state);

    // Generate the list of heuristics to use to solve the puzzle.
    let heuristics = all_heuristics(solve_state.board);

    // Solve the puzzle and print out the solution.
    let solved = solve_iter(solve_state, SolveStrategy::Fast, &heuristics).last().unwrap().solve_state;
    println!("{}", solved);

    Ok(())
}

Development

qsolve is a side project, so development will happen in a pretty ad-hoc basis (and issues and PRs might go unanswered: caveat emptor). However, if you wish to fork or contribute back, here's a quick runthrough:

This repository contains both qsolve the binary and qsolve the library it depends on. The only logic in the binary is command line logic; all actual functionality should live in the library.

There are moderately comprehensive integration, unit and doctests that can be run with cargo test. Additionally, there are a few benchmarks using the criterion benchmark engine that can be run with cargo bench. In general, changes should be neutral or positive in that benchmark (for example, a change to use the bitvec package to implement the data structures in src/datastructure.rs was abandoned because cargo bench showed it was a regression).