//CHECKJS C:\temp\sudoku\subsets.js 11/6/2005 12:29:59 PM //subsets.js hansonr@stolaf.edu 7:00 AM 10/28/2005 // handles all subset elimination, including n-tuples, x-wings, swordfish, etc. wingtype = 0 function analyzeSlice(P,foundFunction,m,type,idonochecks){ //all hidden and naked ntuples, simple xwings, swordfish, W-constraints // p>=0 block // i>=0 row scan // j>=0 column scan // k>=0 candidate scan var List=new Array() var ifound=0 var i=-1 var j=-1 var k=-1 var p=-1 var icheckalmostlockedx=(P==Possible && igetalmostlockedx) var icheckalmostlockedy=(P==Possible && igetalmostlockedy) iseliminated=0 if(type=="3x3 block"){ p=m //naked sets in block p List=new Array() for(var i=0;i<9;i++)if(xNum(P.XBlockCell[p][i])>=2)List[List.length]=i ifound=analyzeX(P,foundFunction,p,"BlockCell",0,0,List,0,0,0,0,0,"naked set in 3x3 block "+(p+1),icheckalmostlockedy,idonochecks) if(ifound==1)addAutoMsg("Sn"+wingtype,type) if(ifound)return 1 //hidden sets in block p List=new Array() for(var k=0;k<9;k++)if(xNum(P.XBlock[p][k])>=2)List[List.length]=k ifound=analyzeX(P,foundFunction,p,"Block",0,0,List,0,0,0,0,0,"hidden set in 3x3 block "+(p+1),0,idonochecks) if(ifound==1)addAutoMsg("Sh"+wingtype,type) return(ifound?1:0) } if(type=="row"){ i=m //naked sets in row i List=new Array() for(var j=0;j<9;j++)if(xNum(P.XCell[i][j])>=2)List[List.length]=j ifound=analyzeX(P,foundFunction,i,"Cell",0,0,List,0,0,0,0,0,"naked set in row "+(i+1),icheckalmostlockedy,idonochecks) if(ifound==1)addAutoMsg("Sn"+wingtype,type) if(ifound)return 1 //hidden sets in row i List=new Array() for(var k=0;k<9;k++)if(xNum(P.XCol[i][k])>=2)List[List.length]=k ifound=analyzeX(P,foundFunction,i,"Col",0,0,List,0,0,0,0,0,"hidden set in column "+(i+1),0,idonochecks) if(ifound==1)addAutoMsg("Sh"+wingtype,type) return(ifound?1:0) } if(type=="column"){ j=m //naked sets in column j List=new Array() for(var i=0;i<9;i++)if(xNum(P.XCell[i][j])>=2)List[List.length]=i ifound=analyzeX(P,foundFunction,j,"Cell",0,1,List,0,0,0,0,0,"naked set in column "+(j+1),icheckalmostlockedy,idonochecks) if(ifound==1)addAutoMsg("Sn"+wingtype,type) if(ifound)return 1 //hidden sets in column j List=new Array() for(var k=0;k<9;k++)if(xNum(P.XRow[j][k])>=2)List[List.length]=k ifound=analyzeX(P,foundFunction,j,"Row",0,0,List,0,0,0,0,0,"hidden set in row "+(j+1),0,idonochecks) if(ifound==1)addAutoMsg("Sh"+wingtype,type) return(ifound?1:0) } if(type=="grid"){ k=m //X-Wings, Swordfish, etc. Row-based List=new Array() for(var i=0;i<9;i++)if(xNum(P.XCol[i][k])>=2)List[List.length]=i ifound=analyzeX(P,foundFunction,k,"Col",1,1,List,0,0,0,0,0,"row-based grid elimination",icheckalmostlockedx,idonochecks) if(ifound)return 1 //X-Wings, Swordfish, etc. Column-based List=new Array() for(var i=0;i<9;i++)if(xNum(P.XRow[i][k])>=2)List[List.length]=i ifound=analyzeX(P,foundFunction,k,"Row",1,1,List,0,0,0,0,0,"column-based grid elimination",icheckalmostlockedx,idonochecks) return(ifound?1:0) } } function analyzeX(P,foundFunction,z,type,isgrid,iscanfirstindex,List,ipt,jlist,ilist,nx,ny,msg,icheckalmostlocked,idonochecks){ //return 1 on elimination // corrected 8:00 PM 12/30/2008 var maxdim=(icheckalmostlocked && (!isgrid || !idoalscolumns || idoalslarge)?List.length - 1:List.length/2) if(ipt>=List.length||nx>maxdim||ny>maxdim)return 0 var maxlen=maxdim+1 //propagate to next row var found = analyzeX(P,foundFunction,z,type,isgrid,iscanfirstindex,List,ipt+1,jlist,ilist,nx,ny,msg,icheckalmostlocked,idonochecks) if(found)return found //OR in these rows and count them var i=List[ipt] //another row/col ilist+=Pwr2[i] jlist|=(iscanfirstindex?P["X"+type][i][z]:P["X"+type][z][i]) nx=xNum(jlist) ny++ if(nx>maxlen)return 0 //ny==1,nx==2 here would be strong edge if((isalsfull || !(ny ==1 && nx == 2)) && nx==ny+1 && icheckalmostlocked && addAlmostLocked(nx,ny,z,isgrid,jlist,ilist,type,iscanfirstindex,maxdim,idonochecks)) return 2 if(ny==nx && foundFunction(z,type,iscanfirstindex,jlist,ilist,nx,msg,List.length,idonochecks))return 1 return analyzeX(P,foundFunction,z,type,isgrid,iscanfirstindex,List,ipt+1,jlist,ilist,nx,ny,msg,icheckalmostlocked,idonochecks) } function checkGrids(idonochecks){ var isOK=1 logAddMessage("Checking for grids") for(var k=0;k<9 && (solving||isOK);k++)isOK&=!analyzeSlice(Possible,foundSubset,k,"grid",idonochecks) return !isOK } function checkSubsets(A, idonochecks){ logAddMessage("Checking for subset elimination") var isOK=1 //A is some permutation of ["3x3 block","row","column"] for(var p=0;p<9;p++)for(var i=0;i<3 && (solving && iShowAnswers||isOK);i++) isOK&=!analyzeSlice(Possible,foundSubset,p,A[i],idonochecks) return !isOK } function foundSubset(z,type,iscanfirstindex,jlist,ilist,nx,msg,xdim,idonochecks){ if (idoalsonly)return 0 var C=new Array() var isfound=0 var hlist="" var s="" var k=0 var isallowed=0 var P="" var snew="" var isNxN = 0 var smsg="" var wcode="" wingtype=Math.min(nx,xdim-nx) // with almost-locked sets we have to go over 1/2-way here //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){ isNxN = 1 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 s=nx+"-long "+s+" involving " + xStr(ilist) }else if(type=="BlockCell"){ C=Blocks[z][i] s=nx+"-long "+s+" involving " + xStr(jlist) } if(!C.N && C.Allowed[k]){ if(ilist & Pwr2[i]){ hlist+=C.showinfo }else if (!idonochecks){ eliminateK(C,k,s) isfound=1 if(isNxN && snew.indexOf(s)<0) { if(Wing_level