ALS
数独の高度な解法では、ALS（Almost Locked Set）が使われます。
(1)ALS
Locked Setは、同じhouseに属する"n個のセルにn個の候補数字がある"状態で、 どのセルがどの数字かは決まらないが、全体としてLocked状態です。 ALSは同じhouseに属する"n個のセルにn+1個の候補数字"がある"ほぼLocked"状態です。 ALS外で数字が確定しALSから数字が除かれると、ALSはLockedSetになります。 これだけでは解法として成立しませんが、何かと組合せて様々な解析アルゴリズムが作れます。 最小のALSは、"1セル2候補数字"です。
(2)RCC
2つのALSの関係する解析アルゴリズムでは、共通の数字が制限する効果を利用します。
次の図には2つのALSがあり（青と緑の点線枠）、これらが次の条件を満たすとき、その数字をRCC (Restricted Common Candidate:制限された共通候補）と呼びます。
条件:重なりのない2つのALSに共通の数字があり、それらが同じhouse内にある。
(オレンジ点線枠、ALSのhouseとは異なる）。
RCCは同じhouseに属するので、RCCは一方のALSのみ真であり、他方のALSではRCCは偽です。ただし、どちらのALSで真かは決定していません。
ここに何らかの条件が加わり、RCCが一方のALSで真("RCCがこのALSにある"）となると、
他方のALSでは偽("RCCはこのALSにない"）が確定します。
偽となったALSでは"n個のセルにn個の候補数字"となり、 このALSはLockedSetになります。
次の右図は、2つのALS間にRCCが2つあるケースです（doubly linked)。
RCCは一方のALSにのみあります。doublylinkedの場合は2つのRCCが一方のALSに片寄ってあることはなく、
それぞれのALSにひとつづつあります。ただし、どのRCCがどちらのALSにあるかは、決定していません。
また、ALS-RCC-ALSをRCCで結ばれたALSのリンクと呼び、これを連続して繋いでALSの連が作れます。
(3)ALSクラス(UALS)
解析アルゴリズムでALSを扱うために、ALSクラス(UALS)で用意しました。
要素は、ALS構成セルのコレクション(UCellLst)、セル数（Size）、house番号(tfx,0-27）、要素数字(FreeB)、
ALSレベル（Level、FreeB数-セル数）、ALSの行列ブロックのビット表現（rcbDir)です。
また、行・列・ブロックのビット表現はプロパティで定義しています。
このほかにALSのチェインを求めるときに用いる作業変数をいくつか持っています。
コンストラクターでは、ALSの要素を定義し、行列ブロックのビット表現とALS構成セルのビット表現を生成します。
関数類はCompareToと表示用の関数を用意しています。
public class UALS: IComparable{
static public GNPZ_Analyzer pSA;
static public List<UCell> pBDL;
public int ID;
public readonly int Size; //セル数
public readonly int tfx; //house番号
public readonly int FreeB; //ALSの要素数字
public readonly int Level; //FreeB数-セル数
public readonly List<UCell> UCellLst = new List<UCell>(); //ALS構成セル
public bool singler; //ALSManで設定（ALSの構成が唯一）
public int rcbDir; //ALSの行列ブロックのビット表現
public int rcbRow{ get{ return (rcbDir&0x1FF); } } //行のビット表現
public int rcbCol{ get{ return ((rcbDir>>9)&0x1FF); } } //列のビット表現
public int rcbBlk{ get{ return ((rcbDir>>18)&0x1FF); } }//ブロックのビット表現
public Bit81 B81; //ALSセル位置のビット表現
//作業変数//(ALS Chainで用いる)
public bool LimitF=false;
public List<LinkAlsAls> ConnLst;
public int RCC;
public List<int> LockedNoDir;
public UALS( int ID, int Size, int tfx, int FreeB, List<UCell> UCellLst ){
this.ID = ID;
this.Size = Size;
this.tfx = tfx;
this.FreeB = FreeB;
this.Level = FreeB.BitCount()-Size;
this.B81 = new Bit81();
this.rcbFilter = new Bit81();
this.UCellLst = UCellLst;
this.LockedNoDir = null;
UCellLst.ForEach( P =>{
rcbDir |= ( (1<<(P.b+18)) | (1<<(P.c+9)) | (1<<(P.r)) );
rcbFilter |= pSA.ConnectedCells[P.rc];
B81.BPSet(P.rc);
} );
}
public override int GetHashCode(){ return (B81.GetHashCode()| FreeB.GetHashCode()); }
public int CompareTo( object obj ){
UALS UB = obj as UALS;
if( this.Level!=UB.Level ) return (this.Level-UB.Level);
if( this.Size!=UB.Size ) return (this.Size-UB.Size);
if( this.tfx!=UB.tfx ) return (this.tfx-UB.tfx);
return (this.ID-UB.ID);
}
public List<UCell> GetRestCells( int selB ){
return pBDL.IEGet(tfx,selB).Where(P=>!B81.IsHit(P.rc)).ToList();
}
public override string ToString(){
string po = "◇ UALS "+ID+" ◇ tfx:"+tfx +" Size:"+Size +" Level:"+Level;
po += " NoB:" + FreeB.ToBitString(9) + "\r";
po += " B81 "+B81+"\r";
for( int k=0; k<UCellLst.Count; k++){
po += "------";
int rcW = UCellLst[k].rc;
po += " rc:" + ((rcW/9+1)*10+(rcW%9+1)).ToString();
po += " FreeB:" + UCellLst[k].FreeB.ToBitString(9);
po += " rcb:B" + (rcbBlk).ToBitString(9);
po += " c" + rcbCol.ToBitString(9);
po += " r" + rcbRow.ToBitString(9);
po += " rcbFilter:" + rcbFilter.ToString();
po += "\r";
}
return po;
}
public string ToStringRCN(){
string st="";
UCellLst.ForEach( p =>{ st += " r"+(p.r+1) + "c"+((p.c)+1); } );
st = st.ToString_SameHouseComp()+" {#"+FreeB.ToBitStringN(9)+"}";
return st;
}
}(4)ALS管理クラス(ALSMan)
解析アルゴリズムでは、ALSクラスを素のまま用いるのではなく、ALSの管理とALSを操作する機能をまとめたクラス(ALSMan)を用います。 ALSManの要素は、2つの外部参照とALSのコレクションのみです。 関数ALS_Search[13-42]は、現状態を走査してALSのコレクションを求めます。引数のnPlsにより、プラス1からプラスnPlsまでのALSを求めます。 0〜26のhouse番号を設定し、そのhouse内の未確定セルのリストを求めます。 次にサイズを設定[]して、組合せでセル群を選択し、ALSのサイズ条件（セル数と数字）を調べます。 なお、異なるhouseで生成したALSが同じ構成となる場合があります。その場合もALSLstに登録します。 2つ目以降のALSでは、singler=false としています。 最後にサイズ、house順にソートします。
public class ALSMan{
private GNPZ_Analyzer pSA;
private List<UCell> pBDL;
public List<UALS> ALSLst;
public ALSMan( GNPZ_Analyzer pSA ){
this.pSA = pSA;
UALS.pSA = pSA;
}
public int ALS_Search( int nPls ){
if( ALSLst!=null ) return ALSLst.Count();
this.pBDL = pSA.pBDL;
UALS.pBDL = pSA.pBDL;
int ALSSizeMax = GNumPzl.ALSSizeMax;
int mx=0; //仮のID、後に再設定
ALSLst = new List<UALS>();
for( int nn=1; nn<=nPls; nn++ ){
for( int tf=0; tf<27; tf++ ){
List<UCell> P=pBDL.IEGet(tf,0x1FF).ToList();
if( P.Count<1 ) continue;
int szMax = Math.Min(P.Count,8-nn);
szMax = Math.Min(szMax,ALSSizeMax); //【変更】ALSサイズ最大値を制限
for( int sz=1; sz<=szMax; sz++ ){
Combination cmb = new Combination(P.Count,sz);
while( cmb.Successor() ){
int FreeB=0;
Array.ForEach(cmb.Cmb, q=> FreeB|=P[q].FreeB );
if( FreeB.BitCount()!=(sz+nn) ) continue;
List<UCell> Q=new List<UCell>();
Array.ForEach(cmb.Cmb, q=> Q.Add(P[q]) );
//Check for the existence of ALS with the same configuration(T:First F:second or later)
UALS UA=new UALS(mx,sz,tf,FreeB,Q);
int hs= UA.GetHashCode();
if( singlyMan.Count>0 && singlyMan.Contains(hs) ) UA.singler=false;
singlyMan.Add(hs);
mx++;
ALSLst.Add(UA);
}
}
}
ALSLst.Sort();
int ID=0;
ALSLst.ForEach(P=> P.ID=ID++ );
//ALSLst.ForEach(P=>Console.WriteLine(P));
return ALSLst.Count();
}
public int GetALSRCC( UALS UA, UALS UB ){
if( (UA.FreeB&UB.FreeB)==0 ) return 0; //共通数字なし
if( !(UA.B81&UB.B81).IsZero() ) return 0; //範囲が重なる
if( (UA.rcbFilter&UB.B81).IsZero() ) return 0; //House接触なし
int RCC=0, Dir=UA.rcbDir&UB.rcbDir;
//rcbDir |= ( (1<<(P.b+18)) | (1<<(P.c+9)) | (1<<(P.r)) );
foreach( int tfx in Dir.IEGet_BtoNo(27) ){
Bit81 ComH = pSA.HouseCells[tfx];
int FrAi=0, FrAo=0, FrBi=0, FrBo=0;
UA.UCellLst.ForEach(P=>{
if( ComH.IsHit(P.rc) ) FrAi |= P.FreeB;
else FrAo |= P.FreeB;
} );
UB.UCellLst.ForEach(P=>{
if( ComH.IsHit(P.rc) ) FrBi |= P.FreeB;
else FrBo |= P.FreeB;
} );
RCC |= (FrAi.DifSet(FrAo)) & (FrBi.DifSet(FrBo)); //RCC
}
return RCC;
}
public void Create_ALS2ALS_Link( bool doubly ){
var cmb = new Combination( ALSLst.Count, 2 );
while (cmb.Successor()) {
UALS UA = ALSLst[cmb.Cmb[0]];
UALS UB = ALSLst[cmb.Cmb[1]];
int RCC = GetALSRCC( UA, UB );
if( RCC==0 ) continue;
if( !doubly && RCC.BitCount()!=1 ) continue;
if( UA.ConnLst==null ) UA.ConnLst=new List<LinkAlsAls>();
if( UB.ConnLst==null ) UB.ConnLst=new List<LinkAlsAls>();
foreach( var no in RCC.IEGet_BtoNo() ){ //RCCの数だけ登録
LinkAlsAls LKX=new LinkAlsAls(UA,UB,RCC,no);
if( !UA.ConnLst.Contains(LKX) ) UA.ConnLst.Add(LKX);
LKX=new LinkAlsAls(UB,UA,RCC,no);
if( !UB.ConnLst.Contains(LKX) ) UB.ConnLst.Add(LKX);
}
}
}
}