===============================================================================
MiniSat ver 1.12   [Niklas Een/Srensson {een,nik}@cs.chalmers.se, 22 Jun 2004]
===============================================================================

This is a continued development of the source code of the solver presented in
"An Extensible SAT-Solver", proceedings of SAT 2003 conference (also available
in extended version at 'http://www.cs.chalmers.se/~een/Satzoo'). If you find
bugs or make interesting improvements or extensions, please let us know. The
code may be used freely in any non-commercial project as long as due credit is
given. To receive a license for commercial use, please contact us.

To build the solver, just run 'gmake' (standard version), 'gmake r' (release
version) 'gmake d' (debug version) or 'gmake p' (profile version). If you don't
have 'gmake', or have troubles with the makefile, have a look at the script
'compile'. Usage: 'MiniSat <dimacs-file>'


Fixes/modification from version 1.11 to 1.12
===============================================================================

* The 'Solver' class now has a method 'bool okay()' which returns FALSE if the
  solver is in a conflicting state (a top-level conflict was found). It is now
  okay to use the public methods even if the solver is in this state. (Internal
  methods still upholds the invariant that the solver is not in a conflicting
  state.)

* The interface for the 'propagate()' method of 'Constr' has changed. Instead
  of always removing a constraint from the watcher list before calling 
  'propagate()', the method now signals through an extra return parameter
  whether the constraint should be kept in the watcher list or not. This
  change was done for efficiency reasons.

* The method 'Clause::simplify()' no longer removes false literals. This
  optimization did not give any measurable speed-up so we simplified the code.

* Likewise 'Solver::analyze()' no longer excludes top-level literals (which are
  assigned) from conflict clauses. The implementation in 1.11 actually violated
  the "('seen[]' is now cleared)" comment, although the solver happened to
  remain sound anyway.

* The efficiency of 'VarOrder' has been slightly improved.


Fixes/modification from version 1.10 to 1.11
===============================================================================

* Fixed bug concerning position of activity field after shrinking a clause.

* One word too much was previously allocated per clause (adjusted).

* Branch variables are occasionally chosen randomly. This gives a quite 
  consistent speed-up.

* 'simplifyDB()' is not carried out unless there is a new top-level assignment.

* Some temporaries are moved to the 'Solver' class to improve allocation
  behavior. 

* Variables can be excluded from the set of possible decision variables in
  'newVar()'. 

* MiniSat now works correctly under Microsoft Visual C++.

* Using 'getrusage()' instead of 'clock()' for timing (the latter wraps too
  quickly).

* Clauses are now inspectable (operator [] is definied and public).


Fixes/modification from version 1.00 to 1.10
===============================================================================

* 'enqueue' does no longer clear the propagation queue in the event of a
  conflict. The reason is that this is not enough when using more general
  constraints -- a conflict might occur without any failing calls to enqueue,
  and in this case the queue might fail to be cleared.

  Instead, the queue is cleared in 'propagate' whenever a conflict occurs.
  Moreover, we added this as a post-condition to the method to make the issue
  clear.

  Finally, since 'enqueue' no longer clears the queue, 'solve' has to clear the
  queue in the case of a failing initial assumption.

  Comment: An alternative would have been to still clear the queue in
  'enqueue', but we prefer to be careful since we believe this will expose more
  bugs in the future.

* The AtMost constraint is too weak, and fails to detect conflicts. The reason
  is the following lines (Constraints.C, L217):

        for (int i = 0; i < size; i++)
            if (S.value(lits[i]) == l_Undef && !S.enqueue(~lits[i], this))

  here if 'lits[i]' is set to true for some 'i', then this is not
  detected. Since 'enqueue' checks that a value is not propagated twice anyway
  it is safe to change it to:

        for (int i = 0; i < size; i++)
            if (!S.enqueue(~lits[i], this))


On line counting... (not updated)
===============================================================================

Size of code can be measured in lines, characters, tokens, semi-colons,
whatever. By any measure, MiniSat should be a small Chaff like SAT-solver,
which should aid clarity. The below line counts excludes comments and empty
lines. The reported lines count of the article does not include the supporting
ADTs (we could have (should have?) used STL instead). Rember that the other
solvers often contains more feature as well as debugging code, so we don't
claim the comparison to be 100% fair.


MiniSat 1.00
  solver core    : 571   (the actual solver)
  supporting ADTs: 219   (sorting routine and an extensible vector)  
  parser & main  : 109   (DIMACS parser, statistics, timing etc.)

  total            899 lines

MiniSat 1.11
  solver core    : 602   (the actual solver)
  supporting ADTs: 237   (sorting routine and an extensible vector)  
  parser & main  : 107   (DIMACS parser, statistics, timing etc.)

  total            946 lines

Limmat : 5844 lines  (includes self-test code)
zChaff : 2718 lines
Jerusat: 6489 lines
Satire : 5855 lines  (supports pseudo-boolean constraints)
Satzoo : 2819 lines  (supports pseudo-boolean constraints)
Satnik :  925 lines  (not including 1121 lines for the auto-generated lexer)



