Chris Pollett > Students > Yunxuan
[Bio] [Blog] [Final Step of Shor's and Grover's Algorithms] [Threshold of Error Correction] [Random-kSAT-Generator: Version 1] [Random-kQSAT-Generator: Version 2] [Random-kQSAT-Generator: Version 3] [Antiferromagnetic Heisenberg Model] [Random-kQSAT-Generator: Version 4] [Random-kQSAT-Generator: Version 5] [Random-kQSAT-Generator: Version 6] [Thesis] |
I have modified the original SolveQ algorithm. The original Solveq program solves only 2-SAT problems. This version solves 2-QSAT problems. I also changed the Clause inner class slight. But most of the program is still the same concept. Note: The first parameter of a Clause must be less than the second parameter. import java.util.ArrayList; import static java.lang.Math.*; public class SolveQ2 { private boolean []settings = new boolean[6]; private ArrayList<Clause> Constraints = new ArrayList<Clause>(); //work with private ArrayList<Clause> Constraints2 = new ArrayList<Clause>(); //work with private ArrayList<Clause> Constraints3 = new ArrayList<Clause>(); private boolean [] solutions = new boolean[6]; private ArrayList<Clause> sum = new ArrayList<Clause>(); private ArrayList<Solution> chain = new ArrayList<Solution>(); private ArrayList<Solution> prelimchain = new ArrayList<Solution>(); private ArrayList<Solution> chain2 = new ArrayList<Solution>(); private ArrayList<Solution> chain3 = new ArrayList<Solution>(); private double threshold= .1; private double coefprod=1; private double coefprodcopy=1; private double coefprod2=1; private int count=0; private ArrayList<Solution> prevchain = new ArrayList<Solution>(); private ArrayList<Integer> alreadyChanged = new ArrayList<Integer>(); private int threshcount=1; private boolean firstime=true; public static void main (String [] args){ SolveQ2 sq = new SolveQ2(); sq.solveq(); } public void solveq (){ boolean [] vec = {false,false,false,false,false,false}; for (int i = 0; i < vec.length; i++){ settings[i] = vec[i]; } setConstraints(vec); sumConstraints(); preliminaries(); algorithm(); } public void setConstraints (boolean [] vec){ boolean [] vec1 = new boolean [solutions.length]; boolean [] vec2 = new boolean [solutions.length]; boolean [] vec3 = new boolean [solutions.length]; boolean [] vec4 = new boolean [solutions.length]; boolean [] vec5 = new boolean [solutions.length]; boolean [] vec6 = new boolean [solutions.length]; boolean [] vec7 = new boolean [solutions.length]; boolean [] vec8 = new boolean [solutions.length]; for (int k=0; k<solutions.length; k++){ //check. vec1[k] = vec[k]; vec2[k] = vec[k]; vec3[k] = vec[k]; vec4[k] = vec[k]; vec5[k] = vec[k]; vec6[k] = vec[k]; vec7[k] = vec[k]; vec8[k] = vec[k]; } //The alpha in the clause must be greater than 0.71 Clause A = new Clause (1,2,2,0.9, vec1); Clause A3 = new Clause (1,2,0,0.9, vec3); Clause E = new Clause (2,3,0,0.9, vec5); Clause E2 = new Clause (2,3,3,0.9, vec4); Clause A2 = new Clause (3,4,0,0.9, vec2); Clause F = new Clause (4,5,1,0.9, vec6); Clause G = new Clause (5,6,1,0.9, vec7); //Clause B = new Clause (4,5,2,0.9,vec1); //Clause C = new Clause (5,6,0,0.9,vec2); //Clause D = new Clause (4,6,1,0.9,vec3); //Clause H = new Clause (1,2,2,0.9, vec1); //Clause I = new Clause (1,2,0,0.9, vec2); //Clause J = new Clause (2,3,1,0.9, vec3); //Clause K = new Clause (2,4,1,0.9, vec4); Constraints.add(A); Constraints2.add(A); Constraints.add(A3); Constraints2.add(A3); //Constraints3.add(A); Constraints.add(E); Constraints2.add(E); //Constraints3.add(A2); //Constraints3.add(E); //Constraints.add(F); Constraints.add(E2); Constraints2.add(E2); Constraints.add(A2); Constraints2.add(A2); Constraints.add(F); Constraints2.add(F); Constraints.add(G); Constraints2.add(G); //Constraints3.add(G); //Constraints.add(D); //Constraints2.add(D); //Constraints.add(B); //Constraints2.add(B); //Constraints3.add(B); //Constraints.add(C); //Constraints2.add(C); //Constraints3.add(C); //Constraints.add(D); //Constraints2.add(D); //Constraints3.add(D); //Constraints.add(H); //Constraints2.add(H); //Constraints3.add(H); //Constraints.add(I); //Constraints2.add(I); //Constraints3.add(I); //Constraints.add(J); //Constraints2.add(J); //Constraints3.add(J); //Constraints.add(K); //Constraints2.add(K); //Constraints3.add(K); } public void sumConstraints (){ double [][]m; ArrayList<Clause>list; double alph=0; //first param. less than second param. for (int i = 0; i<solutions.length; i++){ for(int j = i; j<solutions.length; j++){ list = varSearch(i+1,j+1); if (list.size()>1) { //System.out.println("ls:"+list.size()); m = list.get(0).clause; alph+= list.get(0).alpha*list.get(0).alpha; int k = 1; while(k < list.size()){ m = Add(m, list.get(k).clause); alph+= list.get(k).alpha*list.get(k).alpha; k++; } alph/=list.size(); Clause A = new Clause(i+1, j+1, m, sqrt(alph)); sum.add(A); alph=0; } } } /*for(int i=0; i<sum.size(); i++){ double [][] mat= sum.get(i).clause; for(int j=0; j<mat.length; j++){ for(int k=0; k<mat.length; k++){ System.out.print(mat[j][k]+" "); } System.out.println(); } }*/ } public double [][] Add (double[][]M1, double[][]M2){ double [][] M5 = new double[M1.length][M1[0].length]; for (int i = 0; i<M1.length; i++){ for (int j = 0; j < M1[0].length; j++){ M5[i][j] = M1[i][j] + M2[i][j]; } } return M5; } public ArrayList<Clause> varSearch (int var1, int var2){ ArrayList <Clause>temp = new ArrayList<Clause>(); for(int k = 0; k < Constraints.size(); k++){ if (Constraints.get(k).var1==var1 && Constraints.get(k).var2==var2) temp.add(Constraints.get(k)); } return temp; } public void preliminaries(){ int rank = 1; double [][] temp; int nullvector = -1; boolean [] tempvec; boolean [][] tempvec2 = new boolean [2][solutions.length]; boolean [] vec = new boolean [solutions.length]; int i=0; while(sum.size()>0){ //System.out.println("s"+sum.size()); //System.out.println(sum.get(i).var1+" "+sum.get(i).var2); temp = sum.get(i).clause; rank = findRank(temp); //System.out.println(sum.get(i).var2+"rank"+rank); if (rank==4){ System.out.println("Unsolvable problem."); System.exit(0); } else if (rank==3){ int a = sum.get(i).var1-1; int b = sum.get(i).var2-1; tempvec = rank3Process(temp, a, b); coefprod*=sum.get(i).alpha; coefprodcopy*=sum.get(i).alpha; //System.out.println(coefprod); //i--; if(a!=b){ chain.add(new Solution(a+1, tempvec[a])); chain.add(new Solution(b+1, tempvec[b])); prelimchain.add(new Solution(a+1, tempvec[a])); prelimchain.add(new Solution(b+1, tempvec[b])); } else { double [][] mat= sum.get(i).clause; if(mat[0][0]==1 && mat[3][3]==1){ System.out.println("Unsolvable Problem"); System.exit(0); } else if(mat[0][0]==1){ chain.add(new Solution(a+1, true)); prelimchain.add(new Solution(a+1, true)); } else if(mat[3][3]==1){ chain.add(new Solution(a+1, false)); prelimchain.add(new Solution(a+1, false)); } } ArrayList<Clause> list = varSearch(a+1,b+1); for (int k=0; k<list.size(); k++){ Constraints.remove(list.get(k)); Constraints2.remove(list.get(k)); Constraints3.remove(list.get(k)); } sum.remove(i); } else if (rank==2){ int start = sum.get(i).var1-1; int end = sum.get(i).var2-1; coefprod*=sum.get(i).alpha; coefprodcopy*=sum.get(i).alpha; //System.out.println(""+" "+coefprod); if(start==end){ double [][] mat= sum.get(i).clause; if(mat[1][1]==0 && mat[2][2]==0){ System.out.println("Unsolvable problem."); System.exit(0); } else if(mat[2][2]==0 && mat[3][3]==0){ chain.add(new Solution(start+1, true)); prelimchain.add(new Solution(start+1, true)); } else if(mat[0][0]==0 && mat[1][1]==0){ chain.add(new Solution (start+1, false)); prelimchain.add(new Solution(start+1,false)); } else if(mat[0][0]==0 && mat[2][2]==0){ chain.add(new Solution(start+1, false)); prelimchain.add(new Solution(start+1, false)); } else if(mat[0][0]==0 && mat[3][3]==0){ //System.out.println("Unsolvable problem."); //System.exit(0); } else if(mat[1][1]==0 && mat[3][3]==0){ chain.add(new Solution(start+1, true)); prelimchain.add(new Solution(start+1, true)); } } else if(start!=end){ tempvec2=rank2Process(temp, start, end); boolean added=false; //System.out.println("cs:"+chain.size()); for (int s=0; s<chain.size(); s++){ if(chain.get(s).index==start+1) { //System.out.println("Here here"); if(chain.get(s).value!=tempvec2[0][start] && chain.get(s).value!=tempvec2[1][start]){ System.out.println("Unsolvable"); System.exit(0); } else if(chain.get(s).value==tempvec2[0][start]){ chain.add(new Solution(start+1, tempvec2[0][start], end+1)); chain.add(new Solution(end+1, tempvec2[0][end], start+1)); chain2.add(new Solution(start+1, tempvec2[1][start],end+1)); chain2.add(new Solution(end+1, tempvec2[1][end], start+1)); prelimchain.add(new Solution(start+1, tempvec2[0][start], end+1)); prelimchain.add(new Solution(end+1, tempvec2[0][end], start+1)); }else if(chain.get(s).value==tempvec2[1][start]){ chain.add(new Solution(start+1, tempvec2[1][start],end+1)); chain.add(new Solution(end+1, tempvec2[1][end], start+1)); chain2.add(new Solution(start+1, tempvec2[0][start], end+1)); chain2.add(new Solution(end+1, tempvec2[0][end], start+1)); prelimchain.add(new Solution(start+1, tempvec2[1][start], end+1)); prelimchain.add(new Solution(end+1, tempvec2[1][end], start+1)); } added=true; break; } else if(chain.get(s).index==end+1) { //System.out.println("here Here"); if(chain.get(s).value!=tempvec2[0][end] && chain.get(s).value!=tempvec2[1][end]){ System.out.println("Unsolvable"); System.exit(0); } else if(chain.get(s).value==tempvec2[0][end]){ chain.add(new Solution(start+1, tempvec2[0][start], end+1)); chain.add(new Solution(end+1, tempvec2[0][end], start+1)); chain2.add(new Solution(start+1, tempvec2[1][start],end+1)); chain2.add(new Solution(end+1, tempvec2[1][end], start+1)); prelimchain.add(new Solution(start+1, tempvec2[0][start], end+1)); prelimchain.add(new Solution(end+1, tempvec2[0][end], start+1)); }else if(chain.get(s).value==tempvec2[1][end]){ chain.add(new Solution(start+1, tempvec2[1][start],end+1)); chain.add(new Solution(end+1, tempvec2[1][end], start+1)); chain2.add(new Solution(start+1, tempvec2[0][start], end+1)); chain2.add(new Solution(end+1, tempvec2[0][end], start+1)); prelimchain.add(new Solution(start+1, tempvec2[1][start], end+1)); prelimchain.add(new Solution(end+1, tempvec2[1][end], start+1)); } added=true; break; } } if(!added){ chain.add(new Solution(start+1, tempvec2[0][start], end+1)); chain.add(new Solution(end+1, tempvec2[0][end], start+1)); chain2.add(new Solution(start+1, tempvec2[1][start],end+1)); chain2.add(new Solution(end+1, tempvec2[1][end], start+1)); prelimchain.add(new Solution(start+1, tempvec2[0][start], end+1)); prelimchain.add(new Solution(end+1, tempvec2[0][end], start+1)); added=false; } } ArrayList<Clause> list = varSearch(start+1,end+1); for (int k=0; k<list.size(); k++){ Constraints.remove(list.get(k)); Constraints2.remove(list.get(k)); Constraints3.remove(list.get(k)); } sum.remove(i); } else if(rank==1){ int a = sum.get(i).var1-1; int b = sum.get(i).var2-1; if(a==b){ double [][] mat= sum.get(i).clause; if(mat[1][1]==1|| mat[2][2]==1){ //System.out.println("Unsolvable Problem"); //System.exit(0); } else if(mat[0][0]==1){ chain.add(new Solution(a+1, true)); prelimchain.add(new Solution(a+1, true)); } else if(mat[3][3]==1){ chain.add(new Solution(a+1, false)); prelimchain.add(new Solution(a+1, false)); } ArrayList<Clause> list = varSearch(a+1,b+1); for (int k=0; k<list.size(); k++){ Constraints.remove(list.get(k)); Constraints2.remove(list.get(k)); Constraints3.remove(list.get(k)); } } sum.remove(i); } } } public int findRank(double [][]M4){ double []tempvec = new double[M4.length]; int [] zeros4 = new int [M4.length]; int count = 0; for (int i = 0; i<M4.length; i++){ zeros4[i] = zeroCount(M4[i]); } for(int i = 0; i < M4.length; i++){ if (zeros4[i]==M4.length){ count++; } } return (4-count); } public int zeroCount(double [] M){ boolean on = false; int lead = 0; for (int j = 0; j<M.length; j++){ if(M[j]==0 && !on){ on = true; } if(M[j]==0 && on){ lead = lead+1; } if (M[j]!=0){ break; } } return lead; } public boolean [] rank3Process (double[][]temp, int from, int to){ boolean [] tempvec = new boolean[solutions.length]; for(int i = 0; i < tempvec.length; i++){ tempvec[i] = false; } for(int j = 0; j < temp.length; j++){ if(zeroCount(temp[j])==4){ if (j==0){ tempvec[from] = false; tempvec[to] = false; } else if (j==1){ tempvec[from] = false; tempvec[to] = true; } else if (j==2){ tempvec[from] = true; tempvec[to] = false; } else { tempvec[from] = true; tempvec[to] = true; } } } return tempvec; } public boolean [][] rank2Process(double [][]temp, int from, int to){ boolean [][] tempvec = new boolean[2][solutions.length]; int count = 0; for (int j = 0; j<4 && count<2; j++){ if(zeroCount(temp[j])==4){ if (j==0){ tempvec[count][from] = false; tempvec[count][to] = false; } else if (j==1){ tempvec[count][from] = false; tempvec[count][to] = true; } else if (j==2){ tempvec[count][from] = true; tempvec[count][to] = false; } else { tempvec[count][from] = true; tempvec[count][to] = true; } count++; } } return tempvec; } public void recover(){ Clause tempor = Constraints.get(0); Constraints.remove(0); for(int s=0; s< Constraints3.size(); s++){ if(!Constraints.contains(Constraints3.get(s))){ Constraints.add(Constraints3.get(s)); } } chain = new ArrayList<Solution>(); for(int h=0; h<prelimchain.size(); h++){ chain.add(prelimchain.get(h)); } count=0; coefprod=coefprodcopy; runPrelim1(); } public boolean algorithm (){ while (Constraints.size()>0) { if(prelimchain.size()>0){ runPrelim1(); } int index=0; boolean needagain=false; while(Constraints.size()>0){ Clause cl= Constraints.get(index); int ind1 = cl.var1-1; int ind2 = cl.var2-1; int ind=findInOne(ind1); if(ind!=-1){ int next = cl.var2; ArrayList <Clause> temp3= var1Search(next); ArrayList <Clause> temp4= var2Search(next); if(temp4.size()>0 && temp4.get(0).var1==cl.var1 && temp4.get(0).var2==cl.var2) temp4.remove(0); if(temp3.size()>0){ Clause next1=temp3.get(0); if(cl.TM1[0]==chain.get(ind).value){ coefprod*=cl.alpha; chain.add(new Solution(ind2+1, cl.TM1[1])); } else if(next1.TM1[0]==!cl.TM1[1] && cl.TM1[0]==!chain.get(ind).value &&(coefprod*cl.beta)>threshold){ count++; coefprod*=cl.beta; chain.add(new Solution(ind2+1, !cl.TM1[1])); }else { if(findInTwo(ind1)!=-1 && !AlreadyChanged(ind1+1)) { changeValue(ind1+1); recover(); needagain=true; }else { System.out.println("Unsolvable"); System.exit(0); } } }else if(temp4.size()>0){ Clause next1=temp4.get(0); //System.out.println(next1.var1+" "+next1.var2); if(cl.TM1[0]==chain.get(ind).value){ coefprod*=cl.alpha; chain.add(new Solution(ind2+1, cl.TM1[1])); } else if(next1.TM2[0]==!cl.TM1[1] && !cl.TM1[0]==chain.get(ind).value && (coefprod*cl.beta)>threshold){ count++; coefprod*=cl.beta; chain.add(new Solution(ind2+1, !cl.TM1[1])); } else { if(findInTwo(ind1)!=-1 && !AlreadyChanged(ind1+1)) { changeValue(ind1+1); recover(); needagain=true; }else { System.out.println("Unsolvable"); System.exit(0); } } } else { //System.out.println("here here here"); if(cl.TM1[0]==chain.get(ind).value){ coefprod*=cl.alpha; chain.add(new Solution(ind2+1, cl.TM1[0])); }else if((coefprod*cl.beta)>threshold){ count++; coefprod*=cl.beta; chain.add(new Solution(ind2+1, !cl.TM1[0])); }else { if(findInTwo(ind1)!=-1 && !AlreadyChanged(ind1+1)) { changeValue(ind1+1); recover(); needagain=true; }else { System.out.println("Unsolvable"); System.exit(0); } } } } else { ind=findInOne(ind2); if(ind!=-1) { int next = cl.var1; ArrayList <Clause> temp3= var1Search(next); ArrayList <Clause> temp4= var2Search(next); if(temp3.size()>0 && temp3.get(0).var1==cl.var1 && temp3.get(0).var2==cl.var2) temp3.remove(0); if(temp3.size()>0){ Clause next1=temp3.get(0); if(cl.TM2[0]==chain.get(ind).value){ coefprod*=cl.alpha; chain.add(new Solution(ind1+1, cl.TM2[1])); } else if(next1.TM1[0]==!cl.TM2[1] && !cl.TM2[0]==chain.get(ind).value && (coefprod*cl.beta)>threshold){ count++; coefprod*=cl.beta; chain.add(new Solution(ind1+1, !cl.TM2[1])); }else { if(findInTwo(ind2)!=-1 && !AlreadyChanged(ind2+1)) { changeValue(ind2+1); recover(); needagain=true; }else { System.out.println("Unsolvable"); System.exit(0); } } }else if(temp4.size()>0){ Clause next1=temp4.get(0); if(cl.TM2[0]==chain.get(ind).value){ coefprod*=cl.alpha; chain.add(new Solution(ind1+1, cl.TM2[0])); } else if(next1.TM2[0]==!cl.TM2[1] && !cl.TM2[0]==chain.get(ind).value && (coefprod*cl.beta)>threshold){ count++; coefprod*=cl.beta; chain.add(new Solution(ind1+1, !cl.TM2[0])); } else { if(findInTwo(ind2)!=-1 && !AlreadyChanged(ind2+1)) { changeValue(ind2+1); recover(); needagain=true; }else { System.out.println("Unsolvable"); System.exit(0); } } } else { if(cl.TM2[0]==chain.get(ind).value){ coefprod*=cl.alpha; chain.add(new Solution(ind1+1, cl.TM2[0])); }else if((coefprod*cl.beta)>threshold){ count++; coefprod*=cl.beta; chain.add(new Solution(ind1+1, !cl.TM2[0])); }else { if(findInTwo(ind1)!=-1 && !AlreadyChanged(ind1+1)) { changeValue(ind1+1); recover(); needagain=true; }else { System.out.println("Unsolvable"); System.exit(0); } } } } else{ chain.add(new Solution(ind1+1, cl.TM1[0])); chain.add(new Solution(ind2+1, cl.TM1[1])); } } if(!processChain2()){ System.out.println("Unsolvable"); System.exit(0); } if(!needagain){ Constraints.remove(cl); } needagain=false; } } for (int i = 0; i < chain.size(); i++){ System.out.println(chain.get(i).index+" "+chain.get(i).value); } System.out.println(coefprod); System.out.println(count); return true; } public int findInTwo(int ind){ for(int i=0;i<chain2.size(); i++){ if(chain2.get(i).index==ind+1){ return i; } } return -1; } public int findInOne(int ind){ for(int i=0;i<chain.size(); i++){ if(chain.get(i).index==ind+1){ return i; } } return -1; } public boolean processChain2(){ for (int i = 0; i<chain.size(); i++){ for(int j = 0; j<chain.size(); j++){ if (chain.get(i).index==chain.get(j).index && chain.get(i).value != chain.get(j).value) { return false; } } } return true; } public boolean AlreadyChanged(int a){ for(int k=0; k<alreadyChanged.size(); k++){ if(alreadyChanged.get(k).intValue()==a){ return true; } } return false; } public void changeFixed (int ind){ Solution a; for (int j = 0; j<chain2.size(); j++){ for(int i = 0; i<chain2.size(); i++){ if (chain.get(i).index==ind && chain2.get(j).index==ind) { chain.get(i).value=chain2.get(j).value; prelimchain.get(i).value=chain2.get(j).value; if(!findInAlreadyChanged(chain.get(i).index)){ alreadyChanged.add(new Integer(chain.get(i).index)); } } } } } public void changeValue(int a){ for (int j = 0; j<chain2.size(); j++){ for(int i = 0; i<chain.size(); i++){ if (chain.get(i).index==a && chain2.get(j).index==a) { chain.get(i).value=chain2.get(j).value; prelimchain.get(i).value=chain2.get(j).value; if(chain.get(i).fixed!=-1){ changeFixed(chain.get(i).fixed); } if(!findInAlreadyChanged(chain.get(i).index)){ alreadyChanged.add(new Integer(chain.get(i).index)); } } } } } public boolean findInAlreadyChanged(int temp){ for(int i=0; i<alreadyChanged.size();i++){ if(alreadyChanged.get(i).intValue()==temp){ return true; } } return false; } public void runPrelim1 (){ //boolean alreadyChanged=false; if(firstime){ for(int i=0; i<Constraints.size(); i++){ Constraints3.add(Constraints.get(i)); } coefprodcopy=coefprod; //System.out.println("c"+coefprod); firstime=false; } for(int i=0; i<prelimchain.size(); i++){ Solution one= prelimchain.get(i); int a = one.index; //minus 1? boolean b = one.value; /*if(i==1){ System.out.println("prelim:"+a); System.exit(0); }*/ boolean liveChain = true; int start = a; boolean conflict=false; while(liveChain && Constraints.size()>0){ ArrayList <Clause> temp= var1Search(start); ArrayList <Clause> temp2= var2Search(start); //System.out.println(temp2.size()); /*if(i==1){ System.out.println("prelim:"+temp.size()); System.exit(0); }*/ if(temp.size()>0){ //System.out.println(temp.get(0).var1+" "+temp.get(0).var2); Clause current = temp.get(0); int next = current.var2; ArrayList <Clause> temp3= var1Search(next); //System.out.println(temp3.size()); ArrayList <Clause> temp4= var2Search(next); if(temp4.size()>0 && temp4.get(0).var1==current.var1 && temp4.get(0).var2==current.var2) temp4.remove(0); /*if(i==1){ System.out.println("prelim:"+temp3.size()+" "+temp4.size()); }*/ if(temp3.size()>0){ Clause next1 = temp3.get(0); if(current.TM1[0]==b){ //System.out.println("here1"); start=next; Solution f = new Solution(next,current.TM1[1]); chain.add(f); prevchain.add(f); b=current.TM1[1]; coefprod*=current.alpha; coefprod2*=current.alpha; Constraints.remove(current); //System.out.println(Constraints.size()); } else if(!next1.TM1[0]==current.TM1[1] && current.TM1[0]==!b && (coefprod*current.beta)>threshold){ count++; coefprod*=current.beta; coefprod2*=current.beta; start=next; Solution f = new Solution(next,!current.TM1[1]); chain.add(f); prevchain.add(f); b=!current.TM1[1]; Constraints.remove(current); } else { liveChain = false; conflict=true; //System.out.println("alreadychange1"); if(AlreadyChanged(a)){ System.out.println("Unsolvable"); System.exit(0); } } }else if(temp4.size()>0){ Clause next1 = temp4.get(0); if(current.TM1[0]==b){ start=next; Solution f = new Solution(next,current.TM2[1]); chain.add(f); prevchain.add(f); b=current.TM2[1]; coefprod*=current.alpha; coefprod2*=current.alpha; Constraints.remove(current); } else if(!next1.TM2[0]==current.TM1[1] && current.TM1[0]==!b && (coefprod*current.beta)>threshold){ count++; coefprod*=current.beta; coefprod2*=current.beta; start=next; Solution f = new Solution(next,!current.TM2[1]); chain.add(f); prevchain.add(f); b=!current.TM2[1]; Constraints.remove(current); } else { liveChain = false; conflict=true; //System.out.println("alreadychange2"); if(AlreadyChanged(a)){ System.out.println("Unsolvable"); System.exit(0); } } }else { if(current.TM1[0]==b){ start=next; b= current.TM1[1]; Solution f = new Solution(next,current.TM1[1]); chain.add(f); prevchain.add(f); coefprod*=current.alpha; coefprod2*=current.alpha; Constraints.remove(current); }else if((coefprod*current.beta)>threshold){ //System.out.println("here here here"); start=next; b= !current.TM1[1]; count++; coefprod*=current.beta; coefprod2*=current.beta; Solution f = new Solution(next,!current.TM1[1]); chain.add(f); prevchain.add(f); //System.out.println(next+" "+!current.TM1[1]); //System.exit(0); Constraints.remove(current); }else { liveChain = false; conflict=true; //System.out.println("alreadychange7"); if(AlreadyChanged(a)){ System.out.println("Unsolvable"); System.exit(0); } } } } else if(temp2.size()>0){ //System.out.println(temp2.get(0).var1+" "+temp2.get(0).var2); Clause current = temp2.get(0); int next2 = current.var1; ArrayList <Clause> temp3= var1Search(next2); ArrayList <Clause> temp4= var2Search(next2); if(temp3.size()>0 && temp3.get(0).var1==current.var1 && temp3.get(0).var2==current.var2) temp3.remove(0); if(temp3.size()>0){ Clause next1 = temp3.get(0); if(current.TM2[0]==b){ start=next2; Solution f = new Solution(next2,current.TM2[1]); chain.add(f); prevchain.add(f); b=current.TM2[1]; coefprod*=current.alpha; coefprod2*=current.alpha; Constraints.remove(current); } else if(!next1.TM1[0]==current.TM2[1] && current.TM2[0]==!b && (coefprod*current.beta)>threshold){ count++; coefprod*=current.beta; coefprod2*=current.beta; start=next2; Solution f = new Solution(next2,!current.TM2[1]); chain.add(f); prevchain.add(f); b=!current.TM2[1]; Constraints.remove(current); } else { liveChain = false; conflict=true; //System.out.println("alreadychange3"); if(AlreadyChanged(a)){ System.out.println("Unsolvable"); System.exit(0); } } }else if(temp4.size()>0){ Clause next1 = temp4.get(0); if(current.TM2[0]==b){ start=next2; Solution f = new Solution(next2,current.TM2[1]); chain.add(f); prevchain.add(f); b=current.TM2[1]; coefprod*=current.alpha; coefprod2*=current.alpha; Constraints.remove(current); } else if(!next1.TM2[0]==current.TM2[1] && current.TM2[0]==!b && (coefprod*current.beta)>threshold){ count++; coefprod*=current.beta; coefprod2*=current.beta; start=next2; Solution f = new Solution(next2,!current.TM2[1]); chain.add(f); prevchain.add(f); b=!current.TM2[1]; Constraints.remove(current); } else { liveChain = false; conflict=true; //System.out.println("alreadychange4"); if(AlreadyChanged(a)){ System.out.println("Unsolvable"); System.exit(0); } } }else { if(current.TM2[0]==b){ start=next2; b= current.TM2[1]; Solution f = new Solution(next2,current.TM2[1]); chain.add(f); prevchain.add(f); coefprod*=current.alpha; coefprod2*=current.alpha; Constraints.remove(current); }else if((coefprod*current.beta)>threshold){ start=next2; b= !current.TM2[1]; count++; coefprod*=current.beta; coefprod2*=current.beta; Solution f = new Solution(next2,!current.TM2[1]); chain.add(f); prevchain.add(f); Constraints.remove(current); } else { liveChain = false; conflict=true; //System.out.println("alreadychange5"); if(AlreadyChanged(a)){ System.out.println("Unsolvable"); System.exit(0); } } } }else { liveChain=false; //System.out.println("here here here here"); /*if(i==1){ System.out.println("here here here here2"); System.exit(0); }*/ } } //System.out.println(processChain2()); if(!processChain2()|| conflict) { UndoCRForward(); for(int s=0; s< Constraints2.size(); s++){ if(!Constraints.contains(Constraints2.get(s))){ Constraints.add(Constraints2.get(s)); } } if(findInTwo(a-1)!=-1 && !AlreadyChanged(a)){ //System.out.println("alreadychange6"); changeValue(a); i--; } else { System.out.println("Unsolvable"); System.exit(0); } } else { //System.out.println(Constraints.size()); Constraints2=Constraints; } liveChain=true; coefprod2=1; prevchain = new ArrayList<Solution>(); conflict=false; } } public void UndoCRForward(){ for (int i = 0; i<chain.size(); i++){ for(int j = 0; j<prevchain.size(); j++){ if (chain.get(i).index==prevchain.get(j).index) { chain.remove(i); i--; } } } coefprod/=coefprod2; //System.out.println(coefprod); } public ArrayList<Clause> var1Search (int var1){ ArrayList <Clause>temp = new ArrayList<Clause>(); for(int k = 0; k < Constraints.size(); k++){ if (Constraints.get(k).var1==var1) temp.add(Constraints.get(k)); } return temp; } //Searches the Constraints ArrayList for the given second variable. public ArrayList<Clause> var2Search (int var2){ ArrayList <Clause>temp = new ArrayList<Clause>(); for(int k = 0; k<Constraints.size(); k++){ if (Constraints.get(k).var2==var2) temp.add(Constraints.get(k)); } return temp; } private class Clause { int var1 = 0; int var2 = 1; double alpha; double beta; int rank; boolean [] phi = new boolean[2]; boolean [] TM1 = new boolean [2]; boolean [] TM2 = new boolean [2]; //reverse. double [][] clause = new double [4][4]; //(phi[0],phi[1])=(a0,b0)=00, 01, 10, 11 public Clause (int a, int b, int c, double alph, boolean [] input){ var1=a; var2=b; alpha=alph; beta=sqrt(1-alpha*alpha); // c= 0,1,2,3 if(var1!=var2){ if (c==1){ input[var1-1] = !input[var1-1]; } else if (c==2){ input[var2-1] = !input[var2-1]; } else if (c==3){ input[var1-1] = !input[var1-1]; input[var2-1] = !input[var2-1]; }else {} phi[0] = input[var1-1]; //left phi[1] = input[var2-1]; //right TM1[1] = !phi[1]; //left TM1[0] = phi[0]; //right TM2[1] = !phi[0]; TM2[0] = phi[1]; makeClause(); } else{ for (int i = 0; i < 4 ;i++){ for (int j = 0; j < 4; j++){ clause[i][j] = 0; } } if(c==0){ clause[0][0] = 1; }else if(c==1){ clause[1][1] = 1; }else if(c==2){ clause[2][2] = 1; }else if(c==3){ clause[3][3] = 1; } } } public Clause (int a, int b, double[][]M, double alph){ var1 = a; var2 = b; clause = M; alpha=alph; beta=sqrt(1-alpha*alpha); } public void makeClause(){ for (int i = 0; i<4 ;i++){ for (int j = 0; j<4; j++){ clause[i][j] = 0; } } if (!phi[0] && !phi[1]){ clause[0][0] = 1; } else if (phi[0] && phi[1]){ clause[3][3] = 1; } else if (phi[0] && !phi[1]){ clause[2][2] = 1; }else { clause [1][1] = 1; } } } private class Solution { ArrayList<Solution> fixedones=new ArrayList(); int index; boolean value; int fixed=-1; public Solution(int a, boolean b){ index=a; value=b; } public Solution(int a, boolean b, int c){ index=a; value=b; fixed=c; } } } |