//CHECKJS  C:\temp\sudoku\logic.js 11/6/2005 12:29:49 PM
//logic.js hansonr@stolaf.edu 12:08 PM 11/01/2005
// forward logic chain see 	Nick70's idea at http://www.setbb.com/phpbb/viewtopic.php?t=300&start=0&mforum=sudoku
// added locked candidates

// 3:36 AM 12/4/2005 added three levels -- 

// 0	P	no added depth, including Nick70 stuff
// 1	P+	adds single-row/column/block intersections: singles and locked candidates
// 2	P++	adds multiple-row/column/block intersections: tuples and grids


LogicSave=[]
Logic={}
Logic.True={}
Logic.False={}
Logic.List=[]
Logic.ChainList=[[],[]]
Logic.Table=[]
Logic.terminator=""
Logic_nentries=0
Logic.isreverse=0
Logic.listed=""
Logic.debug=""
nlogic=0
ishowdeadends=0
interlacedepth=1

itestlogic=0 // testing JUST logic -- slow, doesn't work when chains are illdefined and weak nodes are not checked
if(itestlogic)alert("itestlogic=1 in logic.js")

function addAssociatedChains(A,istrue,B){

	// just finding all chains associated with this set of nodes
	// B gets filled only if !istrue -- adding F nodes, so will setAllTrueExcept them
	var ichain=0
	var p=0
	var k=0
	var N=[]
	var D={}
	var coord=""
	var ichain=0
	var TorF=(istrue?Logic.True:Logic.False)
	var notTorF=(istrue?Logic.False:Logic.True)
	for(var i=0;i<A.length;i++){
		D=A[i][1]
		k=A[i][2]
		coord=coordOf(D,k)
		if(StrongNodePtr[coord]){
			N=StrongNodes[StrongNodePtr[coord]]
			ichain=nodeData(N,CHAIN)
			p=nodeData(N,PARITY)
			if(istrue && !Logic.ChainList[p][ichain] && addLogicChainOrNode(ichain,p,0,0,"linked by "+nodeData(N,INFO)))return 1
			if(!istrue && !Logic.ChainList[1-p][ichain] && addLogicChainOrNode(ichain,1-p,0,0,"linked by "+nodeData(N,INFO)))return 1
		}else if(!istrue){
			if(setAllTrueExcept(coord,D,k,B))return 1
		}
	}
	return 0
}

function addAssociatedChains2(A,istrue,B){

	// just finding all chains associated with this set of nodes
	// B gets filled only if istrue -- adding T nodes, so will setAllFalseExcept them
	var ichain=0
	var p=0
	var k=0
	var N=[]
	var D={}
	var coord=""
	var ichain=0
	var TorF=(istrue?Logic.True:Logic.False)
	var notTorF=(istrue?Logic.False:Logic.True)
	for(var i=0;i<A.length;i++){
		D=A[i][1]
		k=A[i][2]
		coord=coordOf(D,k)
		if(StrongNodePtr[coord]){
			N=StrongNodes[StrongNodePtr[coord]]
			ichain=nodeData(N,CHAIN)
			p=nodeData(N,PARITY)
			if(istrue && !Logic.ChainList[1-p][ichain] && addLogicChainOrNode2(ichain,1-p,0,0,"linked by "+nodeData(N,INFO)))return 1
			if(!istrue && !Logic.ChainList[p][ichain] && addLogicChainOrNode2(ichain,p,0,0,"linked by "+nodeData(N,INFO)))return 1
		}else if(istrue){
			if(setAllFalseExcept(coord,D,k,B))return 1
		}
	}
	return 0
}

function addLogic(ichain,p,List,istrue,info){
	var D={}
	var N=[]
	var k=0
	var n=0
	var iparity=0
	var List1=(istrue?Logic.True:Logic.False)
	var List2=(istrue?Logic.False:Logic.True)
	var s=""
	var st=""
	var r=0
	var ch=ALPHABET.charAt((nlogic-1)%26)
	if(istrue!=1)ch=ch.toLowerCase()

	if(istrue<0){ //finalization
		getTableRef(Logic.Table)
		info="<br /><b>"+info+"</b>"
		s=dumpLogic('<br />')
		if(istrue==-1 && Logic.terminator){ //terminator is a coord
			r=new RegExp(Logic.terminator,"g")
			s=s.replace(r,"<b><font color=red>"+Logic.terminator+"</font></b>")
		}
		s=info+s
		n=LogicSave.length
		st=(istrue!=-2?"":checkMagic()?"Magic Cell at ":"Dead End at ") 
		st+=(istrue==-2?ch:"<b>The hypothesis is "+(Logic.isreverse?"proven":"disproved")+". QED")
		LogicSave[n]=s+st
		if(istrue==-2){
			s=info+"<br />" //-2 here indicates showing dead ends
			k=0
			for(var i=0;i<Logic.Table.length;i++){
				ch=Logic.Table[i]
				if(ch && isNaN(ch))Logic.Table[i]=ch.replace(/[A-Z]/g,k+1).replace(/[a-z]/g,"")
				k=(k+1)%9
			}
		}
		logAddMessage(s+st+" <a  href=\"javascript:doShowLogicTable('"+Logic.Table+"','"+Logic.List[0][0]+"','"+Logic.List[Logic.List.length-1][0]+"',"+n+",'"+Logic.terminator+"')\">Table</a></b>")
	}else{
		Logic.List[Logic.List.length]=[ch+": "+info]//,ichain,p,List] //only first is used; others were for debugging
	}

	// adding (a) T or F chain nodes or (b) lists of associated false-forcing weak nodes,
	// or (c) nodes in the same row, column, block, or cell of (b) that complete a set so that
	// their being false forces one of the others to be true

	// for group nodes, we set them FALSE ("all false") but not TRUE ("any true" -- we don't know which one)
	if(ichain){
		if(Logic.listed.indexOf("_"+ichain+";")<0){
			addLogic(0,0,0,istrue,"Chain "+ichain+": "+getChainListing(ichain))
			Logic.listed+="_"+ichain+";"
		}
		for(var inode=0;inode<StrongChains[ichain].length;inode++){
			N=StrongNodes[StrongChains[ichain][inode]]
			iparity=nodeData(N,PARITY)
			if(iparity==p){
				n=nodeData(N,NDATA)
				k=nodeData(N,K)
				if(n==1||!istrue){
					for(var i=1;i<=n;i++){
						if(addLogicX(ch,nodeData(N,DATA,i),k,List1,List2,"chain "+chainCode(ichain,p,1)))return 1
					}
				}
			}
		}
	}else if(List){
		for(var i=0;i<List.length;i++){
			if(List[i][0]){			//associated weak node
				D=List[i][1][0]
				k=List[i][1][2]
			}else{				//added by setAllTrue or getFalseImpliesTrue
				D=List[i][1]
				k=List[i][2]
			}
			if(addLogicX(ch,D,k,List1,List2,""))return 1
		}
	}
	return 0
}

function addLogicChainOrNode(ichain,p,D,k,question,isentrypoint){

	var A=[]
	var a=[]
	var B=[]
	var q=1-p
	var ret=0
	var working=0
	var s=""
	var isinit=0

	// we are setting half of the nodes of the chain T, and the others F
	// (false in a strong chain forces the opposite parity to be true and vice-versa)

	// we could do all chain nodes at once, but this makes for a more human analysis.


	// if chain already done -- nothing to do

	//A and a

	nlogic++

	if(ichain){
		if(Logic.ChainList[p][ichain])return 0

		// if chain is already FALSE then we have our proof -- both false and true lead to same result

		if(Logic.ChainList[q][ichain])return !addLogic(0,0,0,0,"TRUE!!! "+question)

		Logic.ChainList[p][ichain]=ichain
		Logic.ChainList[q][ichain]=ichain


		if(isentrypoint){

			//sorry, I messed up here -- two ways to enter -- this is just to make the statement look better

			// add "nodes of this parity are FALSE"

			if(addLogic(ichain,q,0,0, "The hypothesis is "+question))return 1


			// add "nodes of opposite parity are TRUE"

			if(addLogic(ichain,p,0,1, "The hypothesis is proven if chain "+chainCode(ichain,p,1)+" is proven to be TRUE"))return 1


		}else{


			// from a forced link

			// add "nodes of this parity are TRUE"

			if(addLogic(ichain,p,0,1, "The hypothesis is "+question))return 1


			// add "nodes of opposite parity are FALSE"

			if(addLogic(ichain,q,0,0, "The hypothesis is proven if chain "+chainCode(ichain,q,1)+" is proven to be FALSE"))return 1

		}

		// find all nodes that, "when TRUE, would force opposite parity nodes FALSE"

		A=getAssociatedNodes(ichain,q,Logic.True)

	}else{
		isinit=1
		a=[[0,D,k]]
		if(addLogic(0,0,0,0, "The hypothesis is "+question))return 1
	}
	working=1
	s="The hypothesis is proven if any of the following weakly associated nodes "+chainCode(ichain,q,1)+" are TRUE:"
	while(working){

		if(A.length){

			//B

			nlogic++

			if(addLogic(0,0,A,1,s))return 1

			// add all associated chains of these nodes with SAME PARITY

			if(addAssociatedChains(A,1))return 1
		}

		// recursively find all nodes that "when FALSE would force any one of a SET of nodes TRUE"	

		working=0
		if(!isinit){
			a=[]
			if(getFalseImpliesTrue(a))return 1
		}
		if(a.length){
			if(!A.length && !isinit)nlogic++

			if(addLogic(0,0,a,0,"The hypothesis is proven if any of the following are forced FALSE:"))return 1

			// recursively add all associated chains of these nodes with OPPOSITE PARITY

			// for nice output only -- not required: 
			if(getFalseImpliesTrue([],1))return 1

			B=[]
			if(addAssociatedChains(a,0,B))return 1
			A=[]
			for(var coord in B)A[A.length]=B[coord]
			working=A.length
			if(working)s="The hypothesis is proven if any of the following nodes are TRUE:"
		}
		isinit=0
	}

	// now add all linked strong chains (some may be only indirectly linked through multiple weak links)

	for(var j=1;ichain && j<StrongChains.length;j++)if(j!=ichain){
		if(WeakLinks[ichain+"_"+j+","+q+"/1"] && addLogicChainOrNode(j,1,0,0,"linked by "+chainCode(ichain,q,1)+"-->"+chainCode(j,0,1)))return 1
		if(WeakLinks[ichain+"_"+j+","+q+"/0"] && addLogicChainOrNode(j,0,0,0,"linked by "+chainCode(ichain,q,1)+"-->"+chainCode(j,1,1)))return 1
	}

	return 0
}

function addLogicChainOrNode2(ichain,p,D,k,question,isentrypoint){

	var A=[]
	var a=[]
	var b=[]
	var q=1-p
	var ret=0
	var working=0
	var s=""
	var isinit=0

	// p will be eliminated; q will be TRUE

	// we are setting half of the nodes of the chain T, and the others F
	// (false in a strong chain forces the opposite parity to be true and vice-versa)

	// we could do all chain nodes at once, but this makes for a more human analysis.


	// if chain already done -- nothing to do

	//A and a

	nlogic++

	if(ichain){
		if(Logic.ChainList[p][ichain])return 0

		// if chain is already FALSE then we have our proof -- both false and true lead to same result

		if(Logic.ChainList[q][ichain])return !addLogic(0,0,0,0,"TRUE!!! "+question)

		Logic.ChainList[p][ichain]=ichain
		Logic.ChainList[q][ichain]=ichain


		if(isentrypoint){

			//sorry, I messed up here -- two ways to enter -- this is just to make the statement look better

			// add "nodes of opposite parity are TRUE"

			if(addLogic(ichain,q,0,1, "The hypothesis is "+question))return 1

			// add "nodes of this parity are FALSE"

			if(addLogic(ichain,p,0,0, "The hypothesis forces chain "+chainCode(ichain,p,1)+" to be FALSE"))return 1



		}else{


			// from a forced link

			// add "nodes of this parity are FALSE"

			if(addLogic(ichain,p,0,0, "The hypothesis is "+question))return 1


			// add "nodes of opposite parity are TRUE"

			if(addLogic(ichain,q,0,1, "The hypothesis forces chain "+chainCode(ichain,q,1)+" to be TRUE"))return 1

		}

		// find all nodes that are forced FALSE by this hypothesis"

		a=getAssociatedNodes(ichain,q,Logic.True)
		s="The hypothesis forces the following weakly associated nodes FALSE"

	}else{ //suggesting that a node is true?
		isinit=1
		A=[[0,D,k]]
		if(addLogic(0,0,0,0, "The hypothesis is "+question))return 1
	}
	working=1
	while(working){

		if(a.length){

			//B

			nlogic++

			if(addLogic(0,0,a,0,s))return 1

			// add all associated chains of these nodes with SAME PARITY will also be FALSE

			addLogic(0,0,0,0,"Checking for weakly associated nodes...")
			
			if(addAssociatedChains2(a,0))return 1

		}

		// recursively find all nodes that are forced TRUE by this hypothesis

		working=0
		if(!isinit){
			A=[]
			if(getTrueForcesTrue(A))return 1
		}
		if(A.length){
			if(!a.length && !isinit)nlogic++

			if(addLogic(0,0,A,1,"The hypothesis forces all of the following to be TRUE:"))return 1

			// recursively add all associated chains of these nodes with OPPOSITE PARITY

			// for nice output only -- not required: 
			if(getTrueForcesTrue([],1))return 1

			b=[]
			if(addAssociatedChains2(A,1,b))return 1
			a=[]
			for(var coord in b)a[a.length]=b[coord]
			working=a.length
			if(working)s="The hypothesis forces all of the following nodes FALSE:"
		}
		isinit=0

		if(!working){
			// now add all linked strong chains (some may be only indirectly linked through multiple weak links)
			for(var j=1;ichain && j<StrongChains.length;j++)if(j!=ichain){
				if(WeakLinks[ichain+"_"+j+","+q+"/1"] && addLogicChainOrNode2(j,1,0,0,"linked by "+chainCode(ichain,q,1)+"-->"+chainCode(j,0,1)))return 1
				if(WeakLinks[ichain+"_"+j+","+q+"/0"] && addLogicChainOrNode2(j,0,0,0,"linked by "+chainCode(ichain,q,1)+"-->"+chainCode(j,1,1)))return 1
			}
		}
		if(!working && !interlacedepth && (!isentrypoint || !ichecklockedcandidates&&!ichecklogicsubsets))return 0

		logicSetXArray()
		
		if(!working && isentrypoint && ichecklockedcandidates){
			a=[]
			logicCheckLockedCandidates(a)
			working=a.length
			if(working)s="The hypothesis locks the following "+a.length+" nodes FALSE:"
			if(working && Logic_level<1)Logic_level=1
		}
		if(!working && isentrypoint && ichecklogicsubsets){
			a=[]
			logicCheckSubsets(a)
			working=a.length
			if(working)s="The hypothesis discovered subsets that set the following "+a.length+" nodes FALSE:"
			if(working && Logic_level<2)Logic_level=2
		}
	}

	return 0
}


function logicFoundX(z,type,iscanfirstindex,jlist,ilist,nx,msg){

	var C={}
	var isfound=0
	var hlist=""
	var s=""
	var k=0
	var P=""
	var snew=""

	//Row: jlist are cols, ilist lists indexes into XRow
	//Col: jlist are rows, ilist lists indexes into XCol
	//remove k in all rows of ilist except columns of jlist!

	for(var i=0;i<9;i++)for(var j=0;j<9;j++)if(jlist & Pwr2[j]){
		k=j
		s=msg
		if(type=="Row"||type=="Col"){
			if(iscanfirstindex){
				C=(type=="Row"?Data[i][j]:Data[j][i])
				k=z
				s=(k+1)+(type=="Row"?" in rows ":" in columns ")+xStr(ilist)+" form a "+nx+"x"+nx+" closed circuit "+(nx==2?" (X-Wing)":nx==3?" (Swordfish)":"")
			}else{
				C=(type=="Row"?Data[z][j]:Data[j][z])
				k=i				
				s=nx+"-long "+s+" involving "+(type=="Row"?"columns ":"rows ") + xStr(jlist)
			}
		}else if(type=="Cell"){
			if(iscanfirstindex){
				C=Data[i][z]
			}else{
				C=Data[z][i]
			}
			s=nx+"-long "+s+" involving " + xStr(jlist)
		}else if(type=="Block"){
			C=Blocks[z][j]
			k=i
		}else if(type=="BlockCell"){
			C=Blocks[z][i]
			s=nx+"-long "+s+" involving " + xStr(jlist)
		}


		if(!C.N && C.Allowed[k]&&(Logic.XCell[C.row][C.col]&Pwr2[k])){
			if(ilist & Pwr2[i]){
			}else{
				Logic.FoundList[Logic.FoundList.length]=[0,C,k,s]
				isfound=1
			}
		}
	}
	return isfound
}

function logicSetXArray(){
	initXArray(Logic)
	for(var k=0;k<9;k++)for(var i=0;i<9;i++)for(var j=0;j<9;j++){
		if((Possible.XCell[i][j]^Logic.False.XCell[i][j])&Pwr2[k])xSetArray(Logic,Data[i][j],k)
	}
}

function logicCheckSubsets(a){
	var isOK=1
	Logic.FoundList=a
	for(var p=0;p<9 && isOK;p++)isOK&=!analyzeSlice(Logic,logicFoundX,p,"row")
	for(var p=0;p<9 && isOK;p++)isOK&=!analyzeSlice(Logic,logicFoundX,p,"column")	
	for(var p=0;p<9 && isOK;p++)isOK&=!analyzeSlice(Logic,logicFoundX,p,"3x3 block")
	for(var k=0;k<9 && isOK;k++)isOK&=!analyzeSlice(Logic,logicFoundX,k,"grid")

}

function logicCheckLockedCandidates(A){
	//A is an empty array to be filled with array of nodes [0,D,k]
	//not the most efficient routine here
	var P=Possible
	var j=0
	var i=0
	var b=0
	var p=0
	var n=-1
	var x=0
	for(var k=0;k<9;k++){		
		for(var i=0;i<9;i++){
			x=Logic.XRowSubset[i][k]
			if(xNum(x)==1){
				j=xVal(x)
				b=Data[i][j].block
				x=Logic.XBlockRow[b][k]
				if(xNum(x)>1){
					for(var p=0;p<9;p++)if(Blocks[b][p].row!=i && (Logic.XBlock[b][k]&Pwr2[p])){
						A[A.length]=[0,Blocks[b][p],k,coordOf(Blocks[b][p],k),"bij:",b,i,j,"-1-"
,"P.XRowSubset[i][k],Logic.XRowSubset[i][k]",xStr(Possible.XRowSubset[i][k]),"/",xStr(Logic.XRowSubset[i][k])
,"P.XBlockRow[b][k],Logic.XBlockRow[b][k]",xStr(Possible.XBlockRow[b][k]),"/",xStr(Logic.XBlockRow[b][k])
]
					}
				}
			}
		}
		for(var j=0;j<9;j++){
			x=Logic.XColSubset[j][k]
			if(xNum(x)==1){
				i=xVal(x)
				b=Data[i][j].block
				x=Logic.XBlockCol[b][k]
				if(xNum(x)>1){
					for(var p=0;p<9;p++)if(Blocks[b][p].col!=j && (Logic.XBlock[b][k]&Pwr2[p])){
						A[A.length]=[0,Blocks[b][p],k,coordOf(Blocks[b][p],k),"bij:",b,i,j,"-2-"
,"P.XColSubset[j][k],Logic.XColSubset[j][k]",xStr(Possible.XColSubset[j][k]),"/",xStr(Logic.XColSubset[j][k])
,"P.XBlockCol[b][k],Logic.XBlockCol[b][k]",xStr(Possible.XBlockCol[b][k]),"/",xStr(Logic.XBlockCol[b][k])
]
					}
				}
			}
		}
	}
//if(A.length)addLogic(0,0,0,0,"locking "+A.length+" "+A)
}


function addLogicX(ch,D,k,ListT,ListF,info){

	// add a new node as "if A is TRUE then this is TRUE" or "if A is TRUE then this is FALSE"

	var istrue=(ListT==Logic.True)
	if(ListT.XCell[D.row][D.col]&Pwr2[k])return 0
	addLogic(0,0,0,istrue,"setting "+coordOf(D,k)+(istrue?" TRUE":" FALSE")+" "+info)
	if(ListF.XCell[D.row][D.col]&Pwr2[k]){

		addLogic(0,0,0,istrue,(Logic.isreverse?"found either state for "+coordOf(D,k)+" leads to the same conclusion":coordOf(D,k)+" cannot be both TRUE and FALSE"))
		Logic.terminator=coordOf(D,k)
		return 1
	}
	Logic.Table[k+D.col*9+D.row*81]=ch
	xSetArray(ListT,D,k)
	return 0
}

function checkLogic(isreverse,ijustcheckmagic){


	// this replaces all need for "weak field" checking

	logAddMessage("Hypothesis and "+(isreverse?"Proof":"Disproof"))

	ishowdeadends=ishowdetail

	// Here we are using forward logic
	// "X cannot be eliminated, where X is a strong chain node"
	// 1. find all a that are forced false when X is not eliminated (strong chain nodes; weakly associated nodes)
	// 2. find all A that are forced TRUE when a is false (opposite parity strong chain nodes)
	// 3. find all b that are forced false when A is TRUE (anything in line with those nodes)

	// trick is that we add "human depth" by allowing checking for singles, locked candidates, n-tuples, and grids

	// this tests ALL nodes of each chain at once

	// they are not necessary, but faster, so I've left them in. -- kills MANY birds with one stone


	Logic_nentries=0
	for(var i=1;i<StrongChains.length;i++){
		if(testLogic(i,1,0,0,isreverse,ijustcheckmagic))return 1
		if(testLogic(i,0,0,0,isreverse,ijustcheckmagic))return 1
	}

	//nonetheless, all we really need to do is check all weak nodes as being TRUE?
	//based on the idea that then any related nodes (in strong chains) must be FALSE

	for(var coord in WeakNodes)if(!StrongNodePtr[coord]){
		if(testLogic(0,0,WeakNodes[coord][0][0],WeakNodes[coord][0][2],isreverse,ijustcheckmagic))return 1
	}

	if(!ichecklockedcandidates&&!ichecklogicsubsets)return 0
	for(var i=0;i<9;i++)for(var j=0;j<9;j++)for(var k=0;k<9;k++){
		if(!Data[i][j].N && Data[i][j].Allowed[k]){
		
			coord=coordOf(Data[i][j],k)
			if(!WeakNodes[coord] && !StrongNodePtr[coord]){
				if(testLogic(0,0,Data[i][j],k,isreverse,ijustcheckmagic))return 1
			}
		}
	}
	return 0
}

function checkLogicXVal(xT,xP,xF,type,i,j,isquick){

	// check to see if we are done.
	// xT, xP, and xF are binary bit-sets 2^0 to 2^8 for quicker comparison

	var x=0

	if(xP==0)return 0

	// were all possible set true?

	if(xT==xP){
		addLogic(0,0,0,1,(type=="cell"?"any of the possibilities for cell "+Data[i][j].showinfo+" lead to the same conclusion":type+" "+(i+1)+" is all TRUE for candidate "+(j+1)))
		return 1
	}

	// were two or more set false?

	if(xNum(xF)>1){
		addLogic(0,0,0,0,(type=="cell"?"cell "+Data[i][j].showinfo:"candidate "+(j+1)+" in "+type+" "+(i+1))+" -- more than one FALSE value -- either will force the hypothesis to be TRUE")
		return 1 //one must be false if two are false
	}

	if(isquick)return 0
	if(!ichecklockedcandidates&&!ichecklogicsubsets)return 0

	// were all but ONE possible set true, and this isn't just a short strong chain?


	if(xF==0 && xNum(xP^xT)==1 && xNum(xP)!=2){
		x=1+xVal(xP^xT)
		addLogic(0,0,0,0,type+" "+(i>=0?i+1:"")+" is nearly all TRUE for #"+x+", so a FALSE there would force one of the others TRUE")
		if(Logic_level<1)Logic_level=1
		return -x  //set false
	}
	return 0
}

function checkLogicXVal2(xT,xP,xF,type,i,j,isquick){

	// check to see if we are done.
	// xT, xP, and xF are binary bit-sets 2^0 to 2^8 for quicker comparison

	var x=0

	if(xP==0)return 0

	// were all possible set false?

	if(xF==xP){
		addLogic(0,0,0,0,(i<0?"none of the options for "+type+" are possible":type+" "+(i+1)+" is all FALSE for candidate "+(j+1)))
		return 1
	}

	// were two or more set true?

	if(xNum(xT)>1){
		addLogic(0,0,0,1,(i<0?type:"candidate "+(j+1)+" in "+type+" "+(i+1))+" -- more than one TRUE value -- one of them must be TRUE")
		return 1 //only one can be TRUE
	}

	if(isquick)return 0
	if(!ichecklockedcandidates&&!ichecklogicsubsets)return 0

	// were all but ONE possible set false, and this isn't just a short strong chain?

	if(xT==0 && xNum(xP^xF)==1 && xNum(xP)!=2){
		x=1+xVal(xP^xF)
		addLogic(0,0,0,1,type+" "+(i>=0?i+1:"")+" is nearly all FALSE for #"+x+", requiring a TRUE in that last location")
		if(Logic_level<1)Logic_level=1
		return -x  //set TRUE
	}
	return 0
}

function checkMagic(info){
	for(var i=0;i<9;i++)for(var j=0;j<9;j++)if(!Data[i][j].N){
		if(Logic.True.XCell[i][j]+Logic.False.XCell[i][j]!=Possible.XCell[i][j])return 0
	}
	return 1
}

function dumpLogic(termch){
	var s=""
	for(var i=0;i<Logic.List.length;i++)s+=termch+Logic.List[i][0]
	return s+termch
}

function eliminateMagic(isreverse,slist){
	var A=(isreverse?Logic.True:Logic.False)
	var S=[]
	for(var i=0;i<9;i++)for(var j=0;j<9;j++){
		S=xList(A.XCell[i][j])
		for(var m=0;m<S.length;m++)eliminateK(Data[i][j],S[m],"Magic Cell: "+slist)
	}
	addAutoMsg("G","Magic Cells found: "+slist)
	return 1
}

function getFalseImpliesTrue(A,isquick){

	// This is Nick70's idea at http://www.setbb.com/phpbb/viewtopic.php?t=300&start=0&mforum=sudoku

	// Basically, once all but one of a row, column, block, for a given k value, or any value for a cell have
	// been found to be "if TRUE then A is TRUE", the last can be filled in as an abc-type
	// "if FALSE then A is TRUE", because if it is false, then at least ONE of the others must be true.

	// I have expanded this to "if two are of the "if FALSE then A is TRUE", then A must be TRUE, because at
	// least one of the false ones must be false!

	var xT=0
	var xF=0
	var xP=0
	var x=0

	Logic_nentries++

	for(var i=0;i<9;i++)for(var j=0;j<9;j++){
		x=checkLogicXVal(Logic.True.XRow[i][j],Possible.XRow[i][j],Logic.False.XRow[i][j],"row",i,j,isquick)
		if(x>0)return 1
		if(x<0)A[A.length]=[0,Data[i][-1-x],j]

		x=checkLogicXVal(Logic.True.XCol[i][j],Possible.XCol[i][j],Logic.False.XCol[i][j],"column",i,j,isquick)
		if(x>0)return 1
		if(x<0)A[A.length]=[0,Data[-1-x][i],j]

		x=checkLogicXVal(Logic.True.XBlock[i][j],Possible.XBlock[i][j],Logic.False.XBlock[i][j],"3x3 block",i,j,isquick)
		if(x>0)return 1
		if(x<0)A[A.length]=[0,Blocks[i][-1-x],j]

		x=(Data[i][j].N?0:checkLogicXVal(Logic.True.XCell[i][j],Possible.XCell[i][j],Logic.False.XCell[i][j],"cell "+Data[i][j].showinfo,-1,-1,isquick))
		if(x>0)return 1
		if(x<0)A[A.length]=[0,Data[i][j],-1-x]
	}
	var testk=0
	return 0
}

function getTrueForcesTrue(a,isquick){

	// this can be seen as adding depth.

	// Basically, once all but one of a row, column, block, for a given k value, or any value for a cell have
	// been found to be FALSE", the last can be filled in as an ABC-type
	// "if A is TRUE, then this is also TRUE", because if it is false, then at least ONE of the others must be true.

	// I have expanded this to "if two are "TRUE", then the hypothesis is proven, because at
	// least one of the false ones must be false!

	var x=0

	Logic_nentries++

	for(var i=0;i<9;i++)for(var j=0;j<9;j++){
		x=checkLogicXVal2(Logic.True.XRow[i][j],Possible.XRow[i][j],Logic.False.XRow[i][j],"row",i,j,isquick)
		if(x>0)return 1
		if(x<0)a[a.length]=[0,Data[i][-1-x],j]

		x=checkLogicXVal2(Logic.True.XCol[i][j],Possible.XCol[i][j],Logic.False.XCol[i][j],"column",i,j,isquick)
		if(x>0)return 1
		if(x<0)a[a.length]=[0,Data[-1-x][i],j]

		x=checkLogicXVal2(Logic.True.XBlock[i][j],Possible.XBlock[i][j],Logic.False.XBlock[i][j],"3x3 block",i,j,isquick)
		if(x>0)return 1
		if(x<0)a[a.length]=[0,Blocks[i][-1-x],j]

		x=(Data[i][j].N?0:checkLogicXVal2(Logic.True.XCell[i][j],Possible.XCell[i][j],Logic.False.XCell[i][j],"cell "+Data[i][j].showinfo,-1,-1,isquick))
		if(x>0)return 1
		if(x<0)a[a.length]=[0,Data[i][j],-1-x]
	}
	var testk=0
	return 0
}

function setAllFalse(coord0,type,m,n,p,B){


	// check rows, columns, blocks, and cells for possible but TRUE-forcing values

	var xp=Possible[type][m][n]^Pwr2[p]
	var xt=Logic.True[type][m][n]
	var xf=Logic.False[type][m][n]
	xf^=(xf&Pwr2[p])
	xp^=(xp&Pwr2[p])
	var x=xp^xf

	var L=[]
	var A=[]
	var coord=""
	if(!x)return 0
	if(x&xt){
		addLogic(0,0,0,0,"Two values in "
			+(type=="XCell"?"Cell r"+(m+1)+"c"+(n+1)+"(#"+(p+1)+","+xStr(x&xt)+")"
			:type.substring(1,type.length)+" "+(m+1)+" for #"+(n+1))
			+", either TRUE, disproves the hypothesis")
		return 1
	}
	L=xList(x)
	for(var ipt=0;ipt<L.length;ipt++){
		p=L[ipt]
		if(type=="XRow"){
			A=[0,Data[m][p],n]
		}else if(type=="XCol"){
			A=[0,Data[p][m],n]
		}else if(type=="XBlock"){
			A=[0,Blocks[m][p],n]
		}else if(type=="XCell"){
			A=[0,Data[m][n],p]
		}
		coord=coordOf(A[1],A[2])
		if(!B[coord])B[coord]=A
	}
	return 0
}

function setAllFalseExcept(coord,D,k,B){

	// a cell "x" was found to be TRUE
	// so now we mark all others in its subsets, which must be forced FALSE
	// and this gives us another set of F nodes that need checking for associated chains

	var i=D.row
	var j=D.col
	var b=D.block
	var p=D.bptr
	var x=0
	if(setAllFalse(coord,"XRow",i,k,j,B))return 1
	if(setAllFalse(coord,"XCol",j,k,i,B))return 1
	if(setAllFalse(coord,"XBlock",b,k,p,B))return 1
	if(setAllFalse(coord,"XCell",i,j,k,B))return 1
	return 0
}

function setAllTrue(coord0,type,m,n,p,B){


	// check rows, columns, blocks, and cells for possible but non-TRUE-forcing values

	var xp=Possible[type][m][n]^Pwr2[p]
	var xt=Logic.True[type][m][n]
	var xf=Logic.False[type][m][n]
	xt^=(xt&Pwr2[p])
	xp^=(xp&Pwr2[p])
	var x=xp^xt

	var L=[]
	var A=[]
	var coord=""
	if(!x)return 0
	if(x&xf){
		addLogic(0,0,0,0,"Two values in "
			+(type=="XCell"?"Cell r"+(m+1)+"c"+(n+1)+"(#"+(p+1)+","+xStr(x&xf)+")"
			:type.substring(1,type.length)+" "+(m+1)+" for #"+(n+1))
		+", either false, proves the hypothesis")
		return 1
	}
	L=xList(x)
	for(var ipt=0;ipt<L.length;ipt++){
		p=L[ipt]
		if(type=="XRow"){
			A=[0,Data[m][p],n]
		}else if(type=="XCol"){
			A=[0,Data[p][m],n]
		}else if(type=="XBlock"){
			A=[0,Blocks[m][p],n]
		}else if(type=="XCell"){
			A=[0,Data[m][n],p]
		}
		coord=coordOf(A[1],A[2])
		if(!B[coord])B[coord]=A
	}
	return 0
}

function setAllTrueExcept(coord,D,k,B){

	// a cell "x" was found to be "if FALSE, then A is TRUE"
	// so now we mark all others in its subsets "if TRUE then "x" is FALSE, so A is TRUE"
	// and this gives us another set of T nodes that need checking for associated chains

	var i=D.row
	var j=D.col
	var b=D.block
	var p=D.bptr
	var x=0
	if(setAllTrue(coord,"XRow",i,k,j,B))return 1
	if(setAllTrue(coord,"XCol",j,k,i,B))return 1
	if(setAllTrue(coord,"XBlock",b,k,p,B))return 1
	if(setAllTrue(coord,"XCell",i,j,k,B))return 1
	return 0
}

function showNodeList(List){
	var s=""
	for(var i=0;i<List.length;i++)s+=" "+(List[i][0]?List[i][0]:List[i][1].showinfo)
	return s.substring(1,s.length)
}

function testLogic(ichain,p,D,k,isreverse,ijustcheckmagic){
	var n=0
	var s=(isreverse?"":"not")
	var st=""
	var isfound=0
	var pdelete=0
	var ilevel=Logic_level

	Logic={}
	Logic.True={}
	Logic.False={}
	Logic.List=[]
	Logic.ChainList=[[],[]]
	Logic.Table=[]

	Logic.terminator=""
	Logic.isreverse=isreverse
	Logic.listed=""

	initXArray(Logic.True)
	initXArray(Logic.False)
	nlogic=0

	Logic.debug=""

	if(ichain){
		pdelete=(isreverse?p:1-p)
		if(isreverse){
			pdelete=p
			if(addLogicChainOrNode(ichain,1-p,0,0,"this: Chain "+chainCode(ichain,p,1)+" can be eliminated based on hypothesis",1)){
				//st=Logic_nentries+" entries to getFalseImpliesTrue()"
				isfound=1
			}
		}else{
			pdelete=1-p
			if(addLogicChainOrNode2(ichain,p,0,0,"this: Chain "+chainCode(ichain,1-p,1)+" cannot be eliminated based on hypothesis",1)){
				//st=Logic_nentries+" entries to getTrueImpliesTrue()"
				isfound=1
			}
		}
		if(isfound && !ijustcheckmagic){
			addLogic(0,0,0,-1,"Logical analysis: Chain "+chainCode(ichain,pdelete,1))
			eliminateChainParity(ichain,pdelete,"chain "+chainCode(ichain,pdelete,1)+" may be eliminated based on hypothesis","P")
			return 1
		}else if(icheckmagic){
			if(!checkMagic("chain "+chainCode(ichain,p,1)))return 0
			s="The following nodes in chain "+ichain+" are magic: "+getChainListing(ichain,pdelete)
			redlist+=s
			logAddMessage(s)
			if(!ijustcheckmagic)eliminateMagic(isreverse,s)
			return !ijustcheckmagic
		}
		if(ishowdeadends)s="Logical analysis: Chain "+chainCode(ichain,pdelete,1)
	}else{
		if(isreverse){
			if(addLogicChainOrNode(0,0,D,k,"this: Node "+coordOf(D,k)+" can be eliminated based on hypothesis",1)){
				//st=Logic_nentries+" entries to getFalseImpliesTrue()"
				isfound=1
			}
		}else{
			if(addLogicChainOrNode2(0,0,D,k,"this: Node "+coordOf(D,k)+" cannot be eliminated based on hypothesis",1)){
				//st=Logic_nentries+" entries to getTrueImpliesTrue()"
				isfound=1
			}
		}
		if(isfound && !ijustcheckmagic){
			addLogic(0,0,0,-1,"Logical Analysis: Node "+coordOf(D,k))
			s="node "+coordOf(D,k)+" may be eliminated based on hypothesis"
			eliminateK(D,k,s)
			//logAddMessage(st)
			addAutoMsg("P",s)
			return 1
		}else if(icheckmagic){
			if(!checkMagic(D.showinfo))return 0
			s="Cell "+D.showinfo+" is a magic cell. Set its value to "+(k+1)+" to solve the puzzle."
			redlist+=D.showinfo
			logAddMessage(s)
			if(!ijustcheckmagic)eliminateMagic(isreverse,s)
			return !ijustcheckmagic
		}
		if(ishowdeadends)s="Logical Analysis: Node "+coordOf(D,k)
	}

	if(ishowdeadends)addLogic(0,0,0,-2,s)
	Logic_level=ilevel   // reset level to previous

	return 0
}