puzzle-solver's Introduction

Puzzle Solver

About

Solve logic puzzles by simply describing the puzzle's rules as constraints. This is suitable for solving puzzles with integer variables such as Sudoku, Killer Sudoku, Kakuro, and Zebra puzzles.

The puzzle solver maintains a list of candidates for each puzzle variable. It solves puzzles by eliminating candidates that would lead to a contradiction and taking any forced moves that were exposed in the process. This is repeated until it gets stuck, whereupon it will perform a backtracking search -- it will assign a single variable and continue with the candidate elimination step again.

Examples

A few example programs are provided in the tests/ directory:

Hidato - https://en.wikipedia.org/wiki/Hidato
Kakuro - https://en.wikipedia.org/wiki/Kakuro
Killer Sudoku - https://en.wikipedia.org/wiki/Killer_sudoku
Magic Square - https://en.wikipedia.org/wiki/Magic_square
N-queens problem - https://en.wikipedia.org/wiki/Eight_queens_puzzle
Nonogram (Hanjie, Picross) - https://en.wikipedia.org/wiki/Nonogram
Send More Money - https://en.wikipedia.org/wiki/Verbal_arithmetic
Sudoku - https://en.wikipedia.org/wiki/Sudoku
- Samurai Sudoku
Sujiko - https://en.wikipedia.org/wiki/Sujiko
Takuzu (Binairo) - https://en.wikipedia.org/wiki/Takuzu
xkcd - https://xkcd.com/287/
Zebra puzzle (Einstein's riddle) - https://en.wikipedia.org/wiki/Zebra_Puzzle

To clone this repository, run:

git clone https://github.com/wangds/puzzle-solver.git

Then build the library and run the test programs using Cargo.

cargo test --test sudoku -- --nocapture

Basic Usage

We will demonstrate how to solve the equation "SEND + MORE = MONEY". Add Puzzle Solver as a dependency to your project's Cargo.toml:

[dependencies]
puzzle-solver = "0.4"

Import the library in your project, e.g.:

extern crate puzzle_solver;

use puzzle_solver::Puzzle;

First, we create a puzzle object and the 8 puzzle variables (S,E,N,D,M,O,R,Y).

let mut puzzle = Puzzle::new();
let vars = puzzle.new_vars_with_candidates_1d(8, &[0,1,2,3,4,5,6,7,8,9]);
let (s, e, n, d) = (vars[0], vars[1], vars[2], vars[3]);
let (m, o, r, y) = (vars[4], vars[5], vars[6], vars[7]);

All eight puzzle variables have been initialised to be any number between 0 and 9. However, we know that the numbers are not allowed to begin with zero, so we remove the choices of S = 0 and M = 0.

puzzle.remove_candidates(s, &[0]);
puzzle.remove_candidates(m, &[0]);

We add the constraint that the variables should be all different:

puzzle.all_different(&vars);

We write the equation as another puzzle constraint:

puzzle.equals(
    (1000 * s + 100 * e + 10 * n + d) + (1000 * m + 100 * o + 10 * r + e),
    10000 * m + 1000 * o + 100 * n + 10 * e + y);

And we solve!

let solution = puzzle.solve_any().expect("solution");
assert_eq!(solution[o], 0);
assert_eq!(solution[m], 1);
assert_eq!(solution[y], 2);
assert_eq!(solution[e], 5);
assert_eq!(solution[n], 6);
assert_eq!(solution[d], 7);
assert_eq!(solution[r], 8);
assert_eq!(solution[s], 9);

Documentation

Documentation.

Author

David Wang

puzzle-solver's People

Contributors

Stargazers

Watchers

puzzle-solver's Issues

Search space small for sendmoremoney

Using this test

macro_rules! make_word {
    ($arr:expr) => {
        $arr.iter()
            .rev()
            .enumerate()
            .fold(LinExpr::from(0), |sum, (x, y)| {
                sum + i32::pow(10, x as u32) * *y
            })
    };
}

#[test]
fn manyaddends() {
    let mut sys = Puzzle::new();
    let vars = sys.new_vars_with_candidates_1d(10, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    let e = vars[0];
    let a = vars[1];
    let l = vars[2];
    let r = vars[3];
    let s = vars[4];
    let f = vars[5];
    let o = vars[6];
    let i = vars[7];
    let h = vars[8];
    let t = vars[9];

    let a_ = make_word!([a]);
    let affiliates_ = make_word!([a, f, f, i, l, i, a, t, e, s]);
    let after_ = make_word!([a, f, t, e, r]);
    let alerts_ = make_word!([a, l, e, r, t, s]);
    let all_ = make_word!([a, l, l]);
    let arrest_ = make_word!([a, r, r, e, s, t]);
    let as_ = make_word!([a, s]);
    let assails_ = make_word!([a, s, s, a, i, l, s]);
    let assisters_ = make_word!([a, s, s, i, s, t, e, r, s]);
    let at_ = make_word!([a, t]);
    let falsifies_ = make_word!([f, a, l, s, i, f, i, e, s]);
    let far_ = make_word!([f, a, r]);
    let fast_ = make_word!([f, a, s, t]);
    let fasts_ = make_word!([f, a, s, t, s]);
    let fathers_ = make_word!([f, a, t, h, e, r, s]);
    let fears_ = make_word!([f, e, a, r, s]);
    let feasts_ = make_word!([f, e, a, s, t, s]);
    let fire_ = make_word!([f, i, r, e]);
    let fires_ = make_word!([f, i, r, e, s]);
    let first_ = make_word!([f, i, r, s, t]);
    let fish_ = make_word!([f, i, s, h]);
    let flee_ = make_word!([f, l, e, e]);
    let for_ = make_word!([f, o, r]);
    let foresee_ = make_word!([f, o, r, e, s, e, e]);
    let forest_ = make_word!([f, o, r, e, s, t]);
    let forfeits_ = make_word!([f, o, r, f, e, i, t, s]);
    let fortresses_ = make_word!([f, o, r, t, r, e, s, s, e, s]);
    let free_ = make_word!([f, r, e, e]);
    let harasses_ = make_word!([h, a, r, a, s, s, e, s]);
    let hate_ = make_word!([h, a, t, e]);
    let hear_ = make_word!([h, e, a, r]);
    let hears_ = make_word!([h, e, a, r, s]);
    let heart_ = make_word!([h, e, a, r, t]);
    let heat_ = make_word!([h, e, a, t]);
    let her_ = make_word!([h, e, r]);
    let histories_ = make_word!([h, i, s, t, o, r, i, e, s]);
    let hole_ = make_word!([h, o, l, e]);
    let hoof_ = make_word!([h, o, o, f]);
    let horrors_ = make_word!([h, o, r, r, o, r, s]);
    let horse_ = make_word!([h, o, r, s, e]);
    let horses_ = make_word!([h, o, r, s, e, s]);
    let hot_ = make_word!([h, o, t]);
    let i_ = make_word!([i]);
    let is_ = make_word!([i, s]);
    let it_ = make_word!([i, t]);
    let its_ = make_word!([i, t, s]);
    let last_ = make_word!([l, a, s, t]);
    let late_ = make_word!([l, a, t, e]);
    let least_ = make_word!([l, e, a, s, t]);
    let leathers_ = make_word!([l, e, a, t, h, e, r, s]);
    let lie_ = make_word!([l, i, e]);
    let life_ = make_word!([l, i, f, e]);
    let losses_ = make_word!([l, o, s, s, e, s]);
    let of_ = make_word!([o, f]);
    let off_ = make_word!([o, f, f]);
    let offer_ = make_word!([o, f, f, e, r]);
    let others_ = make_word!([o, t, h, e, r, s]);
    let raise_ = make_word!([r, a, i, s, e]);
    let resettle_ = make_word!([r, e, s, e, t, t, l, e]);
    let rest_ = make_word!([r, e, s, t]);
    let rests_ = make_word!([r, e, s, t, s]);
    let rise_ = make_word!([r, i, s, e]);
    let rises_ = make_word!([r, i, s, e, s]);
    let roles_ = make_word!([r, o, l, e, s]);
    let roofs_ = make_word!([r, o, o, f, s]);
    let safe_ = make_word!([s, a, f, e]);
    let satisfies_ = make_word!([s, a, t, i, s, f, i, e, s]);
    let share_ = make_word!([s, h, a, r, e]);
    let she_ = make_word!([s, h, e]);
    let shift_ = make_word!([s, h, i, f, t]);
    let shorter_ = make_word!([s, h, o, r, t, e, r]);
    let stares_ = make_word!([s, t, a, r, e, s]);
    let stars_ = make_word!([s, t, a, r, s]);
    let stores_ = make_word!([s, t, o, r, e, s]);
    let tailor_ = make_word!([t, a, i, l, o, r]);
    let tale_ = make_word!([t, a, l, e]);
    let taste_ = make_word!([t, a, s, t, e]);
    let tear_ = make_word!([t, e, a, r]);
    let teeth_ = make_word!([t, e, e, t, h]);
    let tell_ = make_word!([t, e, l, l]);
    let terrifies_ = make_word!([t, e, r, r, i, f, i, e, s]);
    let that_ = make_word!([t, h, a, t]);
    let the_ = make_word!([t, h, e]);
    let their_ = make_word!([t, h, e, i, r]);
    let there_ = make_word!([t, h, e, r, e]);
    let therefore_ = make_word!([t, h, e, r, e, f, o, r, e]);
    let this_ = make_word!([t, h, i, s]);
    let those_ = make_word!([t, h, o, s, e]);
    let tis_ = make_word!([t, i, s]);
    let title_ = make_word!([t, i, t, l, e]);
    let to_ = make_word!([t, o]);
    let torso_ = make_word!([t, o, r, s, o]);
    let total_ = make_word!([t, o, t, a, l]);
    let troll_ = make_word!([t, r, o, l, l]);
    sys.equals(
        this_
            + 5* a_
            // + a_
            // + a_
            // + a_
            // + a_
            + affiliates_
            + 3*after_
            // + after_
            // + after_
            + alerts_
            + 3* all_
            // + all_
            // + all_
            + arrest_
            + 6*as_
            // + as_
            // + as_
            // + as_
            // + as_
            // + as_
            + assails_
            + assisters_
            + 3* at_
            // + at_
            // + at_
            + falsifies_
            + 2*far_
            // + far_
            + fast_
            + fasts_
            + 3*fathers_
            // + fathers_
            // + fathers_
            + 2*fears_
            // + fears_
            + feasts_
            + 5*fire_
            // + fire_
            // + fire_
            // + fire_
            // + fire_
            + fires_
            + 4* first_
            // + first_
            // + first_
            // + first_
            + fish_
            + flee_
            + 3*for_
            // + for_
            // + for_
            + foresee_
            + 2*forest_
            // + forest_
            + forfeits_
            + 2*free_
            // + free_
            + harasses_
            + hate_
            + 2*hear_
            // + hear_
            + hears_
            + heart_
            + heat_
            + 2*her_
            // + her_
            + histories_
            + hole_
            + hoof_
            + 2*horrors_
            // + horrors_
            + 2*horse_
            // + horse_
            + 6*horses_
            // + horses_
            // + horses_
            // + horses_
            // + horses_
            // + horses_
            + hot_
            + i_
            + is_
            + it_
            + 3*its_
            // + its_
            // + its_
            + 7*last_
            // + last_
            // + last_
            // + last_
            // + last_
            // + last_
            // + last_
            + late_
            + least_
            + leathers_
            + lie_
            + 2*life_
            // + life_
            + losses_
            + 8*of_
            // + of_
            // + of_
            // + of_
            // + of_
            // + of_
            // + of_
            // + of_
            + 4*off_
            // + off_
            // + off_
            // + off_
            + offer_
            + others_
            + raise_
            + resettle_
            + rest_
            + rests_
            + rise_
            + rises_
            + roles_
            + roofs_
            // + safe_
            + satisfies_
            + share_
            + 3*she_
            // + she_
            // + she_
            + shift_
            + shorter_
            + stares_
            + stars_
            + stores_
            + tailor_
            + 2*tale_
            // + tale_
            + taste_
            + tear_
            + teeth_
            + tell_
            + terrifies_
            + 5*that_
            // + that_
            // + that_
            // + that_
            // + that_
            + 29*the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            // + the_
            + 5*their_
            // + their_
            // + their_
            // + their_
            // + their_
            + there_
            + therefore_
            + 2*those_
            // + those_
            + tis_
            + title_
            + 2*to_
            // + to_
            + torso_
            + total_
            + 7*troll_
            // + troll_
            // + troll_
            // + troll_
            // + troll_
            // + troll_
            // + troll_
            + 2*safe_,
        fortresses_,
    );
    let dict = sys.solve_unique().expect("solution");
    assert_eq!(dict[e], 0);
    assert_eq!(dict[a], 1);
    assert_eq!(dict[l], 2);
    assert_eq!(dict[r], 3);
    assert_eq!(dict[s], 4);
    assert_eq!(dict[f], 5);
    assert_eq!(dict[o], 6);
    assert_eq!(dict[i], 7);
    assert_eq!(dict[h], 8);
    assert_eq!(dict[t], 9);
}

I get

---- manyaddends stdout ----
thread 'manyaddends' panicked at 'attempt to multiply with overflow', /rustc/a8314ef7d0ec7b75c336af2c9857bfaf43002bfc/library/core/src/ops/arith.rs:369:1
stack backtrace:
   0: rust_begin_unwind
             at /rustc/a8314ef7d0ec7b75c336af2c9857bfaf43002bfc/library/std/src/panicking.rs:584:5
   1: core::panicking::panic_fmt
             at /rustc/a8314ef7d0ec7b75c336af2c9857bfaf43002bfc/library/core/src/panicking.rs:142:14
   2: core::panicking::panic
             at /rustc/a8314ef7d0ec7b75c336af2c9857bfaf43002bfc/library/core/src/panicking.rs:48:5
   3: <i32 as core::ops::arith::Mul>::mul
             at /rustc/a8314ef7d0ec7b75c336af2c9857bfaf43002bfc/library/core/src/ops/arith.rs:362:45
   4: <num_rational::Ratio<T> as core::ops::arith::Mul>::mul
             at /Users/sverma/.cargo/registry/src/github.com-1ecc6299db9ec823/num-rational-0.1.42/src/lib.rs:570:20
   5: <puzzle_solver::constraint::equality::Equality as puzzle_solver::constraint::Constraint>::on_updated
             at ./src/constraint/equality.rs:84:37
   6: puzzle_solver::puzzle::PuzzleSearch::constrain
             at ./src/puzzle.rs:778:26
   7: puzzle_solver::puzzle::PuzzleSearch::solve
             at ./src/puzzle.rs:686:12
   8: puzzle_solver::puzzle::Puzzle::solve_unique
             at ./src/puzzle.rs:395:13
   9: sendmoremoney::manyaddends
             at ./tests/sendmoremoney.rs:964:16
  10: sendmoremoney::manyaddends::{{closure}}
             at ./tests/sendmoremoney.rs:88:1
  11: core::ops::function::FnOnce::call_once
             at /rustc/a8314ef7d0ec7b75c336af2c9857bfaf43002bfc/library/core/src/ops/function.rs:248:5
  12: core::ops::function::FnOnce::call_once
             at /rustc/a8314ef7d0ec7b75c336af2c9857bfaf43002bfc/library/core/src/ops/function.rs:248:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.


failures:
    manyaddends

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 2 filtered out; finished in 0.02s

This testcase is based on this testcase on exercism

Recommend Projects

wangds / puzzle-solver Goto Github PK

puzzle-solver's Introduction

Puzzle Solver

About

Examples

Basic Usage

Documentation

Author

puzzle-solver's People

Contributors

Stargazers

Watchers

Forkers

puzzle-solver's Issues

Search space small for sendmoremoney

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent