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] |
Here is my version of the SolveQ algorithm programed in java. It is pretty much correct if my understanding of the algorithm is correct in the first place. If not then someone can tell me and I can change it very fast because I have written all the necessary methods, I just need to make slight adjustments and put them together. I spent a week trying to figure out what the "discretized cycles" mentioned in the algorithm really was. My conclusion was that for simple OR clauses, there are no discretized cycles. This algorithm solves 2-SAT problems. It is a quantum algorithm. It finds only one solution to the problem even though there could be more than one solution. import static java.lang.Math.sqrt; import java.util.*; public class SolveQ { 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 ArrayList<Solution> prevchain = new ArrayList<Solution>(); private ArrayList<Integer> alreadyChanged = new ArrayList<Integer>(); private boolean []settings = new boolean[6]; private boolean myright = false; private boolean myleft = false; private String myString; private boolean isCyclic = false; private boolean unsolvable = false; private ArrayList<Solution> mychain = new ArrayList<Solution>(); private int cycleEnd = -1; private double coeff = 0.9; private static final double coeffmin = 0.7; private boolean firstime=true; public static void main (String [] args){ SolveQ sq = new SolveQ(); 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 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; } public void printString(String s, int n){ s = s.concat(""+n); myString = s; } //look for forward cycles such as 1234561 public void cycleForward (int v, int start, boolean[] visited, String s){ visited[v] = true; //boolean var2bool=false; int a=v+1; s = s.concat(""+a+"&"); ArrayList<Clause> list = var1Search(v+1); int i = 0; if(list.size()==0){ myString = s.substring(0,s.length()-1); return; } while(i<list.size()){ int n = list.get(i).var2-1; if(visited[n]){ isCyclic = true; cycleEnd = n; //????? myleft = list.get(i).TM1[0]; printString(s,n); //System.out.println(myString); break; } else { cycleForward(n, start, visited,s); } i++; } } public boolean CRForward(int ind, boolean vec){ boolean visited[] = new boolean[solutions.length]; int index1 = 0; int tempvar1, tempvar2; boolean found = false; String [] tokens; int count=0; cycleForward(ind,ind,visited,""); if(myString!=null && myString.compareTo(""+ind)!=0){ found = true; tokens = myString.split("&"); while((index1+1)<tokens.length){ tempvar1 = Integer.parseInt(tokens[index1]); tempvar2 = Integer.parseInt(tokens[index1+1]); ArrayList<Clause> list = varSearch(tempvar1, tempvar2); if(list.get(0).TM1[1]==vec){ count++; vec = list.get(0).TM1[0]; } else { break; } index1 = index1+1; } while((index1+1)<tokens.length && count>0){ tempvar1=Integer.parseInt(tokens[index1]); tempvar2=Integer.parseInt(tokens[index1+1]); ArrayList<Clause> list = varSearch(tempvar1, tempvar2); if(list.get(0).TM1[1]==vec){ if(index1==0){ chain.add(new Solution(list.get(0).var1, vec)); } vec = list.get(0).TM1[0]; chain.add(new Solution(list.get(0).var2, vec)); } Constraints.remove(list.get(0)); index1 = index1+1; } } else { return false; } return true; } 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]; } //Clause A = new Clause (1,2,2,vec1); //Clause B = new Clause (1,2,3,vec2); //Clause C = new Clause (1,2,4,vec3); //Clause C2 = new Clause (1,2,1,vec4); //Clause A2 = new Clause (3,4,2,vec2); //Clause A3 = new Clause (2,4,1,vec3); //Clause D = new Clause (3,1,2,vec4); //Clause E = new Clause (2,3,1,vec5); //Clause F = new Clause (4,5,2, vec6); //Clause G = new Clause (5,6,3, vec7); //Clause H = new Clause (6,4,2, vec8); //Clause I= new Clause(1,2,1, vec1); Clause J= new Clause(2,3,3, vec3); Clause J2= new Clause(2,3,4,vec6); Clause J3= new Clause(4,4,3,vec7); Clause J4= new Clause(4,4,1,vec8); Clause K = new Clause (3,4,3, vec5); Clause L= new Clause(4,5,3, vec4); //Clause M= new Clause(1,1,4,vec8); //Clause N= new Clause(1,2,1,vec4); //Clause O= new Clause(3,4,1, vec3); //Clause P = new Clause(2,3,4,vec5); //Clause Q = new Clause(3,2,2,vec2); //Clause R= new Clause(4,2,2,vec4); Clause S= new Clause(4,6,4,vec1); Clause T = new Clause(5,6,1,vec2); //Constraints.add(A); //Constraints2.add(A); //Constraints3.add(A); //Constraints3.add(A); //Constraints.add(A2); //Constraints2.add(A2); //Constraints3.add(A2); //Constraints.add(A3); //Constraints2.add(A3); //Constraints3.add(A3); //Constraints.add(B); //Constraints2.add(B); //Constraints3.add(B); //Constraints.add(C); //Constraints2.add(C); //Constraints.add(C2); //Constraints2.add(C2); //Constraints3.add(C2); //Constraints.add(D); //Constraints2.add(D); //Constraints.add(E); //Constraints2.add(E); //Constraints3.add(E); //Constraints.add(F); //Constraints2.add(F); //Constraints3.add(F); //Constraints.add(K); //Constraints2.add(K); //Constraints3.add(K); //Constraints.add(G); //Constraints2.add(G); //Constraints3.add(G); //Constraints.add(H); //Constraints2.add(H); //Constraints3.add(H); //Constraints.add(I); Constraints.add(J); Constraints2.add(J); //Constraints3.add(J); Constraints.add(J2); Constraints2.add(J2); Constraints.add(J3); Constraints2.add(J3); Constraints.add(J4); Constraints2.add(J4); //Constraints3.add(J2); Constraints.add(K); Constraints2.add(K); //Constraints3.add(K); Constraints.add(S); Constraints2.add(S); Constraints.add(L); Constraints2.add(L); //Constraints3.add(L); //Constraints.add(M); //Constraints2.add(M); //Constraints.add(N); //Constraints.add(P); //Constraints2.add(P); //Constraints3.add(P); //Constraints.add(Q); //Constraints2.add(Q); //Constraints.add(O); //Constraints.add(R); //Constraints2.add(R); Constraints.add(T); Constraints2.add(T); } 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); sum.add(A); alph=0; } } } } 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 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 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){ temp = sum.get(i).clause; rank = findRank(temp); 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); //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; 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; for (int s=0; s<chain.size(); s++){ if(chain.get(s).index==start+1) { 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) { 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 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 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--; } } } } 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 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 void runPrelim1 (){ boolean beenhere=false; int saved=0; boolean conflict = false; boolean canChange =true; if(firstime){ for(int i=0; i<Constraints.size(); i++){ Constraints3.add(Constraints.get(i)); } firstime=false; } for(int i=0; i<prelimchain.size(); i++){ Solution one= prelimchain.get(i); int a = one.index; boolean b = one.value; boolean liveChain = true; int start = a; while(liveChain && Constraints.size()>0){ ArrayList <Clause> temp= var1Search(start); ArrayList <Clause> temp2= var2Search(start); if(temp.size()>0){ Clause current = temp.get(0); int next = current.var2; if(current.TM1[1]==b){ start = next; Solution f = new Solution(next,current.TM1[0]); chain.add(f); prevchain.add(f); b = current.TM1[0]; Constraints.remove(current); } else { liveChain = false; conflict=true; if(AlreadyChanged(a)){ System.out.println("Unsolvable"); System.exit(0); } } } else if(temp2.size()>0){ Clause current2= temp2.get(0); int next2 = current2.var1; if(current2.TM2[1]==b){ start = next2; Solution f = new Solution(next2,current2.TM2[0]); chain.add(f); prevchain.add(f); b = current2.TM2[0]; Constraints.remove(current2); }else { liveChain = false; conflict=true; if(AlreadyChanged(a)){ System.out.println("Unsolvable"); System.exit(0); } } } else { liveChain=false; } } 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)){ changeValue(a); i--; } else { System.out.println("Unsolvable"); System.exit(0); } } else { Constraints2=Constraints; } liveChain=true; prevchain = new ArrayList<Solution>(); conflict=false; } } 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 runPrelim1 (){ for(int i=0; i<prelimchain.size(); i++){ Solution one= prelimchain.get(i); int a = one.index; //minus 1? boolean b = one.value; CRForward(a-1,b); if(!processChain2()) { 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){ changeValue(a); i--; } else { System.out.println("Unsolvable"); System.exit(0); } } else { Constraints2=Constraints; } } }*/ /*public boolean algorithm (){ int loop; int count = 0; boolean passed=false; boolean previouschain = false; boolean cycleDone = false; while (Constraints.size()>0) { if(prelimchain.size()>0){ runPrelim1(); } int index=0; 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){ if(cl.TM1[1]==chain.get(ind).value){ chain.add(new Solution(ind2+1, cl.TM1[0])); } } else { ind=findInOne(ind2); if(ind!=-1) { if(cl.TM2[1]==chain.get(ind).value){ coeff *= 0.95; chain.add(new Solution(ind1+1, cl.TM2[0])); }else{ int index5=chain.get(ind).index; if(findInTwo(index5-1)!=-1) { changeValue(index5); chain=new ArrayList<Solution>(); for(int i=0; i<prelimchain.size(); i++){ chain.add(prelimchain.get(i)); } if(prelimchain.size()>0){ //System.out.println(Constraints3.size()); Constraints= new ArrayList<Clause>(); Constraints2= new ArrayList<Clause>(); for(int u=0; u<Constraints3.size(); u++){ Constraints.add(Constraints3.get(u)); Constraints2.add(Constraints3.get(u)); } runPrelim1(); } if(cl.TM2[1]==chain.get(findInOne(index5-1)).value){ chain.add(new Solution(ind1+1, cl.TM2[0])); }else { System.out.println("Unsolvable"); System.exit(0); } }else { System.out.println("Unsolvable"); System.exit(0); } } } else{ chain.add(new Solution(ind1+1, cl.TM1[1])); chain.add(new Solution(ind2+1, cl.TM1[0])); } } if(!processChain2()){ System.out.println("Unsolvable"); System.exit(0); } Constraints.remove(cl); //what about Constraints2? index=index; } } for (int i = 0; i < chain.size(); i++){ System.out.println(chain.get(i).index+" "+chain.get(i).value); } return true; }*/ 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)); } 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){ if(cl.TM1[1]==chain.get(ind).value){ 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) { if(cl.TM2[1]==chain.get(ind).value){ 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{ chain.add(new Solution(ind1+1, cl.TM1[1])); chain.add(new Solution(ind2+1, cl.TM1[0])); } } 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); } return true; } //returns whether there is a conflict in the solution chain. private class Clause { int var1 = 0; int var2 = 1; double alpha = 0.95; double beta = 0.32; int rank; boolean [] phi = new boolean[2]; boolean [] TM1 = new boolean [2]; boolean [] TM2 = new boolean [2]; //reverse. double [][] clause = new double [4][4]; //1: a-bar 2: b-bar: 3:both not bar 4: both bar public Clause (int a, int b, int c, boolean [] input){ var1=a; var2=b; 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==4){ input[var1-1] = !input[var1-1]; input[var2-1] = !input[var2-1]; }else {} phi[0] = input[var1-1]; phi[1] = input[var2-1]; TM1[0] = !phi[1]; TM1[1] = phi[0]; TM2[0] = !phi[0]; TM2[1] = phi[1]; makeClause(); } else{ for (int i = 0; i < 4 ;i++){ for (int j = 0; j < 4; j++){ clause[i][j] = 0; } } if(c==1){ clause[1][1]=1; } else if(c==2){ clause[2][2]=1; } else if(c==3){ clause[0][0] = 1; }else if(c==4){ clause[3][3] = 1; } } } public Clause (int a, int b, double[][]M){ var1 = a; var2 = b; clause = M; } 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; } } } |