pydoku

A SAT Solver that will make you smile.

Table of Contents

• Key Features
• Download
• Usage

Key Features

• A simple command line interface (CLI) to solve Boolean Satisfiability problems.
• Input and output in the Conjunctive Normal Form DIMACS file format.
• Support for three key branching heuristics:
  • Standard Davis-Putnam-Logemann-Loveland (DPLL)
  • Random literal (RAND)
  • Maximum Occurrences in Clauses of Minimal Size (MOMS)
• Cross platform
  • Windows, macOS and Linux ready.

Download

To clone and run this application, you'll need Git and python3 (which comes with pip) installed on your computer. From your command line:

# Clone this repository
$ git clone https://github.com/bay3s/pydoku

# Go into the repository
$ cd pydoku

# Install CLI tool and dependencies
$ pip install .

# Run the help command
$ SAT --help

Usage

Once you have followed the download and installation instructions, the command line utility (CLI) should be available for use on your computer. You can find a list of available tools offered by the CLI by typing in SAT --help command.

In order to use the CLI to solve a Satisfiability problem, we require that you provide the CLI an input file describing a propositional logic formula in Conjunctive Normal Form (CNF) using DIMACS.

As mentioned in the Key Features section, the current version of this project supports three heuristics by to solve CNFs. In order to choose a specific heuristic to run using the CLI, you only need to supply the CLI with one of the following option flags: -S1, -S2, or -S3. The mapping between each of these option flags and the heuristic used to solve the CNF is outlined in the table below:

Option	Heuristic
-S1	Standard Davis-Putnam-Logemann-Loveland (DPLL)
-S2	Random literal (RAND)
-S3	Maximum Occurrences in Clauses of Minimal Size (MOMS)

Sample Usage

  SAT -S1 [DIMACS_INPUT_FILE] // will run DPLL on the CNF defined in the DIMACS_INPUT_FILE
  SAT -S2 [DIMACS_INPUT_FILE] // will use RAND as the branching heuristic while solving the CNF
  SAT -S3 [DIMACS_INPUT_FILE] // will use MOMS as the branching heuristic while solving the CNF

If a satisifiable solution for the provided CNF is found, the CLI will output a file in DIMACS format containing the assignments which satisfied the input CNF. This file will be output in the same directory as the original input file provided albeit with a .out extension.

So, if your input file was ~/Desktop/9x9-sudoku-dimacs.txt, the output file will be ~/Desktop/9x9-sudoku-dimacs.txt.out.