U
    9%e]O                     @   sj   d Z ddlmZ ddlmZmZ ddlmZ ddlm	Z	 dddZ
d	d
 ZG dd dZG dd dZdS )zImplementation of DPLL algorithm

Features:
  - Clause learning
  - Watch literal scheme
  - VSIDS heuristic

References:
  - https://en.wikipedia.org/wiki/DPLL_algorithm
    )defaultdict)heappushheappop)ordered)
EncodedCNFFc                 C   s   t | tst }||  |} dh| jkr@|r<dd dD S dS t| j| jt | j}| }|rjt	|S z
t
|W S  tk
r   Y dS X dS )a  
    Check satisfiability of a propositional sentence.
    It returns a model rather than True when it succeeds.
    Returns a generator of all models if all_models is True.

    Examples
    ========

    >>> from sympy.abc import A, B
    >>> from sympy.logic.algorithms.dpll2 import dpll_satisfiable
    >>> dpll_satisfiable(A & ~B)
    {A: True, B: False}
    >>> dpll_satisfiable(A & ~A)
    False

    r   c                 s   s   | ]
}|V  qd S N ).0fr   r   [/var/www/html/Darija-Ai-API/env/lib/python3.8/site-packages/sympy/logic/algorithms/dpll2.py	<genexpr>,   s     z#dpll_satisfiable.<locals>.<genexpr>)FFN)
isinstancer   Zadd_propdata	SATSolver	variablessetsymbols_find_model_all_modelsnextStopIteration)exprZ
all_modelsexprsZsolvermodelsr   r   r   dpll_satisfiable   s     


r   c                 c   s<   d}zt | V  d}qW n tk
r6   |s2dV  Y nX d S )NFT)r   r   )r   Zsatisfiabler   r   r   r   @   s    

r   c                   @   s   e Zd ZdZd0ddZdd	 Zd
d Zdd Zedd Z	dd Z
dd Zdd Zdd Zdd Zdd Zdd Zdd Zd d! Zd"d# Zd$d% Zd&d' Zd(d) Zd*d+ Zd,d- Zd.d/ ZdS )1r   z
    Class for representing a SAT solver capable of
     finding a model to a boolean theory in conjunctive
     normal form.
    Nvsidsnone  c                 C   s  || _ || _d| _g | _g | _|| _|d kr<tt|| _n|| _| 	| | 
| d|kr|   | j| _| j| _| j| _| j| _ntd|kr| j| _| j| _| j| j n"d|krdd | _dd | _nttdg| _|| j_d| _d| _ t!| j"| _#d S )	NFr   simpler   c                 S   s   d S r   r   )xr   r   r   <lambda>v       z$SATSolver.__init__.<locals>.<lambda>c                   S   s   d S r   r   r   r   r   r   r    w   r!   r   )$var_settings	heuristicis_unsatisfied_unit_prop_queueupdate_functionsINTERVALlistr   r   _initialize_variables_initialize_clauses_vsids_init_vsids_calculateheur_calculate_vsids_lit_assignedheur_lit_assigned_vsids_lit_unsetheur_lit_unset_vsids_clause_addedheur_clause_addedNotImplementedError_simple_add_learned_clauseadd_learned_clauseZsimple_compute_conflictcompute_conflictappendZsimple_clean_clausesLevellevels_current_levelZvarsettingsnum_decisionsnum_learned_clauseslenclausesZoriginal_num_clauses)selfr?   r   r"   r   r#   Zclause_learningr'   r   r   r   __init__R   s>    



zSATSolver.__init__c                 C   s,   t t| _t t| _dgt|d  | _dS )z+Set up the variable data structures needed.F   N)r   r   	sentinelsintoccurrence_countr>   variable_set)r@   r   r   r   r   r)      s    

zSATSolver._initialize_variablesc                 C   s   dd |D | _ t| j D ]j\}}dt|kr@| j|d  q| j|d  | | j|d  | |D ]}| j|  d7  < qlqdS )a<  Set up the clause data structures needed.

        For each clause, the following changes are made:
        - Unit clauses are queued for propagation right away.
        - Non-unit clauses have their first and last literals set as sentinels.
        - The number of clauses a literal appears in is computed.
        c                 S   s   g | ]}t |qS r   )r(   )r	   clauser   r   r   
<listcomp>   s     z1SATSolver._initialize_clauses.<locals>.<listcomp>rB   r   N)r?   	enumerater>   r%   r8   rC   addrE   )r@   r?   irG   litr   r   r   r*      s    zSATSolver._initialize_clausesc                 #   s`  d}     jrdS  j j dkr8 jD ]
}|  q,|rJd} jj}n  }  jd7  _d|kr· fdd jD V   jj	r 
  q~t jdkrdS  jj } 
   jt|dd d}q jt|  |      jrd _ jj	r" 
  dt jkrdS q     jj } 
   jt|dd d}qdS )	an  
        Main DPLL loop. Returns a generator of models.

        Variables are chosen successively, and assigned to be either
        True or False. If a solution is not found with this setting,
        the opposite is chosen and the search continues. The solver
        halts when every variable has a setting.

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())
        >>> list(l._find_model())
        [{1: True, 2: False, 3: False}, {1: True, 2: True, 3: True}]

        >>> from sympy.abc import A, B, C
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set(), [A, B, C])
        >>> list(l._find_model())
        [{A: True, B: False, C: False}, {A: True, B: True, C: True}]

        FNr   rB   c                    s$   i | ]} j t|d   |dkqS )rB   r   )r   abs)r	   rM   r@   r   r   
<dictcomp>   s   z)SATSolver._find_model.<locals>.<dictcomp>T)flipped)	_simplifyr$   r<   r'   r&   r;   decisionr-   r"   rQ   _undor>   r:   r8   r9   _assign_literalr6   r7   )r@   Zflip_varfuncrM   Zflip_litr   rO   r   r      sN    







zSATSolver._find_modelc                 C   s
   | j d S )a  The current decision level data structure

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{1}, {2}], {1, 2}, set())
        >>> next(l._find_model())
        {1: True, 2: True}
        >>> l._current_level.decision
        0
        >>> l._current_level.flipped
        False
        >>> l._current_level.var_settings
        {1, 2}

        rI   r:   rO   r   r   r   r;     s    zSATSolver._current_levelc                 C   s$   | j | D ]}|| jkr
 dS q
dS )a  Check if a clause is satisfied by the current variable setting.

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{1}, {-1}], {1}, set())
        >>> try:
        ...     next(l._find_model())
        ... except StopIteration:
        ...     pass
        >>> l._clause_sat(0)
        False
        >>> l._clause_sat(1)
        True

        TF)r?   r"   r@   clsrM   r   r   r   _clause_sat  s    
zSATSolver._clause_satc                 C   s   || j | kS )a  Check if a literal is a sentinel of a given clause.

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())
        >>> next(l._find_model())
        {1: True, 2: False, 3: False}
        >>> l._is_sentinel(2, 3)
        True
        >>> l._is_sentinel(-3, 1)
        False

        )rC   )r@   rM   rY   r   r   r   _is_sentinel1  s    zSATSolver._is_sentinelc                 C   s   | j | | jj | d| jt|< | | t| j|  }|D ]}| |sFd}| j	| D ]X}|| krb| 
||r|}qb| jt| sb| j|  | | j| | d} qqb|rF| j| qFdS )a  Make a literal assignment.

        The literal assignment must be recorded as part of the current
        decision level. Additionally, if the literal is marked as a
        sentinel of any clause, then a new sentinel must be chosen. If
        this is not possible, then unit propagation is triggered and
        another literal is added to the queue to be set in the future.

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())
        >>> next(l._find_model())
        {1: True, 2: False, 3: False}
        >>> l.var_settings
        {-3, -2, 1}

        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())
        >>> l._assign_literal(-1)
        >>> try:
        ...     next(l._find_model())
        ... except StopIteration:
        ...     pass
        >>> l.var_settings
        {-1}

        TN)r"   rK   r;   rF   rN   r/   r(   rC   rZ   r?   r[   remover%   r8   )r@   rM   Zsentinel_listrY   Zother_sentinelZnewlitr   r   r   rU   D  s&    


zSATSolver._assign_literalc                 C   s@   | j jD ](}| j| | | d| jt|< q| j  dS )ag  
        _undo the changes of the most recent decision level.

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())
        >>> next(l._find_model())
        {1: True, 2: False, 3: False}
        >>> level = l._current_level
        >>> level.decision, level.var_settings, level.flipped
        (-3, {-3, -2}, False)
        >>> l._undo()
        >>> level = l._current_level
        >>> level.decision, level.var_settings, level.flipped
        (0, {1}, False)

        FN)r;   r"   r\   r1   rF   rN   r:   popr@   rM   r   r   r   rT   {  s
    
zSATSolver._undoc                 C   s*   d}|r&d}||   O }||  O }qdS )ad  Iterate over the various forms of propagation to simplify the theory.

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())
        >>> l.variable_set
        [False, False, False, False]
        >>> l.sentinels
        {-3: {0, 2}, -2: {3, 4}, 2: {0, 3}, 3: {2, 4}}

        >>> l._simplify()

        >>> l.variable_set
        [False, True, False, False]
        >>> l.sentinels
        {-3: {0, 2}, -2: {3, 4}, -1: set(), 2: {0, 3},
        ...3: {2, 4}}

        TFN)
_unit_prop_pure_literal)r@   changedr   r   r   rR     s
    zSATSolver._simplifyc                 C   sJ   t | jdk}| jrF| j }| | jkr:d| _g | _dS | | q|S )z/Perform unit propagation on the current theory.r   TF)r>   r%   r]   r"   r$   rU   )r@   resultZnext_litr   r   r   r_     s    
zSATSolver._unit_propc                 C   s   dS )z2Look for pure literals and assign them when found.Fr   rO   r   r   r   r`     s    zSATSolver._pure_literalc                 C   s   g | _ i | _tdt| jD ]d}t| j|  | j|< t| j|   | j| < t| j | j| |f t| j | j|  | f qdS )z>Initialize the data structures needed for the VSIDS heuristic.rB   N)lit_heap
lit_scoresranger>   rF   floatrE   r   )r@   varr   r   r   r+     s    zSATSolver._vsids_initc                 C   s&   | j  D ]}| j |  d  < q
dS )a  Decay the VSIDS scores for every literal.

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())

        >>> l.lit_scores
        {-3: -2.0, -2: -2.0, -1: 0.0, 1: 0.0, 2: -2.0, 3: -2.0}

        >>> l._vsids_decay()

        >>> l.lit_scores
        {-3: -1.0, -2: -1.0, -1: 0.0, 1: 0.0, 2: -1.0, 3: -1.0}

        g       @N)rd   keysr^   r   r   r   _vsids_decay  s    zSATSolver._vsids_decayc                 C   sV   t | jdkrdS | jt| jd d  rHt| j t | jdkrdS qt| jd S )a  
            VSIDS Heuristic Calculation

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())

        >>> l.lit_heap
        [(-2.0, -3), (-2.0, 2), (-2.0, -2), (0.0, 1), (-2.0, 3), (0.0, -1)]

        >>> l._vsids_calculate()
        -3

        >>> l.lit_heap
        [(-2.0, -2), (-2.0, 2), (0.0, -1), (0.0, 1), (-2.0, 3)]

        r   rB   )r>   rc   rF   rN   r   rO   r   r   r   r,     s    
zSATSolver._vsids_calculatec                 C   s   dS )z;Handle the assignment of a literal for the VSIDS heuristic.Nr   r^   r   r   r   r.     s    zSATSolver._vsids_lit_assignedc                 C   s<   t |}t| j| j| |f t| j| j|  | f dS )a  Handle the unsetting of a literal for the VSIDS heuristic.

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())
        >>> l.lit_heap
        [(-2.0, -3), (-2.0, 2), (-2.0, -2), (0.0, 1), (-2.0, 3), (0.0, -1)]

        >>> l._vsids_lit_unset(2)

        >>> l.lit_heap
        [(-2.0, -3), (-2.0, -2), (-2.0, -2), (-2.0, 2), (-2.0, 3), (0.0, -1),
        ...(-2.0, 2), (0.0, 1)]

        N)rN   r   rc   rd   )r@   rM   rg   r   r   r   r0     s    zSATSolver._vsids_lit_unsetc                 C   s.   |  j d7  _ |D ]}| j|  d7  < qdS )aD  Handle the addition of a new clause for the VSIDS heuristic.

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())

        >>> l.num_learned_clauses
        0
        >>> l.lit_scores
        {-3: -2.0, -2: -2.0, -1: 0.0, 1: 0.0, 2: -2.0, 3: -2.0}

        >>> l._vsids_clause_added({2, -3})

        >>> l.num_learned_clauses
        1
        >>> l.lit_scores
        {-3: -1.0, -2: -2.0, -1: 0.0, 1: 0.0, 2: -1.0, 3: -2.0}

        rB   N)r=   rd   rX   r   r   r   r2   1  s    zSATSolver._vsids_clause_addedc                 C   sh   t | j}| j| |D ]}| j|  d7  < q| j|d  | | j|d  | | | dS )a  Add a new clause to the theory.

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())

        >>> l.num_learned_clauses
        0
        >>> l.clauses
        [[2, -3], [1], [3, -3], [2, -2], [3, -2]]
        >>> l.sentinels
        {-3: {0, 2}, -2: {3, 4}, 2: {0, 3}, 3: {2, 4}}

        >>> l._simple_add_learned_clause([3])

        >>> l.clauses
        [[2, -3], [1], [3, -3], [2, -2], [3, -2], [3]]
        >>> l.sentinels
        {-3: {0, 2}, -2: {3, 4}, 2: {0, 3}, 3: {2, 4, 5}}

        rB   r   rI   N)r>   r?   r8   rE   rC   rK   r3   )r@   rY   Zcls_numrM   r   r   r   r5   O  s    
z$SATSolver._simple_add_learned_clausec                 C   s   dd | j dd D S )a   Build a clause representing the fact that at least one decision made
        so far is wrong.

        Examples
        ========

        >>> from sympy.logic.algorithms.dpll2 import SATSolver
        >>> l = SATSolver([{2, -3}, {1}, {3, -3}, {2, -2},
        ... {3, -2}], {1, 2, 3}, set())
        >>> next(l._find_model())
        {1: True, 2: False, 3: False}
        >>> l._simple_compute_conflict()
        [3]

        c                 S   s   g | ]}|j  qS r   )rS   )r	   levelr   r   r   rH     s     z6SATSolver._simple_compute_conflict.<locals>.<listcomp>rB   NrW   rO   r   r   r   _simple_compute_conflicts  s    z"SATSolver._simple_compute_conflictc                 C   s   dS )zClean up learned clauses.Nr   rO   r   r   r   _simple_clean_clauses  s    zSATSolver._simple_clean_clauses)Nr   r   r   )__name__
__module____qualname____doc__rA   r)   r*   r   propertyr;   rZ   r[   rU   rT   rR   r_   r`   r+   ri   r,   r.   r0   r2   r5   rk   rl   r   r   r   r   r   K   s6         
2d
7& $r   c                   @   s   e Zd ZdZdddZdS )r9   z
    Represents a single level in the DPLL algorithm, and contains
    enough information for a sound backtracking procedure.
    Fc                 C   s   || _ t | _|| _d S r   )rS   r   r"   rQ   )r@   rS   rQ   r   r   r   rA     s    zLevel.__init__N)F)rm   rn   ro   rp   rA   r   r   r   r   r9     s   r9   N)F)rp   collectionsr   heapqr   r   Zsympy.core.sortingr   Zsympy.assumptions.cnfr   r   r   r   r9   r   r   r   r   <module>   s   
-    C