先日、テーブルの上に物を整理して、私はそれがアイドルの周りに横たわっているミニベッドラムキューブパズルを削除する時だと決めました：
そしてその前に、それを集めておくといいでしょう。 パズルは13個のフィギュアで構成され、12個は4個のうちの1個の5個のキューブで構成されています。 6つの図は対称で、そのうちの3つは平らです。 シェイプは4x4x4ボックスに配置する必要があります。 私は時々、これらのキューブを思い出し、それらに対処しようとしましたが、それから何も得られなかったと言わなければなりません。 したがって、アイデアを思い付きました-パズルを解決するプログラムを作成し、可能な限り少ない労力を費やしてから、古い質問を解決します：何がより収益性が高い-数字やセルを整理し、どのような順序で。
データ表示と簡単な検索
ボックス内のセルの数は整数表現のいずれかのビット数以下であることが判明したため、この表現が主なものとして選択されました：フィールドの現在の状態と各図の各位置の両方が符号なし__int64ビットマスクとして保存されます（ C＃-ulong）。 各図の向きの数は24以下であり、この向きの位置の数は27以下です。合計、おそらく各図の648以下の位置-それらをメモリに保存する余裕があります。 何らかの形でこれらの規定を取得するだけで十分です。
軸の順序と方向を示す24個の立方体の向きを明示的に設定できますが、これには時間がかかります。 これは簡単です。キューブ回転グループで2つのジェネレーターを選択し（残念ながら1つが見つかりません）、結果が安定するまで1つの状態に適用します。 変換（x、y、z）->（y、z、x）および（x、y、z）->（-x、z、y）を選択しました。
結果は次のコードです。
typedef unsigned __int64 ulong; const ulong XLOW=0x1111111111111111LL; const ulong YLOW=0xF000F000F000FLL; const ulong ZLOW=0xFFFFLL; const ulong XHIGH=0x8888888888888888LL; const ulong YHIGH=0xF000F000F000F000LL; const ulong ZHIGH=0xFFFF000000000000LL; struct Fig{ int NF; ulong *Arr; Fig(){ Arr=0;} void Init(ulong fig0); void Init(int nf,ulong *arr); ~Fig(){ delete Arr; } }; ulong Turn(ulong v,int rt){ ulong res=0; for(int a=0;a<64;a++){ int b=rt==0 ? (a>>2)|((a&3)<<4) : (~a&3)|((a>>2)&12)|((a<<2)&48); if((v>>a)&1) res|=1LL<<b; } if(rt) while((res&XLOW)==0) res>>=1; return res; } ulong arr0[648]; void Fig::Init(ulong fig0){ int p=0,q=1; arr0[0]=fig0; while(p<q){ ulong a=arr0[p++]; for(int u=0;u<2;u++){ ulong b=Turn(a,u); int i; for(i=0;i<q;i++) if(arr0[i]==b) break; if(i==q) arr0[q++]=b; } } for(p=0;p<q;p++) if((arr0[p]&XHIGH)==0) arr0[q++]=arr0[p]<<1; for(p=0;p<q;p++) if((arr0[p]&YHIGH)==0) arr0[q++]=arr0[p]<<4; for(p=0;p<q;p++) if((arr0[p]&ZHIGH)==0) arr0[q++]=arr0[p]<<16; Init(q,arr0); } void Fig::Init(int q,ulong *arr){ NF=q; Arr=new ulong[q]; for(int p=0;p<q;p++) Arr[p]=arr[p]; }
Turn（）関数は、2つのターンのうちの1つを実行します。 定数XHIGH、XLOWなど。 立方体の面に対応し、フィギュアをある方向に動かすことができるか、別の方向に動かすことができるかを決定できます。 形状のセット全体を初期化することは非常に簡単になりました。
ulong Cross[2]={0x4E40000000000000LL,0x4E4000000000LL}; const int NFig=13; ulong Figs0[NFig]={0x4E4,0x136,0x263,0x10027,0x20027,0x20063,0x10063,0x30062,0x10047, 0x100017,0x10017,0x20072,0x10031}; Fig Figs[NFig]; int FState[NFig]; void InitFigs(){ Figs[0].Init(2,Cross); for(int i=1;i<NFig;i++){ Figs[i].Init(Figs0[i]); } }
ここで、十字架が占めることができるのは本質的に異なる2つのポジションのみであると考えています。 これにより、後で見つかるすべてのソリューションが異なることが保証されます。
解決策を詳細に探します。 各ステップで、セルを選択し、それを閉じるために使用できるすべての自由な形状を並べ替えるか、またはその逆-何らかの形状を選択し、あらゆる方法でフィールドに配置します。 さらに、閉じられなくなったセルや、どうしても配置できないセルがあるかどうかを確認できます。どちらの場合も、分岐の分析を停止できます。 アルゴリズムの複雑さは、どの戦略を選択するか、不可能な状況をチェックするかどうかによって異なります。
最も単純なバージョン-固定された順序で数値を反復処理する-ソリューションの検索は20行で記述されます。
void Solve(int n,ulong x){ if(n==NFig){ NSolve++; Print(); return; } Fig &F=Figs[n]; for(int i=0;i<F.NF;i++){ ulong s=F.Arr[i]; if((s&x)==0){ FState[n]=i; Solve(n+1,x|s); FState[n]=-1; } } NBack++; }
図形の位置はFState配列に保存され、Print（）関数は見つかった解を簡単に印刷できます。
結果と最適化
合計-110行のプログラムが判明しました。
プログラムは数秒で最初の解決策を見つけましたが、それを考え直しました。 「19186 Solutions」が箱に書かれています。もちろん、私はそれらをすべて見つけたいと思っていました（そして同時に著者が正しく数えているかどうかを確認しました）。 印刷統計は次を示しました。
最初の5億件のSolveコールは295秒で完了し、44のソリューションのみが見つかりました。 これにより、1秒あたり170万回の呼び出し、およびソリューションあたり6.7秒の呼び出しが可能になります。 すべてのソリューションの検索にかかる推定時間-36時間。
多すぎる。
頭に浮かぶ最初の最適化は、フィールドに孤立した空のセルがあるかどうかをチェックすることです。もしそうなら、この位置をこれ以上考慮しないでください。 チェックは非常に簡単であることが判明しました。
bool HaveIsolPoint(ulong x){ ulong y=((x>>1)|XHIGH)&((x<<1)|XLOW)& ((x>>4)|YHIGH)&((x<<4)|YLOW)& ((x>>16)|ZHIGH)&((x<<16)|ZLOW); return (~x&y)!=0; }
Solveに含めた後、結果は桁違いに改善されました。1秒あたり190万回の呼び出しと1秒あたり約1.8のソリューションです。 3時に会えます 2セルと3セルの孤立した領域を検索することもできますが、ここでは形態を処理するのが難しく、完全な3次元の塗りつぶしが必要です。
次の試みは、可能な限り少ない数のメソッドで閉じるセルを検索し、これらのメソッドを列挙することです。 解決機能は約20倍遅くなり始めましたが、解決策を見つける全体的な速度は維持されました
前者-1秒あたり1.8ソリューション。
最適な空のセルを検索する時間を無駄にしないために、それらを順番に整理することにしました。 明らかに、セル0..N-1がすでに塗りつぶされており、セルNが空の場合、このセルはセルNが属する図形の位置でのみ塗りつぶすことができ、同時に図のすべてのセルの数は最小になります。 したがって、最小セル数で数値をソートすると、検索を大幅に削減できます。
コードは次のとおりです（変更された機能のみが表示されます）。
struct Fig{ int NF; ulong *Arr; int Ind[65]; Fig(){ Arr=0;} void Init(ulong fig0); void Init(int nf,ulong *arr); ~Fig(){ delete Arr; } }; extern "C" int i64cmp(const void *a,const void *b){ ulong A=*(const ulong*)a,B=*(const ulong*)b; return A<B ? -1 : A==B ? 0 : 1; } void Fig::Init(int q,ulong *arr){ NF=q; Arr=new ulong[q]; for(int p=0;p<q;p++) Arr[p]=CVT(arr[p]); qsort(Arr,q,sizeof(ulong),i64cmp); int j=0; for(int p=0;p<q;p++){ while(Arr[p]&(-1LL<<j)) Ind[j++]=p; } while(j<=64) Ind[j++]=q; } void Solve(ulong x){ int mb=63; while(mb>=0){ if((x&1)==0) break; x>>=1; mb--; } if(mb<0){ NSolve++; Print(); return; } for(int f=0;f<NFig;f++) if(FState[f]<0){ Fig &F=Figs[f]; int r1=F.Ind[mb],r2=F.Ind[mb+1]; for(int u=r1;u<r2;u++){ ulong s=F.Arr[u]; if((x&s)==0){ FState[f]=u; Solve(x|s,mb,z); } } FState[f]=-1; } NBack++; }
驚いたことに、このオプションは以前のものよりも50倍以上高速であることが判明しました。1秒あたり95のソリューションが見つかり、パズル全体の完全な列挙が203秒で行われます。 その理由はまだ理解されていません。 検索順序を変更しようとすると、Solve（）の呼び出し回数が増加します。 ただし、最後に見つかったセルから開始して空きセルを探すと、時間を半分に短縮できます。
void Solve(ulong x,int mb,ulong z){ while(z!=0){ if((x&z)==0) break; z>>=1; mb--; } if(mb<0){ NSolve++; Print(); return; } for(int f=0;f<NFig;f++) if(FState[f]<0){ Fig &F=Figs[f]; int r1=F.Ind[mb],r2=F.Ind[mb+1]; ulong *aa=F.Arr+r1; for(int u=r1;u<r2;u++){ ulong s=*aa++; if((x&s)==0){ FState[f]=u; Solve(x|s,mb,z); } } FState[f]=-1; } NBack++; }
合計稼働時間は102秒で、最初に検討したオプションの約1250倍です。 同時に、プログラムはあまり拡張しませんでした：すべての行が約130行あります。
未解決の質問
最初の質問は技術的です。 10〜10,000個の64ビット数のストリームがあります。 各数値では、5ビットを超えないでください。 これらの数の最大数で発生するビットを決定する必要があります。 これを最も効果的に行う方法は？
2番目の質問は、むしろ哲学的な質問です。 セルを行で塗りつぶしてからレイヤーで塗りつぶすのが最も効果的なのはなぜですか？ 頂点、次にrib骨を埋めようとしました...結果は、辞書式順序の場合よりも数桁悪化しました。 ここで何が問題になりますか？