//CHECKJS  C:\temp\sudoku\weak.js 11/6/2005 12:29:53 PM
//weak.js hansonr@stolaf.edu 7:00 AM 10/28/2005
// handles all weak link creation and checking
// 5:40 PM 12/11/2005 adjusted comments

WeakLinks=new Array()
WeakCorners=new Array()
ChainXRef=new Array()

function addWeakCheck(){
	var i1=0
	var j1=0
	var pi1=0
	var pj1=0
	var i2=0
	var j2=0
	var pi2=0
	var pj2=0
	var x=""
	var ihave1=0

	// here we propagate the links, so if 1(-)-->x-->2(+), then 2(+)-->1(-)
	// and if 1-->x-->2 and 2-->x-->3, then also 1-->x-->3   :)

	// WeakLinks[i]=[coord,i,j,pi,pj,Wi,Wj]
	// where Wi = [D,TheNode,k,StrongNodeList[k,D.nodeinfo]]

	for(var pt1 in WeakLinks){
		i1=WeakLinks[pt1][0][1]
		j1=WeakLinks[pt1][0][2]
		pi1=WeakLinks[pt1][0][3]
		pj1=WeakLinks[pt1][0][4]
		for(var pt2 in WeakLinks)if(pt1!=pt2){
			i2=WeakLinks[pt2][0][1]
			j2=WeakLinks[pt2][0][2]
			pi2=WeakLinks[pt2][0][3]
			pj2=WeakLinks[pt2][0][4]
			if(i1!=j2 && j1==i2 && pj1!=pi2){
				x=i1+"_"+j2+","+pi1+"/"+pj2
				if(!WeakLinks[x]){ //bridge made
					//bit tricky here--arrays are changing...
					addWeakLink("via chain "+chainCode(i2,pi2,1),i1,j2,pi1,pj2,WeakLinks[pt1][0][5],WeakLinks[pt2][0][6],-1,0,0)
					if(iseliminated)return 0
					ihave1=1
				}
			}
		}		
	}
	return ihave1
}

function addWeakLink(coord,i,j,pi,pj,Wi,Wj,k,isduplicate,iskipcheck){
	var x=i+"_"+j+","+pi+"/"+pj  // pi, pj 0 or 1
	var ipt=0
	if(k>=0){
		if(!WeakCorners[x])WeakCorners[x]=new Array()
		if(!isduplicate)nweakcorners++
		ipt=WeakCorners[x].length
		WeakCorners[x][ipt]=[coord,i,j,pi,pj,Wi,Wj,k]
		if(ishowdetail && !isduplicate)logAddMessage(getWeakLinkInfo(WeakCorners[x][ipt],"corner"))
		x=j+"_"+i+","+pj+"/"+pi
		if(!WeakCorners[x])addWeakLink(coord,j,i,pj,pi,Wj,Wi,k,1,iskipcheck)
		return
	}
	if(!isduplicate)nweaklinks++
	if(!WeakLinks[x])WeakLinks[x]=new Array()
	ipt=WeakLinks[x].length
	WeakLinks[x][ipt]=[coord,i,j,pi,pj,Wi,Wj,-1]
	ChainXRef["_"+(pi==1?i:-i)].push(pj==1?j:-j)
	chainCodeSet(i,pi,j,pj)
	if(ishowdetail && !isduplicate)logAddMessage(getWeakLinkInfo(WeakLinks[x][ipt],"link"))
	x=i+"_"+j+","+(1-pi)+"/"+pj
	if(WeakLinks[x] && !iskipcheck){
		// have 1/pj and 0/pj, meaning pj is N
		greenlist+=WeakLinks[x][0][0]
		ishowchain2=i
		eliminateChainParity(j,pj?1:-1,"[chain "+chainCode(j,pj,1)+"] can be eliminated due to conflicting weak link to [chain "+chainCode(i,pi,1)+"]","Mw")
		return
	}
	x=i+"_"+j+","+pi+"/"+(1-pj)
	if(WeakLinks[x] && !iskipcheck){
		// have pi/0 and pi/1  meaning pi is out
		greenlist+=WeakLinks[x][0][0]
		ishowchain2=j
		eliminateChainParity(i,pi?1:-1,"[chain "+chainCode(i,pi,1)+"] can be eliminated due to conflicting weak link to [chain "+chainCode(j,pj,1)+"]","Mw")
		return
	}
	x=j+"_"+i+","+pj+"/"+pi
	if(!WeakLinks[x])addWeakLink(coord,j,i,pj,pi,Wj,Wi,k,1,iskipcheck)
}

function checkNoPossibleValue(icontinue){
	var D=new Array()
	var X=new Array()
	var C=new Array()
	var slist=""
	var smatch=""
	var ichain=0
	var iparity=0
	var inode=0
	var imatch=0
	var coord=""
	var s=""
	for(var i=0;i<9;i++)for(var j=0;j<9;j++)if(Data[i][j].xiskstrong==Possible.XCell[i][j]){
		D=Data[i][j]
		X=xList(D.xiskstrong)
		inode=StrongNodePtr[coordOf(D,X[0])]
		if(X.length>0 && (X.length!=2||ichain!=StrongNodePtr[coordOf(D,X[1])])){
			ichain=nodeData(StrongNodes[inode],CHAINPARITY)
			slist=";"+ChainXRef["_"+ichain].join(";")+";"			
			for(var p=1;p<X.length;p++){
				smatch=""
				imatch=0
				ichain=nodeData(StrongNodes[StrongNodePtr[coordOf(D,X[p])]],CHAINPARITY)
				C=ChainXRef["_"+ichain]
				for(var c=0;c<C.length;c++){
					s=";"+C[c]+";"
					if(slist.indexOf(s)>=0){
						smatch+=s
						imatch=C[c]
					}
				}
				slist=smatch
			}
			if(imatch){
				ichain=Math.abs(imatch)
				iparity=(ichain==imatch?1:-1)
				greenlist+=D.showinfo
				eliminateChainParity(ichain,iparity,"chain "+chainCode(ichain,iparity,1)+" can be eliminated because it would lead to no possible value at "+D.showinfo,"Mw")
				if(!icontinue)return 1
			}
		}
	}
	return 0
}


function checkWeakConstraints(icontinue){

 //if(isjustycycles)icontinue=0


	// All the odd/even chain business is just measuring alternating parity.
	// There is no distinction betweeen X- and Y-constraints in this context.

	// so we don't make a distinction between "X" and "Y" but, rather, between
	// whether we allow weak link jumps from one chain to the next.

	// note that we allow the chains to follow any 3D path, not just of a certain k-value

	// strong constraints must be checked first, so that chains are built.

	// build WeakLinks array from WeakNodes[coord][WeakNodes[coord].length]=[D,TheNode]

	logAddMessage("Checking for weak links")

	var icheckalmostlocked=(igetalmostlockedx||igetalmostlockedy)

	WeakLinks=new Array()
	WeakCorners=new Array()

	// this next is for checking to see if all possibilities for a given cell have been eliminated for a GIVEN chain setting in checkNoPossibleValue()

	getWeakLinks()

	if(nweaklinks)logAddMessage(nweaklinks+" weak links")
	if(nweakcorners)logAddMessage(nweakcorners+" weak corners")

	// fill in gaps

	while(!iseliminated && addWeakCheck()){}
	if(ishowdetail)logAddMessage(dumpWeakLinks(1))

	if(iseliminated)return 1

	// check for even/odd disparities


	if(icheckalmostlocked&&checkWeakAlmostLocked(icontinue))return 1

	if(checkWeakLinks(icontinue))return 1

	if(checkNoPossibleValue(icontinue))return 1

	return 0
}

function checkWeakLinks(icontinue){

	var isOK=1
	var s=""

	// weak link transmission goes through the same parity set, but we don't know
	// how the chains are phased. (What is "+" on one may be matching with either + or - on the other)
	// What's important is that we get phased transmission: ++/--, +-/+-, -+/-+, or --/++

	// Note: single-chain X-constraint type 1 and Y-constraint have already been found by addWeakNode()

	for(var i=1;i<StrongChains.length;i++)for(var j=1+1;j<StrongChains.length;j++){

		// X-constraint, type 1 with any number of weak links and/or strong Y-type inclusions
		// 0/1,0/1 or 1/0,1/0 means chain i is odd, chain j is odd -- delete weak link point

		if(WeakLinks[i+"_"+j+",0/1"] && WeakLinks[j+"_"+i+",0/1"]){
			isOK&=eliminateWeakLink(WeakLinks,i,j,"0/1","0/1",0,"weakly linked to both "+chainCode(i,0,1)+" and "+chainCode(i,1,1)+"--"+chainCode(j,1,1))
//," X-like weak 0/1 link between 1/0-linked strong chains")
			if(!isOK && !icontinue)return 1
		}

		if(WeakLinks[i+"_"+j+",0/0"] && WeakLinks[j+"_"+i+",1/1"]){
			isOK&=eliminateWeakLink(WeakLinks,i,j,"0/0","1/1",0,"weakly linked to both "+chainCode(i,0,1)+" and "+chainCode(i,1,1)+"--"+chainCode(j,0,1))
//," x-like weak 0/0 link between 1/1-linked strong chains")
			if(!isOK && !icontinue)return 1
		}

		if(WeakLinks[i+"_"+j+",1/0"] && WeakLinks[j+"_"+i+",1/0"]){
			isOK&=eliminateWeakLink(WeakLinks,i,j,"1/0","1/0",0,"weakly linked to both "+chainCode(i,1,1)+" and "+chainCode(i,0,1)+"--"+chainCode(j,0,1))
//," x-like weak 1/0 link between 0/1-linked strong chains")
			if(!isOK && !icontinue)return 1
		}

		if(WeakLinks[i+"_"+j+",1/1"] && WeakLinks[j+"_"+i+",0/0"]){
			isOK&=eliminateWeakLink(WeakLinks,i,j,"1/1","0/0",0,"weakly linked to both "+chainCode(i,1,1)+" and "+chainCode(i,0,1)+"--"+chainCode(j,1,1))
//," x-like weak 1/1 link between 0/0-linked strong chains")
			if(!isOK && !icontinue)return 1
		}

		// X-constraint, type 2 with strong Y-type inclusions see http://www.research.att.com/~gsf/sudoku/
		// 0/1,0/0 or 1/0,1/1, means chain i is even, chain j is odd -- delete endpoint nodes

		if(WeakLinks[i+"_"+j+",0/1"] && WeakLinks[j+"_"+i+",0/0"]){
			isOK&=eliminateWeakLink(WeakLinks,i,j,"0/1","0/0",1,"both "+chainCode(j,0,1)+" and "+chainCode(j,1,1)+"-->"+chainCode(j,1,1))

//" chain end of even-numbered chain section forced by 0/1/0/0-linked strong chains")
			if(!isOK && !icontinue)return 1
		}

		if(WeakLinks[i+"_"+j+",0/0"] && WeakLinks[j+"_"+i+",1/0"]){
			isOK&=eliminateWeakLink(WeakLinks,i,j,"0/0","1/0",1,"both "+chainCode(j,0,1)+" and "+chainCode(j,1,1)+"-->"+chainCode(j,1,1))
//," chain end of even-numbered chain section forced by 0/0/1/0-linked strong chains")
			if(!isOK && !icontinue)return 1
		}

		if(WeakLinks[i+"_"+j+",1/0"] && WeakLinks[j+"_"+i+",1/1"]){
			isOK&=eliminateWeakLink(WeakLinks,i,j,"1/0","1/1",1,"both "+chainCode(j,0,1)+" and "+chainCode(j,1,1)+"-->"+chainCode(j,0,1))
//," chain end of even-numbered chain section forced by 1/0/1/1-linked strong chains")
			if(!isOK && !icontinue)return 1
		}


		if(WeakLinks[i+"_"+j+",1/1"] && WeakLinks[j+"_"+i+",0/1"]){
			isOK&=eliminateWeakLink(WeakLinks,i,j,"1/1","0/1",1,"both "+chainCode(j,0,1)+" and "+chainCode(j,1,1)+"-->"+chainCode(j,0,1))
//," chain end of even-numbered chain section forced by 1/1/0/1-linked strong chains")
			if(!isOK && !icontinue)return 1
		}

		// X-constraint, type 3, with any number of weak links and Y-type inclusions
		// 0/1,0/1 or 1/0,1/0 0/0,1/1  means chain i is odd, chain j is odd, but this is "two edges" (a corner) -- delete weak link point
		//note that the return MUST be a true link, not a corner!

		if(WeakCorners[i+"_"+j+",0/1"] && WeakLinks[j+"_"+i+",0/1"]){
			isOK&=eliminateWeakLink(WeakCorners,i,j,"0/1","0/1",0,"weak corner eliminated by both "+chainCode(i,0,1)+" and "+chainCode(i,1,1)+"--"+chainCode(j,1,1))
//" weak 0/1 corner between linked 1/0 strong chains")
			if(!isOK && !icontinue)return 1
		}

		if(WeakCorners[i+"_"+j+",0/0"] && WeakLinks[j+"_"+i+",1/1"]){
			isOK&=eliminateWeakLink(WeakCorners,i,j,"0/0","1/1",0,"weak corner eliminated by both "+chainCode(i,0,1)+" and "+chainCode(i,1,1)+"--"+chainCode(j,0,1))
//," weak 0/0 corner between linked 1/1 strong chains")
			if(!isOK && !icontinue)return 1
		}

		if(WeakCorners[i+"_"+j+",1/0"] && WeakLinks[j+"_"+i+",1/0"]){
			isOK&=eliminateWeakLink(WeakCorners,i,j,"1/0","1/0",0,"weak corner eliminated by both "+chainCode(i,1,1)+" and "+chainCode(i,0,1)+"--"+chainCode(j,0,1))
//," weak 1/0 corner between linked 0/1 strong chains")
			if(!isOK && !icontinue)return 1
		}

		if(WeakCorners[i+"_"+j+",1/1"] && WeakLinks[j+"_"+i+",0/0"]){
			isOK&=eliminateWeakLink(WeakCorners,i,j,"1/1","0/0",0,"weak corner eliminated by both "+chainCode(i,1,1)+" and "+chainCode(i,0,1)+"--"+chainCode(j,1,1))
//," weak 1/1 corner between linked 0/0 strong chains")
			if(!isOK && !icontinue)return 1
		}

	}

	return !isOK
}

function dumpWeakLinks(ishownodes){
	if(!StrongChains.length)return ""
	var S=new Array()
	var s=""
	var ch=""
	var sLine=""
	var Temp=new Array()
	for(var i=1;i<StrongChains.length;i++){
		Temp[chainCode(i,1,1)]=new Array()
		Temp[chainCode(i,0,1)]=new Array()
	}
	for(var i in WeakLinks){
		S=chainCode2(i)
		if(S.length)Temp[S[0]].push(S)
	}
	s="<br /><br /><b>Primary Chain Implication Table</b>"
	+"<br /><br />The second step in Medusa Strong Chain Compatibility Analysis is to identify how the strong chains are \"weakly\" linked. When the chain on the left is of the indicated parity, then all the chains on the right must be of their indicated parity due to both chains having a node in the indicated cell, row, column, or block. Incompatibilities arise when a given chain parity implies both of the two possible parities of another chain, or when a given chain parity implies the opposite parity of its own chain. Incompatibilities are indicated in <font color=red>red</font>.<br />"
	s+="<br /><table>"
	var incompatibleList=""
	for(var i in Temp)if(Temp[i].length){
		sLine=""
		si=i+"-->"
		for(var j=0;j<Temp[i].length;j++){
			S=Temp[i][j]
			ch=S[1].toUpperCase()
			var isConflict=(sLine.toUpperCase().indexOf(ch)>=0||ch==i.toUpperCase())
			sLine+=" <b>"+(isConflict?"<font color=red>"+S[1]+"</font>":S[1])+"</b> "+S[2]+"&nbsp;&nbsp;"
			if(isConflict){
				incompatibleList+=";"+i
				si="<font color=red>"+i+"--></font>"
			}
		}
		s+="<tr><th class=msg valign=top nowrap>"+si+"</th><td class=msg nowrap>"+sLine+"</td></tr>"
	}
	s+="</table>"
	if(incompatibleList==""){
		s+="<br /><br />There are no chain incompatibilities at this point in the solution."
	}else{
		s+=dumpIncompatibleChainList(incompatibleList)
	}

	if(!ishownodes)return s
	for(var i in WeakNodes){
		s+="<br /><b>WeakNode "+i+"</b>"
		for(var j=0;j<WeakNodes[i].length;j++)s+="<br />-"+j+"-"+getNodeInfo(WeakNodes[i][j][1])+": "+WeakNodes[i][j][4]
	}
	return s
}

function dumpImpliedWeakLinks(){
	if(!StrongChains.length)return ""
	var S=new Array()
	var s=""
	var ch=""
	var sLine=""
	var Temp=new Array()
	for(var i=1;i<StrongChains.length;i++){
		Temp[chainCode(i,1,1)]=new Array()
		Temp[chainCode(i,0,1)]=new Array()
	}
	for(var i in WeakLinks){
		S=chainCode2(i)
		if(S.length)Temp[S[0]].push(S)
	}
	var incompatibleList=""
	var isNew=true
	while(isNew) {
		isNew=false
		for(var i in Temp)if(Temp[i].length){
			s=i+Temp[i]
			for(var j=0;j<Temp[i].length;j++){
				ch=Temp[i][j][1]
				if(Temp[ch]){
					for(var k=0;k<Temp[ch].length;k++){
						if(s.indexOf(Temp[ch][k][1])<0){
							Temp[i].push(Temp[ch][k])
							isNew=true
							s+=Temp[ch][k]
						}
					}
				}
			}
		}
	}

	s="<br /><br /><b>Secondary Chain Implication Table</b><br /><br />"
	+"The third step in Medusa Strong Chain Compatibility Analysis is to follow the weak links and discover all of the implications. This table is created by following all of the implications in the Primary Chain Implication Table until either a conflict arises or no more implications can be made. Incompatibilities arise when a given chain parity implies both of the two possible parities of another chain, or when a given chain parity implies the opposite parity of its own chain. Incompatibilities are indicated in <font color=red>red</font>.<br /><br />"
	s+="<table>"
	for(var i in Temp)if(Temp[i].length){
		sLine=""
		si=i+"-->"
		for(var j=0;j<Temp[i].length;j++){
			S=Temp[i][j]
			ch=S[1].toUpperCase()
			var isConflict=(sLine.toUpperCase().indexOf(ch)>=0||ch==i.toUpperCase())
			sLine+=" <b>"+(isConflict?"<font color=red>"+S[1]+"</font>":S[1])+"</b> "+"&nbsp;&nbsp;"
			if(isConflict){
				incompatibleList+=";"+i
				si="<font color=red>"+i+"--></font>"
				break
			}
		}
		s+="<tr><th class=msg valign=top nowrap>"+si+"</th><td class=msg nowrap>"+sLine+"</td></tr>"
	}
	s+="</table>"

	if(incompatibleList==""){
		s+="<br /><br />There are no chain incompatibilities at this point in the solution."
	}else{
		s+=dumpIncompatibleChainList(incompatibleList)
	}
	return s
}

function dumpIncompatibleChainList(chainlist){
	var s="<br /><br />The implication from the above table is that the following cells MUST have the values indicated:<br />"
	var N=new Array()
	for(var i=1;i<StrongChains.length;i++)if(chainlist.indexOf(";"+i+"(")>=0){
		var ch=chainlist.substring(chainlist.indexOf(";"+i+"("))
		ch=ch.charAt(ch.indexOf("(")+1)
		var si=""
		var sLine=""
		for(var j=0;j<StrongChains[i].length;j++){
			var chain=nodeData(StrongNodes[StrongChains[i][j]],CHAINCODE)
			if(chain!=ch) {
				si=chain
				sLine+=" "+nodeData(StrongNodes[StrongChains[i][j]],ALLCOORD).replace(/\#/,"=")
			}
		}
		s+="<br /><b>Chain "+i+" must be parity "+si+"</b>: "+sLine
	}
	return s
}

function eliminateWeakLink(WType,i,j,linktype1,linktype2,isnode,swhy){

	// WeakLinks or WeakCorners []=[coord,i,j,pi,pj,Wi,Wj]
	// where Wi[] = [D,TheNode,k,StrongNodeList[k,D.nodeinfo]]
	var L=WType[i+"_"+j+","+linktype1][0]
	var W=L[5]
	var N=W[1]
	var C=new Array()
	var N1=new Array()
	var k=0
	var n=0
	var ididdelete=0
	if (!isnode && !W[0])return 1
	greenlist+=getChainSrc(i)+getChainSrc(j)
	ishowchain = i
	ishowchain2 = j
	if(isnode){ //delete both endpoints
		C=nodeData(N,DATA)
		n=nodeData(N,NDATA)
		k=nodeData(N,K)
		for(var ii=1;ii<n;ii++)ididdelete|=eliminateK(nodeData(N,DATA,ii),k,swhy)
		addAutoMsg("Mw",coordOf(C,k)+" eliminated: "+swhy)
		W=WType[j+"_"+i+","+linktype2][0][6]
		N1=W[1]
		C=nodeData(N1,DATA)
		n=nodeData(N1,NDATA)
		k=nodeData(N1,K)
		for(var ii=1;ii<n;ii++)ididdelete|=eliminateK(nodeData(N1,DATA,ii),k,swhy)
		addAutoMsg("Mw",coordOf(C,k)+" eliminated: "+swhy)
	}else{ //delete the weak link/corner
		C=W[0]
		k=W[2]
		eliminateK(C,k,swhy)
		addAutoMsg("Mw",coordOf(C,k)+" eliminated: "+swhy)
	}
	if(!ididdelete)return 1
	return idonotstop
}

function getWeakLinkInfo(W,type){
	return "["+nodeData(W[5][1],INFO)+"]--"+W[0]+"--["+nodeData(W[6][1],INFO)+"] "+type
}

function getWeakLinks(iskipcheck){

	var W=new Array()
	var ichain=0
	var iparity=0
	var jchain=0
	var jparity=0
	var D=new Array()
	var N1=new Array()
	var N2=new Array()
	var islink=0
	var kd=0
	var k1=0
	var k2=0
	var n1=0
	var n2=0
	var xrcbd=0
	var xrcb1=0
	var xrcb2=0
	var inode=0

	var icheckdirect=1//isjustycycles //only when JUST Y-cycles

	//check for direct links

	if(icheckdirect){
		for(var coord in WeakNodes){
			W=WeakNodes[coord]
			for(var i=0;i<W.length;i++){
				if(W[i][3]){
					N1=W[i][1]
					k1=nodeData(N1,K)		
					ichain=nodeData(N1,CHAIN)
					iparity=(N1[1]>0?1:0)

					N2=StrongNodes[W[i][3]]
					jchain=nodeData(N2,CHAIN)
					jparity=(N2[1]>0?1:0)
					if(ichain<jchain||ichain==jchain && iparity==jparity){
						addWeakLink("--",ichain,jchain,iparity,jparity,[0,N1,k1,0,W[i][4]],[0,N2,W[i][2],0,W[i][4]],-1,0,iskipcheck)
						if(iseliminated)return
					}
				}
			}
		}
	}


	//check for weak nodes as links and corners

	for(var coord in WeakNodes)if(WeakNodes[coord].length>1){
		W=WeakNodes[coord]
		D=W[0][0]
		kd=W[0][2]
		xrcbd=D.xrcb
		for(var i=0;i<W.length-1;i++){
			N1=W[i][1]
			k1=nodeData(N1,K)
			n1=nodeData(N1,NDATA)
			ichain=nodeData(N1,CHAIN)
			xrcb1=nodeData(N1,DATA).xrcb
			iparity=(N1[1]>0?1:0)
			for(var j=i+1;j<W.length;j++){
				N2=W[j][1]
				k2=nodeData(N2,K)
				n2=nodeData(N2,NDATA)
				jchain=nodeData(N2,CHAIN)
				jparity=(N2[1]>0?1:0)
				xrcb2=nodeData(N2,DATA).xrcb
				islink=9+1 //multi-k corner

				//this may be a corner: could be eliminated if chains are properly linked
				// but cannot be used to transmit any linkage itself.

				if(ichain==jchain){

					islink=0

					//all the intrachain stuff is done already in checkParity()


				}else if(kd==k1 && k1==k2){ //must be same row, col, or block when k=k1=k2
					islink=(xrcbd & xrcb1 & xrcb2?-1:kd+1) //link or common-k corner
				}else if(xrcbd==xrcb1 && xrcb1==xrcb2){ //otherwise must be same cell
					islink=-1 //full link
				}
				if(islink==-1 && (n1>1||n2>1)){
					islink=kd+1 //only allow corners for group sets
//logAddMessage([coord,kd,k1,k2,W[i],W[j]])
				}
				if(islink)addWeakLink(coord,ichain,jchain,iparity,jparity,W[i],W[j],islink-1,0,iskipcheck)
				if(iseliminated)return
			}
		}
	}

}