Bit 表現
GNPX ver5.0- では、解析アルゴリズム/コードに Bit 表現 を多く使用します。
Bit 表現は 論理を直観的・簡単に表現できます。バグの発生も抑制されています（多分）。
ここに示すのは、GNPXで用いている ビット演算関数 のほんの一部です。
(1) 基本ビット演算
数独の盤面を表すには 81 bit 必要であり、”UInt128” を使います。 処理を明確に示すために、次の関数 を使用します(最なもののみを例示) 。使用方法は、GNPXにあります。
static public partial class GNPZExtender{
static private readonly UInt128 _filter0081 = (UInt128.One<<81)-1;
static private readonly UInt128 qZero = UInt128.Zero;
static private readonly UInt128 qOne = UInt128.One;
static private readonly UInt128 _b9 = 0x1FF;
// [att] UInt128: instance variable! Original variable remains unchanged.
static public UInt128 DifSet( this UInt128 A, UInt128 B ) => (UInt128)(A&(B^UInt128.MaxValue));
static public UInt128 Set( this UInt128 A, int rc ) => A | qOne
static public UInt128 Set( this UInt128 A, UInt128 B ) => A | B;
static public UInt128 Reset( this UInt128 A, int rc ) => A & ((qOne<<rc)^UInt128.MaxValue);
static public UInt128 Reset( this UInt128 A, UInt128 B ) => A & B^UInt128.MaxValue;
static public bool IsHit( this UInt128 A, int rc ) => (A & (qOne<<rc)) != qZero;
static public bool IsHit( this UInt128 A, UInt128 B ) => (A & B) != qZero;
static public bool IsZero( this UInt128 A ) => (A == qZero);
static public bool IsNotZero( this UInt128 A ) => (A != qZero);
}
(2) ビット表現の定数
解析アルゴリズムで用いる最も基本的な定数の例として、ConnectedCells81 と HouseCells81 を示します。
- ConnectedCells81[]
ConnectedCells81は、盤面81セルに連結するセルをビット表現した配列定数です。 数独問題のビット表現との and 演算で連結するセルが求まります。ConnectedCells81 ("."=0 9,27ビットごとに区切っている).11111111 111...... 111...... /1........ 1........ 1........ /1........ 1........ 1........ 1.1111111 111...... 111...... /.1....... .1....... .1....... /.1....... .1....... .1....... 11.111111 111...... 111...... /..1...... ..1...... ..1...... /..1...... ..1...... ..1...... 111.11111 ...111... ...111... /...1..... ...1..... ...1..... /...1..... ...1..... ...1..... 1111.1111 ...111... ...111... /....1.... ....1.... ....1.... /....1.... ....1.... ....1.... 11111.111 ...111... ...111... /.....1... .....1... .....1... /.....1... .....1... .....1... 111111.11 ......111 ......111 /......1.. ......1.. ......1.. /......1.. ......1.. ......1.. 1111111.1 ......111 ......111 /.......1. .......1. .......1. /.......1. .......1. .......1. 11111111. ......111 ......111 /........1 ........1 ........1 /........1 ........1 ........1 111...... .11111111 111...... /1........ 1........ 1........ /1........ 1........ 1........ 111...... 1.1111111 111...... /.1....... .1....... .1....... /.1....... .1....... .1....... 111...... 11.111111 111...... /..1...... ..1...... ..1...... /..1...... ..1...... ..1...... ...111... 111.11111 ...111... /...1..... ...1..... ...1..... /...1..... ...1..... ...1..... ...111... 1111.1111 ...111... /....1.... ....1.... ....1.... /....1.... ....1.... ....1.... ...111... 11111.111 ...111... /.....1... .....1... .....1... /.....1... .....1... .....1... ......111 111111.11 ......111 /......1.. ......1.. ......1.. /......1.. ......1.. ......1.. ......111 1111111.1 ......111 /.......1. .......1. .......1. /.......1. .......1. .......1. ......111 11111111. ......111 /........1 ........1 ........1 /........1 ........1 ........1 111...... 111...... .11111111 /1........ 1........ 1........ /1........ 1........ 1........ 111...... 111...... 1.1111111 /.1....... .1....... .1....... /.1....... .1....... .1....... 111...... 111...... 11.111111 /..1...... ..1...... ..1...... /..1...... ..1...... ..1...... ...111... ...111... 111.11111 /...1..... ...1..... ...1..... /...1..... ...1..... ...1..... ...111... ...111... 1111.1111 /....1.... ....1.... ....1.... /....1.... ....1.... ....1.... ...111... ...111... 11111.111 /.....1... .....1... .....1... /.....1... .....1... .....1... ......111 ......111 111111.11 /......1.. ......1.. ......1.. /......1.. ......1.. ......1.. ......111 ......111 1111111.1 /.......1. .......1. .......1. /.......1. .......1. .......1. ......111 ......111 11111111. /........1 ........1 ........1 /........1 ........1 ........1 1........ 1........ 1........ /.11111111 111...... 111...... /1........ 1........ 1........ .1....... .1....... .1....... /1.1111111 111...... 111...... /.1....... .1....... .1....... ..1...... ..1...... ..1...... /11.111111 111...... 111...... /..1...... ..1...... ..1...... ...1..... ...1..... ...1..... /111.11111 ...111... ...111... /...1..... ...1..... ...1..... ....1.... ....1.... ....1.... /1111.1111 ...111... ...111... /....1.... ....1.... ....1.... .....1... .....1... .....1... /11111.111 ...111... ...111... /.....1... .....1... .....1... ......1.. ......1.. ......1.. /111111.11 ......111 ......111 /......1.. ......1.. ......1.. .......1. .......1. .......1. /1111111.1 ......111 ......111 /.......1. .......1. .......1. ........1 ........1 ........1 /11111111. ......111 ......111 /........1 ........1 ........1 1........ 1........ 1........ /111...... .11111111 111...... /1........ 1........ 1........ .1....... .1....... .1....... /111...... 1.1111111 111...... /.1....... .1....... .1....... ..1...... ..1...... ..1...... /111...... 11.111111 111...... /..1...... ..1...... ..1...... ...1..... ...1..... ...1..... /...111... 111.11111 ...111... /...1..... ...1..... ...1..... ....1.... ....1.... ....1.... /...111... 1111.1111 ...111... /....1.... ....1.... ....1.... .....1... .....1... .....1... /...111... 11111.111 ...111... /.....1... .....1... .....1... ......1.. ......1.. ......1.. /......111 111111.11 ......111 /......1.. ......1.. ......1.. .......1. .......1. .......1. /......111 1111111.1 ......111 /.......1. .......1. .......1. ........1 ........1 ........1 /......111 11111111. ......111 /........1 ........1 ........1 1........ 1........ 1........ /111...... 111...... .11111111 /1........ 1........ 1........ .1....... .1....... .1....... /111...... 111...... 1.1111111 /.1....... .1....... .1....... ..1...... ..1...... ..1...... /111...... 111...... 11.111111 /..1...... ..1...... ..1...... ...1..... ...1..... ...1..... /...111... ...111... 111.11111 /...1..... ...1..... ...1..... ....1.... ....1.... ....1.... /...111... ...111... 1111.1111 /....1.... ....1.... ....1.... .....1... .....1... .....1... /...111... ...111... 11111.111 /.....1... .....1... .....1... ......1.. ......1.. ......1.. /......111 ......111 111111.11 /......1.. ......1.. ......1.. .......1. .......1. .......1. /......111 ......111 1111111.1 /.......1. .......1. .......1. ........1 ........1 ........1 /......111 ......111 11111111. /........1 ........1 ........1 1........ 1........ 1........ /1........ 1........ 1........ /.11111111 111...... 111...... .1....... .1....... .1....... /.1....... .1....... .1....... /1.1111111 111...... 111...... ..1...... ..1...... ..1...... /..1...... ..1...... ..1...... /11.111111 111...... 111...... ...1..... ...1..... ...1..... /...1..... ...1..... ...1..... /111.11111 ...111... ...111... ....1.... ....1.... ....1.... /....1.... ....1.... ....1.... /1111.1111 ...111... ...111... .....1... .....1... .....1... /.....1... .....1... .....1... /11111.111 ...111... ...111... ......1.. ......1.. ......1.. /......1.. ......1.. ......1.. /111111.11 ......111 ......111 .......1. .......1. .......1. /.......1. .......1. .......1. /1111111.1 ......111 ......111 ........1 ........1 ........1 /........1 ........1 ........1 /11111111. ......111 ......111 1........ 1........ 1........ /1........ 1........ 1........ /111...... .11111111 111...... .1....... .1....... .1....... /.1....... .1....... .1....... /111...... 1.1111111 111...... ..1...... ..1...... ..1...... /..1...... ..1...... ..1...... /111...... 11.111111 111...... ...1..... ...1..... ...1..... /...1..... ...1..... ...1..... /...111... 111.11111 ...111... ....1.... ....1.... ....1.... /....1.... ....1.... ....1.... /...111... 1111.1111 ...111... .....1... .....1... .....1... /.....1... .....1... .....1... /...111... 11111.111 ...111... ......1.. ......1.. ......1.. /......1.. ......1.. ......1.. /......111 111111.11 ......111 .......1. .......1. .......1. /.......1. .......1. .......1. /......111 1111111.1 ......111 ........1 ........1 ........1 /........1 ........1 ........1 /......111 11111111. ......111 1........ 1........ 1........ /1........ 1........ 1........ /111...... 111...... .11111111 .1....... .1....... .1....... /.1....... .1....... .1....... /111...... 111...... 1.1111111 ..1...... ..1...... ..1...... /..1...... ..1...... ..1...... /111...... 111...... 11.111111 ...1..... ...1..... ...1..... /...1..... ...1..... ...1..... /...111... ...111... 111.11111 ....1.... ....1.... ....1.... /....1.... ....1.... ....1.... /...111... ...111... 1111.1111 .....1... .....1... .....1... /.....1... .....1... .....1... /...111... ...111... 11111.111 ......1.. ......1.. ......1.. /......1.. ......1.. ......1.. /......111 ......111 111111.11 .......1. .......1. .......1. /.......1. .......1. .......1. /......111 ......111 1111111.1 ........1 ........1 ........1 /........1 ........1 ........1 /......111 ......111 11111111. - HouseCells81[]
”houseに属するセル”を表す配列定数です。行house、列house、ブロックhouseの順です。HouseCells81 ("."=0 9,27ビットごとに区切っている)111111111 ......... ......... /......... ......... ......... /......... ......... ......... ......... 111111111 ......... /......... ......... ......... /......... ......... ......... ......... ......... 111111111 /......... ......... ......... /......... ......... ......... ......... ......... ......... /111111111 ......... ......... /......... ......... ......... ......... ......... ......... /......... 111111111 ......... /......... ......... ......... ......... ......... ......... /......... ......... 111111111 /......... ......... ......... ......... ......... ......... /......... ......... ......... /111111111 ......... ......... ......... ......... ......... /......... ......... ......... /......... 111111111 ......... ......... ......... ......... /......... ......... ......... /......... ......... 111111111 1........ 1........ 1........ /1........ 1........ 1........ /1........ 1........ 1........ .1....... .1....... .1....... /.1....... .1....... .1....... /.1....... .1....... .1....... ..1...... ..1...... ..1...... /..1...... ..1...... ..1...... /..1...... ..1...... ..1...... ...1..... ...1..... ...1..... /...1..... ...1..... ...1..... /...1..... ...1..... ...1..... ....1.... ....1.... ....1.... /....1.... ....1.... ....1.... /....1.... ....1.... ....1.... .....1... .....1... .....1... /.....1... .....1... .....1... /.....1... .....1... .....1... ......1.. ......1.. ......1.. /......1.. ......1.. ......1.. /......1.. ......1.. ......1.. .......1. .......1. .......1. /.......1. .......1. .......1. /.......1. .......1. .......1. ........1 ........1 ........1 /........1 ........1 ........1 /........1 ........1 ........1 111...... 111...... 111...... /......... ......... ......... /......... ......... ......... ...111... ...111... ...111... /......... ......... ......... /......... ......... ......... ......111 ......111 ......111 /......... ......... ......... /......... ......... ......... ......... ......... ......... /111...... 111...... 111...... /......... ......... ......... ......... ......... ......... /...111... ...111... ...111... /......... ......... ......... ......... ......... ......... /......111 ......111 ......111 /......... ......... ......... ......... ......... ......... /......... ......... ......... /111...... 111...... 111...... ......... ......... ......... /......... ......... ......... /...111... ...111... ...111... ......... ......... ......... /......... ......... ......... /......111 ......111 ......111
(3) ビット表現の関数
- ビット表現の生成関数
解析アルゴリズムでは、盤面全体の状態やALSなどのセル群の状態を”bit表現の1変数”で表わします。List<UCell> UCellLst; UInt128 bitExp = UCellLst.Aggregate(UInt128.Zero, (p,q) => p | qOne<<q.rc ); UInt128 Connected = UCellLst.Aggregate(UInt128.Zero, (p,q) => p | pConnectedCells81[q.rc] ); - ビット表現の列挙関数
ビット表現の変数から、値"1"の位置＝元の値を列挙します。 "IEGet_BtoNo()"は、9ビット変数の列挙関数、 "IEGet_BtoHouse27()"は、27ビット変数の列挙関数、 "IEGet_rc()"は、128(81)ビット変数の列挙関数 です。static public IEnumerable<int>> IEGet_BtoNo( this int B, int sz=9 ){ for(int no=0; no<sz; no++ ){ if((B & (1<<no) )>0) yield return no; } yield break; } static public IEnumerableIEGet_BtoHouse27( this int P ){ for(int m=0; m<27; m++ ){ if( (P & (1<m)) > 0 ) yield return m; } yield break; } static public IEnumerable IEGet_rc( this UInt128 A, int mx=81){ for(int rc=0; rc<mx; rc++){ if( (A & (UInt128.One<<rc)) > 0 ) yield return rc; } yield break; }
(4) rcbFrame
数独セルの行・列・ブロックを表す関数と、集計関数(Aggregate関数)です。
複数のセルを扱うアルゴリズム(例えば ALS）で、セル群の共通部分や被覆状態を調べるときに用います。
static public class ULogical_Node_Utility (only some){
static public int func_rcbFrame_Value( this int rc) => (1<<(rc.ToBlock()+18)) | (1<<(rc%9+9)) | (1<<rc/9);
static public int rcbFrame_Value( this int rc) => _rcbFrame_Value[rc];
static public int Ceate_rcbFrameAnd( this UInt128 b081 ) => b081.IEGet_rc().Aggregate( 0x7FFFFFF, (p,q) => p & rcbFrame_Value(q) );
static public int Ceate_rcbFrameOr( this UInt128 b081 ) => b081.IEGet_rc().Aggregate( 0, (p,q) => p | rcbFrame_Value(q) );
static public UInt128 AggregateCommonAxis( this UInt128 B) => B.IEGet_rc().Aggregate( (UInt128.One<<81)-1, (b,rc)=>b & pConnectedCells81[rc] );
}
Top