§
    OŠtjùS  ã                   óŒ   — 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l
mZ dd„Zd	„ Z G d
„ d¦  «        Z G d„ d¦  «        ZdS )z«Implementation of DPLL algorithm

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

References:
  - https://en.wikipedia.org/wiki/DPLL_algorithm
é    )Údefaultdict)ÚheappushÚheappop)Úordered)Ú
EncodedCNF)Ú	LRASolverFc                 óÖ  — t          | t          ¦  «        s%t          ¦   «         }|                     | ¦  «         |} dh| j        v r|rd„ dD ¦   «         S dS |rt	          j        | ¦  «        \  }}nd}g }t          | j        |z   | j        t          ¦   «         | j	        |¬¦  «        }| 
                    ¦   «         }|rt          |¦  «        S 	 t          |¦  «        S # t          $ r Y dS w xY w)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              3   ó   K  — | ]}|V — Œd S ©N© )Ú.0Úfs     úZ/var/www/html/CA-Chatbot/venv/lib/python3.11/site-packages/sympy/logic/algorithms/dpll2.pyú	<genexpr>z#dpll_satisfiable.<locals>.<genexpr>.   s"   è è € Ð'Ð'˜!�AÐ'Ð'Ð'Ð'Ð'Ð'ó    ©FFN)Ú
lra_theory)Ú
isinstancer   Úadd_propÚdatar   Úfrom_encoded_cnfÚ	SATSolverÚ	variablesÚsetÚsymbolsÚ_find_modelÚ_all_modelsÚnextÚStopIteration)ÚexprÚ
all_modelsÚuse_lra_theoryÚexprsÚlraÚimmediate_conflictsÚsolverÚmodelss           r   Údpll_satisfiabler(      s  € õ" �d�JÑ'Ô'ð Ý‘”ˆØ�Š�tÑÔÐØˆð 	
€sˆdŒiÐÐØð 	(Ø'Ð'˜wÐ'Ñ'Ô'Ð'Øˆuàð !Ý#,Ô#=¸dÑ#CÔ#CÑ ˆÐ Ð àˆØ ÐÝ�t”yÐ#6Ñ6¸¼ÍÉÌÈtÌ|ÐhkÐlÑlÔl€FØ×ÒÑ!Ô!€Fàð #Ý˜6Ñ"Ô"Ð"ðÝ�F‰|Œ|ÐøÝð ð ð Øˆuˆuðøøøs   ÃC Ã
C(Ã'C(c              #   ój   K  — d}	 	 t          | ¦  «        V — d}Œ# t          $ r |sdV — Y d S Y d S w xY w)NFT)r   r   )r'   Úsatisfiables     r   r   r   G   st   è è € Ø€Kðð	Ý�v‘,”,ÐÐÐØˆKð	øõ ð ð ð Øð 	ØˆKˆKˆKˆKˆKˆKð	ð 	ð 	ðøøøs   † ›2±2c                   óª   — e Zd ZdZ	 	 	 dd„Zd„ Zd„ Zd	„ Zed
„ ¦   «         Z	d„ Z
d„ Zd„ Zd„ Z	 d„ Zd„ Zd„ Zd„ Zd„ Zd„ Zd„ Zd„ Zd„ Zd„ Zd„ Zd„ ZdS )r   z‚
    Class for representing a SAT solver capable of
     finding a model to a boolean theory in conjunctive
     normal form.
    NÚvsidsÚnoneéô  c	                 óþ  — || _         || _        d| _        g | _        g | _        || _        |€"t          t          |¦  «        ¦  «        | _        n|| _        |  	                    |¦  «         |  
                    |¦  «         d|k    rE|                      ¦   «          | j        | _        | j        | _        | j        | _        | j        | _        nt(          ‚d|k    r8| j        | _        | j        | _        | j                             | j        ¦  «         nd|k    rd„ | _        d„ | _        nt(          ‚t7          d¦  «        g| _        || j        _        d| _        d| _         tC          | j"        ¦  «        | _#        || _$        d S )NFr,   Úsimpler-   c                 ó   — d S r   r   )Úxs    r   ú<lambda>z$SATSolver.__init__.<locals>.<lambda>~   s   € °€ r   c                  ó   — d S r   r   r   r   r   r3   z$SATSolver.__init__.<locals>.<lambda>   s   € ¨D€ 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_clauseÚ_simple_compute_conflictÚcompute_conflictÚappendÚ_simple_clean_clausesÚLevelÚlevelsÚ_current_levelÚvarsettingsÚnum_decisionsÚnum_learned_clausesÚlenÚclausesÚoriginal_num_clausesr$   )	ÚselfrU   r   r5   r   r6   Úclause_learningr:   r   s	            r   Ú__init__zSATSolver.__init__Y   s„  € ð )ˆÔØ"ˆŒØ#ˆÔØ "ˆÔØ "ˆÔØ ˆŒàˆ?Ý¥¨	Ñ 2Ô 2Ñ3Ô3ˆDŒLˆLà"ˆDŒLà×"Ò" 9Ñ-Ô-Ð-Ø× Ò  Ñ)Ô)Ð)à�iÒÐØ×ÒÑÔÐØ"&Ô"7ˆDÔØ%)Ô%=ˆDÔ"Ø"&Ô"7ˆDÔØ%)Ô%=ˆDÔ"Ð"õ &Ð%à�Ò&Ð&Ø&*Ô&EˆDÔ#Ø$(Ô$AˆDÔ!ØÔ!×(Ò(¨Ô)CÑDÔDÐDÐDØ�Ò&Ð&Ø&4 nˆDÔ#Ø$0 LˆDÔ!Ð!å%Ð%õ ˜Q‘x”x�jˆŒØ*6ˆÔÔ'ð ˆÔØ#$ˆÔ Ý$'¨¬Ñ$5Ô$5ˆÔ!àˆŒˆˆr   c                 ó    — t          t          ¦  «        | _        t          t          ¦  «        | _        dgt          |¦  «        dz   z  | _        dS )z+Set up the variable data structures needed.Fé   N)r   r   Ú	sentinelsÚintÚoccurrence_countrT   Úvariable_set)rW   r   s     r   r<   zSATSolver._initialize_variablesŽ   sA   € å$¥SÑ)Ô)ˆŒÝ +­CÑ 0Ô 0ˆÔØ"˜G¥s¨9¡~¤~¸Ñ'9Ñ:ˆÔÐÐr   c                 ó�  — d„ |D ¦   «         | _         t          | j         ¦  «        D ]Ÿ\  }}dt          |¦  «        k    r!| j                             |d         ¦  «         Œ9| j        |d                                       |¦  «         | j        |d                                       |¦  «         |D ]}| j        |xx         dz  cc<   ŒŒ 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                 ó,   — g | ]}t          |¦  «        ‘ŒS r   )r;   )r   Úclauses     r   ú
<listcomp>z1SATSolver._initialize_clauses.<locals>.<listcomp>œ   s   € Ð;Ð;Ð;¨�˜V™œÐ;Ð;Ð;r   r[   r   éÿÿÿÿN)rU   Ú	enumeraterT   r8   rL   r\   Úaddr^   )rW   rU   Úirb   Úlits        r   r=   zSATSolver._initialize_clauses”   så   € ð <Ð;°7Ð;Ñ;Ô;ˆŒå" 4¤<Ñ0Ô0ð 	0ð 	0‰IˆAˆvð •C˜‘K”KÒÐØÔ%×,Ò,¨V°A¬YÑ7Ô7Ð7ØàŒN˜6 !œ9Ô%×)Ò)¨!Ñ,Ô,Ð,ØŒN˜6 "œ:Ô&×*Ò*¨1Ñ-Ô-Ð-àð 0ð 0�ØÔ% cÐ*Ð*Ô*¨aÑ/Ð*Ð*Ñ*Ð*ð0ð	0ð 	0r   c              #   óf  ‡ ‡K  — d}‰                       ¦   «          ‰ j        rdS 	 ‰ j        ‰ j        z  dk    r‰ j        D ]} |¦   «          Œ|rd}‰ j        j        }�nã‰                      ¦   «         }‰ xj        dz  c_        d|k    �r‘‰ j        r[‰ j	        D ] }‰ j         
                    |¦  «        Š‰� nŒ!‰ j                             ¦   «         Š‰ j                             ¦   «          ndŠ‰�‰d         rˆ fd„‰ j	        D ¦   «         V — ny‰                      ‰d         ¦  «         t          ˆfd„‰ j        j	        D ¦   «         ¦  «        s9‰                      ¦   «          t          ˆfd„‰ j        j	        D ¦   «         ¦  «        ¯9‰ j        j        r ‰                      ¦   «          ‰ j        j        ° t#          ‰ j        ¦  «        dk    rdS ‰ j        j         }‰                      ¦   «          ‰ j                             t)          |d¬¦  «        ¦  «         d}�Œö‰ j                             t)          |¦  «        ¦  «         ‰                      |¦  «         ‰                       ¦   «          ‰ j        rÀd‰ _        ‰ j        j        r:‰                      ¦   «          dt#          ‰ j        ¦  «        k    rdS ‰ j        j        °:‰                      ‰                      ¦   «         ¦  «         ‰ j        j         }‰                      ¦   «          ‰ j                             t)          |d¬¦  «        ¦  «         d}�Œ)	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}]

        FNTr   r[   c                 óT   •— i | ]$}‰j         t          |¦  «        d z
           |dk    “Œ%S )r[   r   )r   Úabs)r   rh   rW   s     €r   ú
<dictcomp>z)SATSolver._find_model.<locals>.<dictcomp>í   sG   ø€ ð Jð Jð JØ03ð  $œ|­C°©H¬H°q©LÔ9Ø$'¨!¢GðJð Jð Jr   c              3   ó.   •K  — | ]}| ‰d          v V — ŒdS )r[   Nr   )r   rh   Úress     €r   r   z(SATSolver._find_model.<locals>.<genexpr>ó   s-   øè è € Ð%aÐ%a¸ s d¨c°!¬f nÐ%aÐ%aÐ%aÐ%aÐ%aÐ%ar   )Úflipped)Ú	_simplifyr7   rR   r:   r9   rP   Údecisionr@   r$   r5   Ú
assert_litÚcheckÚreset_boundsrH   ÚanyÚ_undoro   rT   rO   rL   rN   Ú_assign_literalrI   rK   )rW   Úflip_varÚfuncrh   Úenc_varÚflip_litrn   s   `     @r   r   zSATSolver._find_model«   s›  øøè è € ð8 ˆð 	�ŠÑÔÐØÔð 	ØˆFðN	 àÔ! D¤MÑ1°QÒ6Ð6Ø Ô1ð ð �DØ�D‘F”F�F�Fàð ,/à �ØÔ)Ô2�‘ð ×)Ò)Ñ+Ô+�ØÐ"Ô" aÑ'Ð"Ô"ð ˜’8‘8ð ”xð #Ø'+Ô'8ð &ð &˜GØ"&¤(×"5Ò"5°gÑ">Ô">˜CØ"˜Ø % ð  /à"œhŸnšnÑ.Ô.˜Øœ×-Ò-Ñ/Ô/Ð/Ð/à"˜Ø�{ c¨!¤f�{ðJð Jð Jð JØ7;Ô7HðJñ Jô Jð Jð Jð Jð Jð ×7Ò7¸¸A¼Ñ?Ô?Ð?õ #&Ð%aÐ%aÐ%aÐ%aÀÔ@SÔ@`Ð%aÑ%aÔ%aÑ"aÔ"að )Ø ŸJšJ™LœL˜Lõ #&Ð%aÐ%aÐ%aÐ%aÀÔ@SÔ@`Ð%aÑ%aÔ%aÑ"aÔ"að )ð Ô-Ô5ð %ØŸ
š
™œ˜ð Ô-Ô5ð %å˜4œ;Ñ'Ô'¨1Ò,Ð,Ø˜Ø $Ô 3Ô <Ð<�HØ—J’J‘L”L�LØ”K×&Ò&¥u¨X¸tÐ'DÑ'DÔ'DÑEÔEÐEØ#�HÙð ”×"Ò"¥5¨¡:¤:Ñ.Ô.Ð.ð × Ò  Ñ%Ô%Ð%ð �NŠNÑÔÐð Ô"ð  à&+�Ô#ð Ô)Ô1ð Ø—J’J‘L”L�Lð �C ¤Ñ,Ô,Ò,Ð,Ø˜ð Ô)Ô1ð ð ×'Ò'¨×(=Ò(=Ñ(?Ô(?Ñ@Ô@Ð@ð !Ô/Ô8Ð8�Ø—
’
‘”�Ø”×"Ò"¥5¨¸4Ð#@Ñ#@Ô#@ÑAÔAÐAØ�ñ]N	 r   c                 ó   — | 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}

        rd   ©rO   ©rW   s    r   rP   zSATSolver._current_level"  s   € ð& Œ{˜2ŒÐr   c                 ó>   — | j         |         D ]}|| j        v r dS Œ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)rU   r5   ©rW   Úclsrh   s      r   Ú_clause_satzSATSolver._clause_sat7  s9   € ð$ ”< Ô$ð 	ð 	ˆCØ�dÔ'Ð'Ð'Ø�t�tð (àˆur   c                 ó    — || j         |         v 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

        )r\   )rW   rh   r�   s      r   Ú_is_sentinelzSATSolver._is_sentinelN  s   € ð" �d”n SÔ)Ð)Ð)r   c                 ó”  — | j                              |¦  «         | j        j                              |¦  «         d| j        t	          |¦  «        <   |                      |¦  «         t          | j        |          ¦  «        }|D ]Ä}|                      |¦  «        s­d}| j	        |         D ]�}|| k    rx|  
                    ||¦  «        r|}Œ"| j        t	          |¦  «                 sE| j        |                               |¦  «         | j        |                              |¦  «         d} nŒ‚|r| j                             |¦  «         ŒÅd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)r5   rf   rP   r_   rk   rB   r;   r\   r‚   rU   r„   Úremover8   rL   )rW   rh   Úsentinel_listr�   Úother_sentinelÚnewlits         r   rw   zSATSolver._assign_literala  sg  € ð> 	Ô×Ò˜cÑ"Ô"Ð"ØÔÔ(×,Ò,¨SÑ1Ô1Ð1Ø&*ˆÔ�#˜c™(œ(Ñ#Ø×Ò˜sÑ#Ô#Ð#å˜Tœ^¨S¨DÔ1Ñ2Ô2ˆà ð 	Að 	AˆCØ×#Ò# CÑ(Ô(ð AØ!%�Ø"œl¨3Ô/ð "ð "�FØ # ’~�~Ø×,Ò,¨V°SÑ9Ô9ð "Ø-3˜N˜NØ!%Ô!2µ3°v±;´;Ô!?ð "Ø œN¨C¨4Ô0×7Ò7¸Ñ<Ô<Ð<Ø œN¨6Ô2×6Ò6°sÑ;Ô;Ð;Ø-1˜NØ!˜Eøð "ð AØÔ)×0Ò0°Ñ@Ô@Ð@øð	Að 	Ar   c                 óâ   — | j         j        D ]H}| j                             |¦  «         |                      |¦  «         d| j        t          |¦  «        <   ŒI| 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)rP   r5   r†   rD   r_   rk   rO   Úpop©rW   rh   s     r   rv   zSATSolver._undo˜  st   € ð, Ô&Ô3ð 	0ð 	0ˆCØÔ×$Ò$ SÑ)Ô)Ð)Ø×Ò Ñ$Ô$Ð$Ø*/ˆDÔ�c #™hœhÑ'Ð'ð 	Œ�ŠÑÔÐÐÐr   c                 óv   — d}|r4d}||                       ¦   «         z  }||                      ¦   «         z  }|°2dS 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)rW   Úchangeds     r   rp   zSATSolver._simplify¾  s^   € ð. ˆØð 	,ØˆGØ�t—’Ñ(Ô(Ñ(ˆGØ�t×)Ò)Ñ+Ô+Ñ+ˆGð ð 	,ð 	,ð 	,ð 	,ð 	,r   c                 óâ   — t          | j        ¦  «        dk    }| j        rO| j                             ¦   «         }| | j        v rd| _        g | _        dS |                      |¦  «         | j        °O|S )z/Perform unit propagation on the current theory.r   TF)rT   r8   r‹   r5   r7   rw   )rW   ÚresultÚnext_lits      r   rŽ   zSATSolver._unit_propÛ  sƒ   € å�TÔ*Ñ+Ô+¨aÒ/ˆØÔ#ð 	/ØÔ,×0Ò0Ñ2Ô2ˆHØˆy˜DÔ-Ð-Ð-Ø&*�Ô#Ø(*�Ô%Ø�uà×$Ò$ XÑ.Ô.Ð.ð Ô#ð 	/ð ˆr   c                 ó   — dS )z2Look for pure literals and assign them when found.Fr   r~   s    r   r�   zSATSolver._pure_literalé  s   € àˆur   c                 óˆ  — g | _         i | _        t          dt          | j        ¦  «        ¦  «        D ]�}t          | j        |          ¦  «        | j        |<   t          | j        |           ¦  «        | j        | <   t          | j         | j        |         |f¦  «         t          | j         | j        |          | f¦  «         Œ‘dS )z>Initialize the data structures needed for the VSIDS heuristic.r[   N)Úlit_heapÚ
lit_scoresÚrangerT   r_   Úfloatr^   r   )rW   Úvars     r   r>   zSATSolver._vsids_initð  sÇ   € àˆŒØˆŒå˜�C Ô 1Ñ2Ô2Ñ3Ô3ð 	Cð 	CˆCÝ#(¨$Ô*?ÀÔ*DÐ)DÑ#EÔ#EˆDŒO˜CÑ Ý$)¨4Ô+@À#ÀÔ+FÐ*FÑ$GÔ$GˆDŒO˜S˜DÑ!Ý�T”] T¤_°SÔ%9¸3Ð$?Ñ@Ô@Ð@Ý�T”] T¤_°c°TÔ%:¸S¸DÐ$AÑBÔBÐBÐBð		Cð 	Cr   c                 óh   — | j                              ¦   «         D ]}| j         |xx         dz  cc<   Œ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)r—   ÚkeysrŒ   s     r   Ú_vsids_decayzSATSolver._vsids_decayû  sL   € ð* ”?×'Ò'Ñ)Ô)ð 	(ð 	(ˆCØŒO˜CÐ Ð Ô  CÑ'Ð Ð Ñ Ð ð	(ð 	(r   c                 ór  — t          | j        ¦  «        dk    rdS | j        t          | j        d         d         ¦  «                 rYt	          | j        ¦  «         t          | j        ¦  «        dk    rdS | j        t          | j        d         d         ¦  «                 °Yt	          | 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   r[   )rT   r–   r_   rk   r   r~   s    r   r?   zSATSolver._vsids_calculate  s«   € õ* ˆtŒ}ÑÔ Ò"Ð"Ø�1ð Ô¥ D¤M°!Ô$4°QÔ$7Ñ 8Ô 8Ô9ð 	Ý�D”MÑ"Ô"Ð"Ý�4”=Ñ!Ô! QÒ&Ð&Ø�qð Ô¥ D¤M°!Ô$4°QÔ$7Ñ 8Ô 8Ô9ð 	õ
 �t”}Ñ%Ô% aÔ(Ð(r   c                 ó   — dS )z;Handle the assignment of a literal for the VSIDS heuristic.Nr   rŒ   s     r   rA   zSATSolver._vsids_lit_assigned3  ó   € àˆr   c                 ó°   — 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)rk   r   r–   r—   )rW   rh   rš   s      r   rC   zSATSolver._vsids_lit_unset7  sU   € õ& �#‰hŒhˆÝ�” ¤°Ô!5°sÐ ;Ñ<Ô<Ð<Ý�” ¤°#°Ô!6¸¸Ð =Ñ>Ô>Ð>Ð>Ð>r   c                 óZ   — | xj         dz  c_         |D ]}| j        |xx         dz  cc<   Œ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}

        r[   N)rS   r—   r€   s      r   rE   zSATSolver._vsids_clause_addedN  sR   € ð. 	Ð Ô  AÑ%Ð Ô Øð 	&ð 	&ˆCØŒO˜CÐ Ð Ô  AÑ%Ð Ð Ñ Ð ð	&ð 	&r   c                 óX  — t          | j        ¦  «        }| j                             |¦  «         |D ]}| j        |xx         dz  cc<   Œ| 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}}

        r[   r   rd   N)rT   rU   rL   r^   r\   rf   rF   )rW   r�   Úcls_numrh   s       r   rH   z$SATSolver._simple_add_learned_clausel  s²   € õ2 �d”lÑ#Ô#ˆØŒ×Ò˜CÑ Ô Ð àð 	,ð 	,ˆCØÔ! #Ð&Ð&Ô&¨!Ñ+Ð&Ð&Ñ&Ð&àŒ�s˜1”vÔ×"Ò" 7Ñ+Ô+Ð+ØŒ�s˜2”wÔ×#Ò# GÑ,Ô,Ð,à×Ò˜sÑ#Ô#Ð#Ð#Ð#r   c                 ó4   — 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                 ó   — g | ]
}|j          ‘ŒS r   )rq   )r   Úlevels     r   rc   z6SATSolver._simple_compute_conflict.<locals>.<listcomp>   s   € Ð?Ð?Ð? e�%”.Ð!Ð?Ð?Ð?r   r[   Nr}   r~   s    r   rJ   z"SATSolver._simple_compute_conflict�  s#   € ð  @Ð?¨t¬{¸1¸2¸2¬Ð?Ñ?Ô?Ð?r   c                 ó   — dS )zClean up learned clauses.Nr   r~   s    r   rM   zSATSolver._simple_clean_clauses¢  r    r   )Nr,   r-   r.   N)Ú__name__Ú
__module__Ú__qualname__Ú__doc__rY   r<   r=   r   ÚpropertyrP   r‚   r„   rw   rv   rp   rŽ   r�   r>   r�   r?   rA   rC   rE   rH   rJ   rM   r   r   r   r   r   R   sŽ  € € € € € ðð ð BFØDGØ"ð3ð 3ð 3ð 3ðj;ð ;ð ;ð0ð 0ð 0ð.r ð r ð r ðn ðð ñ „Xðð(ð ð ð.*ð *ð *ð&5Að 5Að 5Aðnð ð ðBð
,ð ,ð ,ð:ð ð ðð ð ð	Cð 	Cð 	Cð(ð (ð (ð0)ð )ð )ð@ð ð ð?ð ?ð ?ð.&ð &ð &ð<"$ð "$ð "$ðH@ð @ð @ð$ð ð ð ð r   r   c                   ó   — e Zd ZdZdd„ZdS )rN   z‚
    Represents a single level in the DPLL algorithm, and contains
    enough information for a sound backtracking procedure.
    Fc                 óH   — || _         t          ¦   «         | _        || _        d S r   )rq   r   r5   ro   )rW   rq   ro   s      r   rY   zLevel.__init__­  s    € Ø ˆŒÝ™EœEˆÔØˆŒˆˆr   Nr   )r©   rª   r«   r¬   rY   r   r   r   rN   rN   §  s2   € € € € € ðð ð
ð ð ð ð ð r   rN   N)FF)r¬   Úcollectionsr   Úheapqr   r   Úsympy.core.sortingr   Úsympy.assumptions.cnfr   Ú!sympy.logic.algorithms.lra_theoryr   r(   r   r   rN   r   r   r   ú<module>rµ      sø   ðð	ð 	ð $Ð #Ð #Ð #Ð #Ð #Ø #Ð #Ð #Ð #Ð #Ð #Ð #Ð #à &Ð &Ð &Ð &Ð &Ð &Ø ,Ð ,Ð ,Ð ,Ð ,Ð ,à 7Ð 7Ð 7Ð 7Ð 7Ð 7ð*ð *ð *ð *ðdð ð ðR	ð R	ð R	ð R	ð R	ñ R	ô R	ð R	ðj	ð 	ð 	ð 	ð 	ñ 	ô 	ð 	ð 	ð 	r   