Please check the attached file
2-SAT Assignment Consider a collection of M lightbulbs and N switches. The switches can be placed either in a down or up position. Each lightbulb is connected to two of the switches and it can only be turned off if the two switches connected to it assume a specific configuration. We ask if there is a configuration of the switches (down or up for each) so that all of the lightbulbs are on simultaneously. Suppose we represent the N switches as integers 1 through N. We represent each lightbulb as a pair of integers which encodes the configuration which avoids the lightbulb to be turned off. We will encode the up and down positions by using positive and negative integers. So, if a lightbulb is represented by the pair (i, -j), then this means the lightbulb is connected to switches i and j. If switch i is in the down position and switch j is in the up position, then the lightbulb is off, otherwise the lightbulb will be on. Example 1: Suppose we have 3 switches (represented as [1,2,3]) and 2 lightbulbs. Suppose the first lightbulb is connected to switches 1 and 2 while the second lightbulb is connected to switches 1 and 3. Assume that the first lightbulb can only be turned off if and only if both switches 1 and 2 are in the down position. We encode this as [1,2]. Assume that the second lightbulb can only be turned off if and only switch 1 is in the up position and switch 3 is in the down position. We encode this as [-1,3] where the negative sign encodes the down position for switch 1. We represent this instance of the problem in a file as follows: 3 2 1 2 -1 3 The first line states that there are 3 switches. The second line states that there are 2 lightbulbs. The next two lines represent the critical configurations for the 2 lightbulbs. Answer: If we use a configuration where switch 1 on, switch 2 off, and switch 3 on, then the 2 lightbulbs are simultaneously on. This "positive" configuration is represented as [1,-2,3]. Example 2: Consider another instance of the problem: 3 4 1 2 1 -2 -1 3 -1 -3 So there are 3 switches and 4 lightbulbs. The next four lines represent the critical configurations for the 4 lightbulbs. Answer: In this case, there is no configuration of the switches which allows all lightbulbs to be on. In summary, if there are N switches and M lightbulbs, then the file encoding contains M+2 lines where the first two lines contain the numbers N and M. The next M lines contain pairs of signed integers from the set -N,-N+1,..,-1,0,1,..,N. Two sample files with 500 switches and 5000 lightbulbs: instance1 and instance2. Two additional sample files with 1000 switches and at least 10000 lightbulbs: instance3 and instance4. PROBLEM Given an instance of this lightbulb problem, determine if there is a configuration of the switches so that all lightbulbs are simultaneously on. If the answer is YES, then provide the sequence of up/down for each switch. If the answer is NO, provide a "proof" of this fact. What to Hand-in Your program should solve the problem in general but specify your solutions for all the sample files above. If the instance has no solution, your program should indicate which variable caused conflicts. If the instance has a solution, your program should output the solution as a sequence of signed integers (say, -1 2 3 -4 -5 6 etc.).