EmptyRectangle

EmptyRectangleは、着目数字に関するブロック内セル配置と強いリンクで構成されるパターン型の解析アルゴリズムです。 次の図にEmptyRectangleのブロック（□）とブロック内のセル配置（）と関係パターンを示します(実線：強いリンク、破線：弱いリンク）。セルが真なら、直接の関係と強いリンクにより、ブロック内のセル（）はいずれも偽となります。 つまり、のセル群の配置の場合、セルはLockedにあり、セルから候補数字が除外されます。 EmptyRectangle(ER)の名称は、着目するブロックから点線が通過するセルを除く4セルには着目数字がない、ことに由来します。

EmptyRectangleの解析アルゴリズムは、上の図を作る手順とおりです。 まずは図を十分に理解するのがよいでしょう。

1. 着目数字Xの設定
2. 着目ブロックの選択
3. 着目ブロック内の軸となるセルの選択
4. 軸セルの行・列を除くと、着目ブロック内にERができることを確認
5. 着目ブロック外に強いリンクを探す
6. 着目ブロックの軸、強いリンクと 四角形を形成する位置にセルを探す。

EmptyRectangleの例を示します。全て同じ問題の同じ場面での異なるEmptyRectangleです。 下段中央も同じ問題の同じ場面ですが、適用しているアルゴリズムはSkyscraperです。異なるアルゴリズムの適用ですが、上段中央と同じセルで候補が除外されます。

EmptyRectangleの解析プログラム

EmptyRectangleの解析プログラムは、前述のアルゴリズムをそのままコード化します。
「09」着目ブロック内の着目数字の配置をビット表現し、これを用いて軸によりERの成立をチェックします。
[25,30]着目ブロック外に行と列を設定し、これと軸セルの行・列で四角形を作ります。その四角形にあう強いリンクと除外候補セルを探します。
このコードはスマートさにやや欠けるので何とか改善したいと思っています。しばらくしたら、このサイトを訪ねてみてください。 改良コードがあるかもしれません。

public partial class CellLinkGen: AnalyzerBaseV2{ 
    public bool  EmptyRectangle( ){
        CeLKMan.PrepareCellLink(1);         //strongLink生成
        
        for( int no=0; no<9; no++ ){        //着目数字
            int noB = 1<<no;
            for( int bx=0; bx<9; bx++ ){    //着目ブロック
                int erB=pBDL.IEGetCellInHouse(bx+18,noB).Aggregate(0,(Q,P)=>Q|(1<<P.nx));
                if(erB==0) continue;

                for( int er=0; er<9; er++ ){//ブロック内の着目セル
                    int Lr=er/3, Lc=er%3;   //ブロックローカル行・列
                    int rxF = 7<<(Lr*3);    //7=1+2+4
                    int cxF = 73<<Lc;       //73=1+8+64
        
                    if( (erB&rxF)==0 || erB.DifSet(rxF)==0 )  continue; //Lr行(行条件検査)
                    if( (erB&cxF)==0 || erB.DifSet(cxF)==0 )  continue; //Lc列(列条件検査)
                    if( erB.DifSet(rxF|cxF)>0 )               continue; //Lr行+Lc列(ER条件検査)
                    
                    int r1 = bx/3*3+Lr;     //絶対行に換算
                    int c1 = (bx%3)*3+Lc;   //絶対列に換算

                    foreach( var P in HouseCells[9+c1].IEGetUCeNoB(pBDL,noB).Where(Q=>Q.b!=bx) ){
                        foreach( var LK in CeLKMan.IEGetRcNoBTypB(P.rc,noB,1) ){
                            UCell Elm=pBDL[r1*9+LK.UCe2.c];
                            if( Elm.b!=bx && (Elm.FreeB&noB)>0 ){ //除外できる数字がある
                                EmptyRectangle_SolResult( no, bx, LK, Elm );
                                if( !AnMan.SnapSaveGP(true) )  return true;
                            }
                        }
                    }

                    foreach( var P in HouseCells[0+r1].IEGetUCeNoB(pBDL,noB).Where(Q=>Q.b!=bx) ){
                        foreach( var LK in CeLKMan.IEGetRcNoBTypB(P.rc,noB,1) ){
                            UCell Elm=pBDL[LK.UCe2.r*9+c1];
                            if( Elm.b!=bx && (Elm.FreeB&noB)>0 ){ //除外できる数字がある
                                EmptyRectangle_SolResult( no, bx, LK, Elm );
                                if( !AnMan.SnapSaveGP(true) )  return true;
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
    
    private void EmptyRectangle_SolResult(  int no, int bx, UCellLink PLK, UCell PElm ){
        int noB=(1<<no);
        SolCode = 2;
        Result = "EmptyRectangl #"+(no+1) +" in B"+(bx+1);
        PElm.CancelB = noB;    //キャンセル数字設定
        if( !SolInfoDsp ) return;
            
        ResultLong = "EmptyRectangl";
        PLK.UCe1.SetNoBBgColor( noB, AttCr, SolBkCr2 );  //強いリンクをマーク
        PLK.UCe2.SetNoBBgColor( noB, AttCr, SolBkCr2 );  //強いリンクをマーク
            
        string st="";
        foreach( var Q in pBDL.IEGetCellInHouse(bx+18,noB) ){
            Q.SetNoBBgColor(noB,AttCr,SolBkCr);   //empty rectangle
            st += " "+Q.rc.ToRCString();
        }
        string msg="\r         digit: #"+(no+1) +"\r            ER: B"+(bx+1)+"("+st.ToString_SameHouseComp()+")";
        msg +="\r        S-Link: "+PLK.rc1.ToRCString()+"-"+PLK.rc2.ToRCString();
        msg +="\rEliminatedCell: "+PElm.rc.ToRCString();
        ResultLong = "EmptyRectangl"+msg;
    }

}