Having no idea how to start to write 3 sat problem in c++ Can anyone give me a l
ID: 3852624 • Letter: H
Question
Having no idea how to start to write 3 sat problem in c++ Can anyone give me a little help
2 Project
For this project you will be writing a 3SAT generator, that can also test given truth values. That is, the goal of this program is to create a general 3SAT problem with at most 10 variables and 10 clauses. Your program will then print this logical expression so the user can see it (you will use as opposed to ¬) and then ask the user for truth values for each of the variables. Then it will test whether those truth values make the whole expression TRUE or not. If they do make the expression TRUE, you should inform the user. If they do not, you again inform the user AND print the clause which is invalid.
3 Expectations
Each run of the program should randomly choose the number of possible variables (between 3 and 10 variables is allowed) it should also randomly choose the number of clauses (between 1 and 10 is allowed). Within a clause, a variable should not be repeated, ever. That is, (x1x1x2) is not a valid clause, neither is (x2¬x2x3). But of course variables can be repeated between other clauses. After choosing the number of variables and clauses, each clause should be generated randomly. You may represent this generation anyway that you like. The standard way to represent a clause is to use a list (in Python) or an int[] in C++. For example: (x1 x2 x3) can be represented as [1,2,3], and (¬x2 x1 ¬x5) can be represented as [-2,1,-5], that is, negative numbers represent a negated variable. One way to randomly generate clauses is for each clause randomly choose a number between 1 and the number of variables. This selects your xk, then you should also randomly decide whether or not to negate this variable, you can do this as a 50/50 chance. After randomly generating all of the clauses, your program should print this clause to the screen. Since you cannot directly print ¬ you will use as an alternative. Similarly subscripts are not possible, so you will just place numbers next to an x. You will print something like this: ( x5 x2 x1) (x2 x5 x6) ( x8 x1 x3) (x9 x7 x4) That is, you MUST print parentheses and and , use v and ˆ for these (it will, ironically, look better printed by your program than by LATEX). After printing the expression you will ask the user for T/F values for each variable. You MUST ensure input is correct! If I enter: s, (instead of T/F) then you should ask again until I successfully choose T/F. However you should allow upper OR lower case, that is, valid inputs are T,t,F,f. Any other inputs are to be ignored and you should re-ask. After asking for user input for EVERY variable, you should evaluate whether the values that were given do or do not satisfy the generated expression. Then you should inform the user whether they were correct or not, you may use any message you like to inform the user. But if they were incorrect you MUST 2 also print the clause that is evaluated to FALSE (and ONLY that clause). It is possible that many clauses fail, you should print the FIRST clause which fails. You should not use any external libraries to evaluate the 3SAT expression. There are many 3SAT solvers in most languages, you should not use these. Programs that do use them will be penalized, harshly. Keep in mind the goal of this project is not to solve a 3SAT expression, but to generate one, and verify a given solution
This is a example result
./Projectl Please enter a value T/F for variable x1: t Please enter a value T/F for variable x2: F Please enter a value T/F for variable x3: F Please enter a value T/F for variable x4:T Please enter a value T/F for variable x5:T Please enter a value T/F for variable x6: F Please enter a value T/F for variable x7:F This assignment is false, due to the clause:Explanation / Answer
Here is the complete code for the question. For the purpose of testing, you can change the value of MAX_VARS to 4 in the code (#define on top)
This will generate only expressions with 3 or 4 variable clauses in the expression. This would be easy to evaluate manually. The current value of MAX_VARS is 10 as indicated in the question.
In case of any issues, please post a comment and I shall respond. If you are happy with the progam, request to rate the answer. Thank you very much.
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cctype>
#define MIN_VARS 3
#define MAX_VARS 10
#define MIN_CLAUSES 1
#define MAX_CLAUSES 10
using namespace std;
class clause
{
private:
int variables[MAX_VARS];
int size; //represents the number of variables in this clause
public:
clause()
{
size = 0;
}
void setVariable(int i, int var ) //set the variable i in the clause to specified one
{
variables[i] = var;
}
void setSize(int s) // set the number of variables in this clause
{
size = s;
}
void print() //prints the clause
{
cout << " ( ";
for(int i = 0; i < size; i++)
{
if(i != 0)
cout << " v ";
if(variables[i] < 0)
cout << "~" << "x" << -variables[i];
else
cout << "x" << variables[i];
}
cout <<" ) ";
}
// the truth values for x1, x2 ... are passed and the clause is evaluated based on these, the 1st location of truthValues is unused
bool evaluate(bool truthValues[])
{
int idx ;
bool val = false, current;
for(int i = 0; i < size; i++)
{
idx = variables[i];
if(variables[i] < 0)
{
idx = -idx; //conver to +ve and negate the truth value
current = !truthValues[idx];
}
else
current = truthValues[idx];
val = val || current;
}
return val;
}
};
//generates variables for this clause and sets its size,. expr_var_used represents the variables that are used in the final expression
//after generating the variables, these variables are set in expr_var_used
void generateVars(clause &c, int expr_var_used[], int numVars);
bool getBoolInput(string prompt); //used to prompt the user for a boolean input and validate it
int main()
{
int numClauses, numVars;
srand(time(0));
int clause_range = MAX_CLAUSES - MIN_CLAUSES + 1;
numClauses = MIN_CLAUSES + (rand() % clause_range); //generates random number between MIN_CLAUSES to MAX_CLAUSES
int var_range = MAX_VARS - MIN_VARS + 1;
numVars = MIN_VARS + (rand() % var_range); //generates random number between MIN_VARS to MAX_VARS
//numVars is the number of variables that will be in each clause
bool truth_values[MAX_VARS + 1]; //index 0 is unsed, 1 to MAX_VARS represnt the truth values of x1, x2,.. etc
int expr_used_vars[MAX_VARS + 1] = {0} ;
clause logicexpr[numClauses];
for(int i = 0; i < numClauses; i++)
{
generateVars(logicexpr[i], expr_used_vars, numVars); //generate the variables for this clause
}
//print the generated logic expression
for(int i = 0; i < numClauses; i++)
{
if(i != 0)
cout << " ^ " ;
logicexpr[i].print();
}
cout << endl << endl;
string prompt = "Please enter a value T/F for variable x";
//ask user for values of the variables that were used in the logical expression
for(int i = 1; i < MAX_VARS + 1; i++)
{
if(expr_used_vars[i] == 1) // was this used in any of the clauses ?
{
truth_values[i] = getBoolInput(prompt + to_string(i));
}
}
cout << endl;
bool expr_value = true;
int j;
for(j = 0; j < numClauses; j++ )
{
if(logicexpr[j].evaluate(truth_values) != true) // this clause did not evaluate to true? stop then
{
expr_value = false;
break;
}
}
if(expr_value)
cout << "This assignment is true. " << endl;
else
{
cout << "This assignment is false, due to the clause: " << endl;
logicexpr[j].print();
cout << endl;
}
}
bool getBoolInput(string prompt)
{
char val;
while(true)
{
cout << prompt << ": ";
cin >> val;
val = toupper(val);
if(val != 'T' && val != 'F')
cout << "invalid input. please try again." << endl;
else
break;
}
if(val == 'T')
return true;
else
return false;
}
void generateVars(clause &c, int expr_used_vars[], int numVars)
{
int usedVars[MAX_VARS + 1] = {0}; //if 0, corresponding var was not used in the clause, if 1 , the corresponindg var was used in the clause
int var;
c.setSize(numVars);
for(int i = 0; i < numVars; )
{
var = 1 + rand() % MAX_VARS; // generate a random variable
if(usedVars[var] == 1)//if the variable is already used, then continut to generate again
continue;
else
{
int negate = rand() % 2;
if(negate == 0)
c.setVariable(i, var);
else
c.setVariable(i, -var);
usedVars[var] = 1; //mark the variable number as used, so that we don't reuse the same variable in the clause
expr_used_vars [var] = 1; //mark the variable number that was used, so we can later ask user's input
i++;
}
}
}
output
( x2 v x1 v x4 ) ^ ( x1 v x2 v ~x3 ) ^ ( x3 v x2 v ~x4 ) ^ ( x1 v ~x4 v x3 ) ^ ( ~x4 v x3 v x1 ) ^ ( x2 v x3 v ~x4 ) ^ ( x4 v x3 v x2 ) ^ ( ~x4 v x1 v ~x2 ) ^ ( ~x4 v ~x2 v x1 ) ^ ( x2 v x1 v x3 )
Please enter a value T/F for variable x1: t
Please enter a value T/F for variable x2: f
Please enter a value T/F for variable x3: t
Please enter a value T/F for variable x4: f
This assignment is true.
===========
( x3 v x4 v x2 v x1 ) ^ ( ~x2 v x1 v ~x3 v x4 ) ^ ( x2 v ~x3 v x1 v ~x4 ) ^ ( ~x4 v x3 v ~x2 v x1 ) ^ ( ~x3 v ~x2 v ~x4 v ~x1 ) ^ ( ~x2 v ~x1 v x4 v x3 ) ^ ( ~x1 v ~x3 v ~x4 v ~x2 ) ^ ( x2 v x3 v x1 v x4 )
Please enter a value T/F for variable x1: f
Please enter a value T/F for variable x2: f
Please enter a value T/F for variable x3: f
Please enter a value T/F for variable x4: f
This assignment is false, due to the clause:
( x3 v x4 v x2 v x1 )
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.