XY Chain

XY-Chainはbivalueの連結で生じるLockedを用いた解析アルゴリズムです。
次の図は XY-Chainのイメージです。着目数字をaとしてbivalueのセルから開始し、bivalueセルを連結します。 イメージ図では異なる数字で繋いでいますが、同じ数字が現れることもあります。連の先端のセルで開始セルと同じ数字a持つとします。 このとき開始セル・先端セルと同時に関係するセルでは、候補数字aが除外できます。

XY Chain

XY Chainの例です。右図には2つの連が重なっています。

XY Chain   XY Chain

.5....3...71.43...2..61...9..5....7.7.34..19.1...9.8..3.2.64.5........185.927.4..
...71...9.14.9.....9....3.72...4.5.186.1.72......8.7....6471..5.......689.25..17.

XY Chain解析プログラム

解析プログラムは、bivalueのリンク列の生成関数と XY Chainの成立をチェックするプログラムからなります。

(0)bivalueの連生成関数

連生成は他のチェイン系とほぼ同じ方法（波及的探索処理）です。Bit81のID要素を使って着目したセルと着目数字を呼び出し元に通知しています[14]。 

public partial class CellLinkGen: AnalyzerBaseV2{
    private IEnumerable<Bit81[]> _GetXYChain( List<int> LKRec ){
        List<UCell> TBDbv = pBDL.FindAll(p=>(p.FreeBC==2));  //BV:bivalue
        foreach( var PS in TBDbv ){
            int rcS=PS.rc;
            foreach( var no in PS.FreeB.IEGet_BtoNo() ){
                int noB=(1<<no);
                Bit81[] CRL=new Bit81[2];
                CRL[0]=new Bit81(); //連結する着目数字の位置
                CRL[1]=new Bit81(); //連結するその他数字の位置
                CRL[0].ID=rcS; CRL[1].ID=no;

                Bit81 CnctdCs = ConnectedCells[rcS]; //開始セルの関連セル群(行列ブロック関連）
                Queue<int> rcQue=new Queue<int>();
                int no0 = pBDL[rcS].FreeB.BitReset(no).BitToNum();//開始セルのもう一方の数字
                rcQue.Enqueue( (no0<<8)|rcS );

                LKRec.Clear();
                while(rcQue.Count>0){
                    int rcX=rcQue.Dequeue();
                    int no1=rcX>>8;
                    int rc1=rcX&0xFF;
                    foreach( var LK in CeLKMan.IEGetRcNoType(rc1,no1,1) ){ //強リンクで連結
                        int rc2= LK.rc2;
                        if( pBDL[rc2].FreeBC!=2 ) continue;     //2数字セルのみ
                        if( CRL[0].IsHit(rc2) || CRL[1].IsHit(rc2) ) continue;//ループ除外
                
                        //開始セルと関連し同じ数字を持つセルは除外
                        if( CnctdCs.IsHit(rc2) && (pBDL[rc2].FreeB&noB)>0 ) continue; 

                        int no2 = (pBDL[rc2].FreeB.BitReset(no1)).BitToNum();//2数字のもう一方
                        int nx=(no2==no)? 0: 1;
                        CRL[nx].BPSet(rc2);
                        rcQue.Enqueue( (no2<<8)|rc2 ); //次ノードをQueueに入れる
                        LKRec.Add((rc1<<8|rc2)); //リンクを記録
                    }
                }
                if( CRL[0].Count>0 || CRL[1].Count>0 ) yield return CRL;
            }
        }
        yield break;
    }
}

(1)XY Chain

リンク列生成関数の結果を用いて、開始セルとリンク先端のセルの両方に関連するセルを探します。 結果の表示用に始点・終点間のリンク列のみを抽出する SelectLink_XYChain を用いています。 これは、解析アルゴリズムとしては必要ありません。 

public partial class CellLinkGen: AnalyzerBaseV2{
    public bool XYChain(){
        CeLKMan.PrepareCellLink(1);    //strongLink生成

        List<int> LKRec=new List<int>();
        foreach( var CRL in _GetXYChain(LKRec) ){
            int rcS=CRL[0].ID;
            int no=CRL[1].ID, noB=(1<<no);

            Bit81 ELM = ConnectedCells[rcS] - (CRL[0]|CRL[1]);
            if( ELM.IsZero() ) continue;

            Bit81 ELM2=new Bit81();
            bool XYChainF=false;
            foreach( var E in ELM.IEGetUCeNoB(pBDL,noB) ){
                if( CRL[0].IsHit(ConnectedCells[E.rc]) ){
                    E.CancelB=noB; XYChainF=true;
                    ELM2 |= CRL[0]&ConnectedCells[E.rc];
                }
            }
            if( !XYChainF )  continue;

            //===== XY-Chain fond =====
            SolCode=2;
            String SolMsg="XY Chain";
            Result=SolMsg;

            int rcE;
            foreach( var P in ELM2.IEGetUCeNoB(pBDL,noB) ) P.SetNoBBgColor(noB,AttCr,SolBkCr);
            Bit81 ELM2cpy=ELM2.Copy();
            while( (rcE=ELM2.FindFirstrc())>=0 ){
                string stR="";
                Bit81 XYchainB = _SelectLink_XYChain(LKRec,rcS,rcE,noB,ref stR)-ELM2cpy; 
                if(SolInfoDsp)  SolMsg+="\r "+stR;

                foreach( var P in XYchainB.IEGetUCeNoB(pBDL,0x1FF) ){
                    P.SetNoBBgColor(P.FreeB,AttCr,SolBkCr2);
                }
                ELM2.BPReset(rcE);
            }
            if(SolInfoDsp)  ResultLong = SolMsg;
            pBDL[rcS].SetNoBBgColor(noB,AttCr,SolBkCr);
                
            if( !AnMan.SnapSaveGP(true) )  return true;
            XYChainF=false;
        }
        return false;
    }
    private Bit81 _SelectLink_XYChain( List<int> LinkRecord, int rcS, int rcE, int noB, ref string stRet ){
        //(直接関係する解チェインのみを抽出して表示する）
        Bit81 XYchainB=new Bit81();
        int rcX=rcE;
        XYchainB.BPSet(rcX);
        List<int> Q=new List<int>();
        if( SolInfoDsp ) Q.Add(rcX);
        while(rcX!=rcS){
            rcX=LinkRecord.Find(p=>(p&0xFF)==rcX);
            if( rcX==0 ) break;
            rcX=(rcX>>8);
            XYchainB.BPSet(rcX);
            if( SolInfoDsp ) Q.Add(rcX);
        }
        if(SolInfoDsp){
            Q.Reverse();
            string st="";
            Q.ForEach(p=> st += "-["+(p/9*10+p%9+11)+"]");
            stRet=">"+st.Substring(1);
        }
        return XYchainB;
    }
}
Top