项目作者: soultanis

项目描述 :
Backtracking, watchlist-based, Boolean satisfiability problem solver
高级语言: Python
项目地址: git://github.com/soultanis/Classic-SAT-Solver.git
创建时间: 2019-06-09T18:55:22Z
项目社区:https://github.com/soultanis/Classic-SAT-Solver

开源协议:

下载


Classic SAT solver in Python

This project is a iterative implementation of a backtracking, watchlist-based, SAT solver.

Usage

  1. usage: run.py [-h] [-v] [-a] [-b] [--output_filter OUTPUT_FILTER]
  2. [-i INPUT]
  3. Solve SAT instance by reading from stdin using an iterative or recursive
  4. watchlist-based backtracking algorithm. Recursive algorithm is used by
  5. default, unless the --iterative flag is given. Empty lines and lines that
  6. starting with a # will be ignored.
  7. optional arguments:
  8. -h, --help show this help message and exit
  9. -v, --verbose verbose output.
  10. -a, --all output all possible solutions.
  11. -b, --brief brief output for assignemnts: outputs variables
  12. assigned 1.
  13. --output_filter OUTPUT_FILTER
  14. only output variables with name-string with given
  15. string.
  16. --iterative use the iterative solver.
  17. -i INPUT, --input INPUT
  18. read from given file instead of stdin.

Example Usage

  1. $ python run.py -v -i examples/03.in.txt
  2. Trying A = 0
  3. Trying C = 0
  4. Current watchlist:
  5. A:
  6. ~A:
  7. C: C, A C
  8. ~C:
  9. B: C B
  10. ~B: ~B
  11. Current assignment: ~A ~C
  12. Clause C contradicted.
  13. Trying C = 1
  14. Trying B = 0
  15. Found satisfying assignment #1:
  16. ~A C ~B

Reference

[1] Understanding SAT by Implementing a Simple SAT Solver in Python