ersatz: A monad for expressing SAT or QSAT problems using observable sharing.
A monad for expressing SAT or QSAT problems using observable sharing.
For example, we can express a full-adder with:
full_adder :: Bit -> Bit -> Bit -> (Bit, Bit) full_adder a b cin = (s2, c1 || c2) where (s1,c1) = half_adder a b (s2,c2) = half_adder s1 cin
half_adder :: Bit -> Bit -> (Bit, Bit) half_adder a b = (a `xor` b, a && b)
Longer Examples
Included are a couple of examples included with the distribution.
Neither are as fast as a dedicated solver for their respective
domains, but they showcase how you can solve real world problems
involving 10s or 100s of thousands of variables and constraints
with ersatz
.
ersatz-sudoku
% time ersatz-sudoku Problem: ┌───────┬───────┬───────┐ │ 5 3 │ 7 │ │ │ 6 │ 1 9 5 │ │ │ 9 8 │ │ 6 │ ├───────┼───────┼───────┤ │ 8 │ 6 │ 3 │ │ 4 │ 8 3 │ 1 │ │ 7 │ 2 │ 6 │ ├───────┼───────┼───────┤ │ 6 │ │ 2 8 │ │ │ 4 1 9 │ 5 │ │ │ 8 │ 7 9 │ └───────┴───────┴───────┘ Solution: ┌───────┬───────┬───────┐ │ 5 3 4 │ 6 7 8 │ 9 1 2 │ │ 6 7 2 │ 1 9 5 │ 3 4 8 │ │ 1 9 8 │ 3 4 2 │ 5 6 7 │ ├───────┼───────┼───────┤ │ 8 5 9 │ 7 6 1 │ 4 2 3 │ │ 4 2 6 │ 8 5 3 │ 7 9 1 │ │ 7 1 3 │ 9 2 4 │ 8 5 6 │ ├───────┼───────┼───────┤ │ 9 6 1 │ 5 3 7 │ 2 8 4 │ │ 2 8 7 │ 4 1 9 │ 6 3 5 │ │ 3 4 5 │ 2 8 6 │ 1 7 9 │ └───────┴───────┴───────┘ ersatz-sudoku 1,13s user 0,04s system 99% cpu 1,179 total
ersatz-regexp-grid
This solves the "regular crossword puzzle" (grid.pdf) from the 2013 MIT mystery hunt.
% time ersatz-regexp-grid
ersatz-regexp-grid 2,45s user 0,05s system 99% cpu 2,502 total
[Skip to Readme]
Modules
[Index] [Quick Jump]
Flags
Manual Flags
Name | Description | Default |
---|---|---|
examples | Build examples | Enabled |
Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info
Downloads
- ersatz-0.5.tar.gz [browse] (Cabal source package)
- Package description (revised from the package)
Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
- No Candidates
Versions [RSS] | 0.1, 0.1.0.1, 0.1.0.2, 0.2, 0.2.0.1, 0.2.4, 0.2.5, 0.2.5.1, 0.2.6, 0.2.6.1, 0.3, 0.3.1, 0.4, 0.4.1, 0.4.2, 0.4.3, 0.4.4, 0.4.5, 0.4.6, 0.4.7, 0.4.8, 0.4.9, 0.4.10, 0.4.11, 0.4.12, 0.4.13, 0.5 |
---|---|
Change log | CHANGELOG.md |
Dependencies | array (>=0.2 && <0.6), attoparsec, base (>=4.9 && <5), bytestring (>=0.10.4.0 && <0.13), containers (>=0.2.0.1 && <0.8), data-default (>=0.5 && <0.9), ersatz, fail, lens (>=4 && <6), mtl (>=1.1 && <2.4), parsec (>=3.1 && <3.2), process (>=1.1 && <1.7), semigroups (>=0.16 && <1), streams (>=3.3 && <4), temporary (>=1.1 && <1.4), transformers (>=0.3 && <0.7), unordered-containers (>=0.2 && <0.3) [details] |
Tested with | ghc ==8.0.2, ghc ==8.2.2, ghc ==8.4.4, ghc ==8.6.5, ghc ==8.8.4, ghc ==8.10.7, ghc ==9.0.2, ghc ==9.2.7, ghc ==9.4.5, ghc ==9.6.2 |
License | BSD-3-Clause |
Copyright | © 2010-2015 Edward A. Kmett, © 2014-2015 Eric Mertens, © 2013 Johan Kiviniemi |
Author | Edward A. Kmett, Eric Mertens, Johan Kiviniemi |
Maintainer | Edward A. Kmett <ekmett@gmail.com> |
Revised | Revision 2 made by ryanglscott at 2024-10-26T20:07:59Z |
Category | Logic, Algorithms |
Home page | http://github.com/ekmett/ersatz |
Bug tracker | http://github.com/ekmett/ersatz/issues |
Source repo | head: git clone git://github.com/ekmett/ersatz.git |
Uploaded | by ryanglscott at 2023-09-18T10:26:28Z |
Distributions | LTSHaskell:0.5, Stackage:0.5 |
Reverse Dependencies | 3 direct, 0 indirect [details] |
Executables | ersatz-sudoku, ersatz-regexp-grid |
Downloads | 19089 total (39 in the last 30 days) |
Rating | 2.0 (votes: 1) [estimated by Bayesian average] |
Your Rating | |
Status | Docs uploaded by user Build status unknown [no reports yet] |