Algorithms For Dummies

Implementing the Python code

To solve the 2-SAT problem using Python and the RandomWalkSAT algorithm, 

you  need  to  set  a  few  helpful  functions.  The 

create_clauses

 and 

signed

 

 functions help generate a circuit problem to solve by handling the 

OR

 and 

NOT

 

gates, respectively. Using these functions, you specify the number of OR gates 

and provide a seed number that guarantees that you can recreate the resulting 

problem later (allowing you to try the problem multiple times and on different 

computers).

The 

create_random_solutions

 function provides a cold problem start by  providing 

a random solution that sets the inputs. The chances of finding the right solution 

using random luck is slim (one out of the power of two to the number of gates), but 

on  average,  you  can  expect  that  three  quarters  of  the  gates  are  correctly  set 

(because, as seen using the truth table for the OR function, three inputs out of four 

possible are 

True

). The 

check_solution

 function determines when the  circuit is 

satisfied  (indicating  a  correct  solution).  Otherwise,  it  outputs  what  conditions 

aren’t satisfied. (You can find this code in the 

A4D; 18; Local Search.ipynb 

file 

---

CHAPTER 18