Darshan Nayak

Full Stack Developer

Binary CSP Generation and Solution Search

Languages/Libraries: Java

The purpose of this application was to generate a random and consistent binary Constraint Satisfaction Problem (CSP), apply Arc Consistency, and use 3 different consistency searching strategies. This was an assignment for CS 820 (Artificial Intelligence) at University of Regina.

Search Strategies: Standard Backtrack, Forward Check, and Full Look Ahead.

Main.java

Following function code shows how Arc Consistency is performed in the program.

						
public static void performArcConsistency()  //this function will perform AC and remove possible domain values from variables
{
	int markerForFinalDeletion;   //this is a counter (decremented, instead of incrementation) to keep a track of all elements that need to be removed at the end of this function
	for (ConstraintVariablePair item : incompatibleConstraintVariablePairsList) //for each of the constraint
	{
		markerForFinalDeletion = 0;
		for (Integer subItem : item.variablePair[0].domain)   //for all domain values of variable on left in the constraint
		{
			int flagToRemove_i_FromItem = 0;
			for (Integer subSubItem:item.variablePair[1].domain)   //for all domain values of variable on right in the constraint
			{
				markerForFinalDeletion--;
				ConstraintValuePair temp = new ConstraintValuePair(subItem, subSubItem, subItem + "," + subSubItem);
				if (doesListContainElement(item.incompatibleValuePairList, temp))
				{
					//IF THE CURRENT VALUES FOR THE TWO VARIABLES EXISTS IN THE INCOMPATIBLE TUPLES, INCREASE THE COUNTER
					flagToRemove_i_FromItem++;
				}
				if (flagToRemove_i_FromItem == item.variablePair[1].domain.size())
				{
					//IF ALL THE VALUE COMBINATIONS OF TWO VARIABLES FOR CURRENT i EXIST IN THE INCOMPATIBLE TUPLES, THEN WE NEED TO REMOVE i FROM DOMAIN OF FIRST VARIABLE
					int tempIndex = item.variablePair[0].domain.indexOf(subItem);
					item.variablePair[0].domain.set(tempIndex, markerForFinalDeletion); //element with value -1 and lower are deleted at the end
				}
				
			}
		}
		for (int i = 0; i < (domainSize*domainSize); i++)  //this is where the values are actually deleted
		{
			if (markerForFinalDeletion == 0)
				break;  //so that elements >=0 are not deleted
			item.variablePair[0].domain.remove((Integer)markerForFinalDeletion);
			markerForFinalDeletion++;
			
		}
		
		
	}
	
}
						
                  

Following function code deals with performing solution search using Standard Back-Tracking

						
public static boolean continueSolutionSearch_SBT(Node currentNode)  //solution search for  Standard Backtracking
{
	boolean flagDie;                //used to store the return value for when a solution is found. Consider it as a kill-variable for recursion
	int counterVariableNotNull = 0;   //used as a counter to find solution node
	boolean includeInStack = true;    //if a bad child, don't push in stack and don't create children
	for (Variable item : currentNode.nodeVariables)
	{
		if (item.currentValue != null) //if all the variables have a value set, then it is a solution
			counterVariableNotNull++;
		
	}
	if (counterVariableNotNull == currentNode.nodeVariables.length)    //found the solution
	{
		//solutionNodeSBT = currentNode;
		return true;
	}
	else
	{
		counterVariableNotNull = 0;
		nodeArrayList_SBTTrace.add(stackSBT.pop());                 //removing the node from stack to expand it
		
		if (nodeArrayList_SBTTrace != null && !nodeArrayList_SBTTrace.isEmpty() && currentNode.levelInTree != Node.maxLevelOfTree)
		{
			Node pregnantNode = nodeArrayList_SBTTrace.get(nodeArrayList_SBTTrace.size() - 1);  //this is the node whose children will be created
			for (int i = 0; i < pregnantNode.nodeVariables[pregnantNode.levelInTree].domain.size(); i++)   //x children will be created, where x = number of domain values for that Variable
			{
				Node childNode = new Node(pregnantNode.nodeVariables,(nodeArrayList_SBTTrace.size() - 1), pregnantNode.levelInTree + 1);
				childNode.nodeVariables[pregnantNode.levelInTree].currentValue = childNode.nodeVariables[pregnantNode.levelInTree].domain.get(i);
				if (childNode.levelInTree == 1)
				{
					stackSBT.push(childNode);   //For nodes in level 1, we don't need to check its constraint satisfaction because it is the only variable, so we directly push in stack
				}
				else
				{
					for (int i1 = 0; i1 < pregnantNode.levelInTree; i1++)  //If the current child's level is x in tree, then we need to check constraints with x-1 variables
					{
						//for every variable pair, we will create a constraing variable pair and check if such a pair exists. If it doesn, then we check if the current values cause a conflict
						ConstraintVariablePair tempVariablePair = new ConstraintVariablePair(childNode.nodeVariables[i1], childNode.nodeVariables[pregnantNode.levelInTree], childNode.nodeVariables[i1].name + "," + childNode.nodeVariables[pregnantNode.levelInTree].name);
						if (doesListContainVariableAndValuePair(incompatibleConstraintVariablePairsList, tempVariablePair))
						{
							//the current value has constraint with some variable, hence, it should not be included in the stack
							includeInStack = false;
						}
					}
					if (includeInStack)  //if the child node does not violate any constraints, then it is good and pushed
					{
						stackSBT.push(childNode);
						if (childNode.levelInTree == Node.maxLevelOfTree)  //we are checking if the child is the solution node we are looking for
						{
							for (Variable item : childNode.nodeVariables)
							{
								if (item.currentValue != null)
									counterVariableNotNull++;           //if all the variables have a value set, then it is a solution

							}

							if (counterVariableNotNull == currentNode.nodeVariables.length)    //found the solution
							{
								solutionNodeSBT = new Node(childNode.nodeVariables,(nodeArrayList_SBTTrace.size()-1), pregnantNode.levelInTree);
								return true;
							}
						}
					}
					else
					{
						includeInStack = true;    //resetting the flag for the next child
					}
				}
			}
		}
		if (!stackSBT.empty())
		{
			flagDie = continueSolutionSearch_SBT(stackSBT.peek());    //recursive call
			if (flagDie && solutionNodeSBT != null)
				return true;
		}
		
	}
	return false;
}