YOUR ANSWER HERE

SAT problems are represented by noting down $($a$)$ the number of variables $$

$,($b$)$ the number of clauses $$

$,$ and $($c$)$ for each clause, the list of literals $($variables or their negations$).$

We will use a data structure in python that has the following fields:

n: the number of variables.

clauses : a list of clauses $--[$c$0,...,$cm$-1]$

Each clause ci is itself a list ci: $[$l$1,$ l$2,..,$ lk$]$ wherein li is a positive number between $1$ to n representing the variable $$

OR a negative number between $-$n and $-1$ representing the literal $$

$.$

Example

Let's revisit the problem from previous example. It is represented as

n$=4$

clauses$=[[1,2,-4],[-2,-3,1],[-1,-2,-3]]$

We have provided a data$-$structure called SATInstance. Your goal is to complete the function evaluate that inputs a partial truth assignment: a dictionary that maps variable numbers from $1-$ n $($inclusive$)$ to true$/$false$.$ If a variable is unmapped then it is not assigned to either value.

evaluate should return $-1$ if the partial truth assignment already violates a clause.

evaluate should return $0$ if the partial truth assignment neither violates nor satisfies the formula.

evaluate should return $+1$ if the partial truth assignment satisfies each and every clause in the formula.

Example $1$

Revisiting the example above, let us take the partial assignment $1$true

$.$ It leaves $2,3,4$

unassigned.

Under this assignment:

The clause $124$

is true since $1$

is true.

The clause $231$

is true since $1$

is true.

The clause $123$

is unresolved since $1$

is false and we do not know what $2$

or $3$

are.

Therefore your function evaluate must return $0$

since at least one clause is unresolved and remaining clauses are all true.

Example $2$

Revisiting the example above, let us take the partial assignment $1$true$,2$false

$.$ It leaves $3,4$

unassigned. Under this assignment:

The clause $124$

is true since $1$

is true.

The clause $231$

is true since $1$

is true.

The clause $123$

is true because $2$

is false and the clause has $2$

$.$

Since all clauses are true, the formula is already satisfied even though we do not know at $3,4$

are. evaluate must return $+1$ for this formula and partial truth assignment.

Example $3$

Revisiting the example above, let us take the partial assignment $1$true$,2$true$,3$true

$.$ It leaves $4$

unassigned. Under this assignment:

The clause $124$

is true since $1$

is true.

The clause $231$

is true since $1$

is true.

The clause $123$

is false since $1,$

x$\_2,$ x$\_3$$ are true.

Since at least one clause is false, the formula is already violated even though we do not know what $4$

is$.$ evaluate must return $-1$ for this formula and partial truth assignment.