From 8a02ea1a528a707b61b5824e7b067368fb3e4290 Mon Sep 17 00:00:00 2001
From: Hamed Gorjiara <hgorjiar@uci.edu>
Date: Thu, 26 Jul 2018 14:27:21 -0700
Subject: [PATCH] Performance improvement in nqueens

---
 nqueens/nqueens.cc | 25 ++++++++++++++++++++++++-
 1 file changed, 24 insertions(+), 1 deletion(-)

diff --git a/nqueens/nqueens.cc b/nqueens/nqueens.cc
index 56fa2f6e..48b1068c 100644
--- a/nqueens/nqueens.cc
+++ b/nqueens/nqueens.cc
@@ -337,6 +337,29 @@ void differentInEachRow(CSolver* solver, int N, vector<Element*> &elems){
 
 }
 
+void oneQueenInEachRow(CSolver* solver, vector<Element*> &elems){
+	Predicate *eq = solver->createPredicateOperator(SATC_EQUALS);
+	int N = elems.size();
+	for(int i=0; i<N; i++){
+		vector<BooleanEdge> rowConstr;
+		for(int j=0; j<N; j++){
+			Element* e1 = elems[j];
+			Element* e2 = solver->getElementConst(3, (uint64_t) i);
+			Element* in[] = {e1, e2};
+                        BooleanEdge equals = solver->applyPredicate(eq, in, 2);
+                        rowConstr.push_back(equals);
+		}
+		if(rowConstr.size()>0){
+			solver->addConstraint(solver->applyLogicalOperation(SATC_OR, &rowConstr[0], rowConstr.size()) );
+		}
+	}
+}
+
+void generateRowConstraints(CSolver* solver, int N, vector<Element*> &elems){
+	oneQueenInEachRow(solver, elems);
+	differentInEachRow(solver, N, elems);
+}
+
 void diagonallyDifferentConstraint(CSolver *solver, int N, vector<Element*> &elems){
 	Predicate *eq = solver->createPredicateOperator(SATC_EQUALS);
 	for(int i=N-1; i>0; i--){
@@ -399,7 +422,7 @@ void csolverNQueens(int N){
 		elems.push_back(solver->getElementVar(domainSet));
 	}
 	mustHaveValueConstraint(solver, elems);
-	differentInEachRow(solver, N, elems);
+	generateRowConstraints(solver, N, elems);
 	diagonallyDifferentConstraintBothDir(solver, N, elems);
 //	solver->printConstraints();
 //	solver->serialize();
-- 
2.34.1