XY-Wing

XY-Wingは、候補数字が2個のセル(bivalue cell)によるLockedの解析アルゴリズムです。 次の図で解説します。 青枠と緑枠の3セルがbivalueで互いに弱いリンクで結びついているとき、青枠セルと弱いリンクで繋がるオレンジ枠のセルの候補数字はaではありません。
XY-Wing
解析アルゴリズムは、次のとおりです。リンクの数字は図のとおりxとyとaです。

  1. bivalueセルのリストを作成する
  2. bivalueセルのリストから軸とするセル(Pivotセル)を選ぶ
  3. 軸セルに接続するbivalue弱リンクのリストを作成する
  4. bivalue弱リンクリストから、2リンクを選ぶ（組合せ選択）
  5. 2リンクは、他端セルが異なり、数字組（axとay)も異なることが条件である。
  6. 2リンクの他端の影響圏セルXを求める
  7. 2リンクの他端とセルXに共通の数字(a)があることが条件である

XY-Wingの例を示します。
XY-Wing XY-Wing XY-Wing

.1..7.69.4.6.9..1.5.9.2...87....9....9..3..8....8....41...6.8.9.8..4.7.5.67.8..4.
6..1....7..18.73...2.3...9..5.9.8641.........1482.6.3..7...2.1...64.18..8....3..4
..8..5..6.3.......6.2.4.5.7...384.59..65..2.39..7...4...4.5.8.....2.8...8.946....


XY-Wingの解析プログラム

XY-Wingの解析プログラムです。上記のアルゴリズムを順にコード化してあります。 このコードのポイントは次の4点です。後の2つは、Bit表現とBit演算を利用して効率よく求めています。

  1. bivalueセルのリストを作る
  2. 着目セルに接続するbivalue弱リンクのリストを作る
  3. 2つのbivalue弱リンクからlockedとなるセルを求める。
  4. 除外候補数字を求める。

public partial class CellLinkGen: AnalyzerBaseV2{
    public bool XYwing( ){
        if(BVCellLst==null)  BVCellLst = pBDL.FindAll(p=>(p.FreeBC==2)); //BV:bivalue
        if(BVCellLst.Count<3) return false;
        CeLKMan.PrepareCellLink(2);    //weak Link生成

        bool XYwing=false;
        foreach( var P0 in BVCellLst ){
            List<UCellLink> BVLKLst =CeLKMan.IEGetRcNoBTypB(P0.rc,0x1FF,2).Where(R=>R.BVFlag).ToList();
                    //foreach( var P in BVLKLst ) Console.WriteLine(P);
            if(BVLKLst.Count<2) continue;

            var cmb = new Combination(BVLKLst.Count,2);
            int nxt=1;
            while(cmb.Successor(nxt)){
                UCellLink LKA=BVLKLst[cmb.Cmb[0]], LKB=BVLKLst[cmb.Cmb[1]];
                UCell Q=LKA.UCe2, R=LKB.UCe2;
                if( Q.rc==R.rc || LKA.no==LKB.no ) continue;

                Bit81 Q81 = ConnectedCells[LKA.rc2]&ConnectedCells[LKB.rc2];
                if(Q81.Count<=0) continue;

                int noB = Q.FreeB.DifSet(1<<LKA.no) & R.FreeB.DifSet(1<<LKB.no);
                if(noB<0) continue;
                int no=noB.BitToNum();

                string msg2="";
                foreach( var A in Q81.IEGetUCeNoB(pBDL,noB) ){
                    if( A==P0 || A==Q || A==R ) continue;
                    A.CancelB=noB; XYwing=true;
                    if(SolInfoDsp) msg2+=" "+A.rc.ToRCString()+"(#"+(no+1)+")";
                }

                if( XYwing ){
                    SolCode=2;
                    P0.SetNoBColor(P0.FreeB,AttCr);
                    P0.SetCellBgColor(SolBkCr);
                    Q.SetCellBgColor(SolBkCr);
                    R.SetCellBgColor(SolBkCr);

                    string msg0= " Pivot: "+_XYwingResSub(P0);
                    string msg1= " Pin: "+_XYwingResSub(R) +" ,"+_XYwingResSub(Q);
                    Result="XY Wing"+msg0;
                    if( SolInfoDsp ){
                        ResultLong="XY Wing\r     "+msg0+"\r       "+msg1+"\r Eliminated:"+msg2;
                    }
                    if( !AnMan.SnapSaveGP() )  return true;
                    XYwing=false;
                }
            }
        }
        return false;
    }
    private string _XYwingResSub( UCell P ){
        string st=P.rc.ToRCString()+"(#"+P.FreeB.ToBitString(9).Replace(".","")+")";
        return st;
    }
}


Top