मिनी बेदलाम क्यूब लगाना

मैंने पेंटामिनो पहेली को हल करने वाले कार्यक्रम को अपने पहले कार्यक्रमों में से एक के रूप में लिखा था। यह बहुत समय पहले था, कार्यक्रम ने किसी तरह काम किया, मैंने सभी विकल्पों को खोजने का प्रबंधन नहीं किया ... सामान्य तौर पर, मैंने लिखा और भूल गया।

दूसरे दिन, चीजों को मेज पर रखने के बाद, मैंने फैसला किया कि मिनी बेदलाम क्यूब पहेली को हटाने का समय आ गया है:



और इससे पहले, इसे इकट्ठा करना अच्छा होगा। पहेली में 13 आंकड़े शामिल हैं - 12 5 क्यूब्स से बना है, चार में से एक; छह आंकड़े सममित हैं, उनमें से तीन समतल हैं। आकृतियों को 4x4x4 बॉक्स में रखा जाना चाहिए। मुझे कहना होगा कि समय-समय पर मैंने इन क्यूब्स को याद किया, उनके साथ सामना करने की कोशिश की, लेकिन कुछ भी नहीं आया। इसलिए, विचार आया - एक प्रोग्राम लिखने के लिए जो पहेली को हल करता है, और जितना संभव हो उतना कम प्रयास खर्च करें, और फिर पुराने प्रश्न को हल करें: क्या अधिक लाभदायक है - आंकड़े या कोशिकाओं को छांटना और किस क्रम में।

डेटा प्रस्तुति और सरल खोज

चूंकि बॉक्स में कोशिकाओं की संख्या पूर्णांक के अभ्यावेदन में बिट्स की संख्या से अधिक नहीं थी, इसलिए इस प्रतिनिधित्व को मुख्य के रूप में चुना गया था: क्षेत्र की वर्तमान स्थिति और प्रत्येक आकृति की प्रत्येक स्थिति एक अहस्ताक्षरित के रूप में संग्रहीत है: सी # - ulong)। प्रत्येक आकृति की अभिविन्यास की संख्या 24 से अधिक नहीं है, इस अभिविन्यास के लिए पदों की संख्या 27 से अधिक नहीं है। कुल मिलाकर, संभवतः प्रत्येक आंकड़े के 648 से अधिक पदों पर - हम आसानी से उन्हें मेमोरी में स्टोर करने का जोखिम उठा सकते हैं। यह केवल इन प्रावधानों को प्राप्त करने के लिए आवश्यक है।

कुल्हाड़ियों के क्रम और उनकी दिशा को इंगित करते हुए, स्पष्ट रूप से 24 घन अभिविन्यास निर्धारित किए जा सकते हैं, लेकिन यह एक लंबा समय है। ऐसा करना आसान है: घन रोटेशन समूह में दो जनरेटर का चयन करें (एक, दुर्भाग्य से, नहीं मिल सकता है), और परिणाम स्थिर होने तक उन्हें एक राज्य में लागू करें। मैंने ट्रांसफ़ॉर्म (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]; } 

टर्न () फ़ंक्शन दो में से एक मोड़ करता है। लगातार 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]); } } 

यहां मैं ध्यान रखता हूं कि क्रॉस केवल दो अनिवार्य रूप से विभिन्न पदों पर कब्जा कर सकता है। यह सुनिश्चित करता है कि बाद में पाए गए सभी समाधान अलग-अलग हैं।

हम गहराई से समाधान की तलाश करेंगे। प्रत्येक चरण में, हम या तो कुछ सेल का चयन कर सकते हैं और सभी मुफ्त आकारों के माध्यम से सॉर्ट कर सकते हैं जो इसे बंद करने के लिए इस्तेमाल किया जा सकता है, या इसके विपरीत - कुछ आकार का चयन करें और इसे सभी संभावित तरीकों से फ़ील्ड पर रखें। इसके अलावा, हम जांच कर सकते हैं कि क्या कोई सेल है जिसे अब बंद नहीं किया जा सकता है या एक आंकड़ा जो किसी भी तरह से नहीं डाला जा सकता है - दोनों मामलों में शाखा के विश्लेषण को रोका जा सकता है। एल्गोरिथ्म की जटिलता इस बात पर निर्भर करती है कि हम किस रणनीति को चुनते हैं और क्या हम असंभवता के लिए स्थितियों की जांच करेंगे।

सबसे सरल संस्करण में - एक निश्चित क्रम में आंकड़ों पर पुनरावृत्ति - समाधान की खोज 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 सरणी में संग्रहीत की जाती हैं, और प्रिंट () फ़ंक्शन आसानी से पाए गए समाधान को प्रिंट कर सकता है।

परिणाम और अनुकूलन

कुल - 110 लाइनों में कार्यक्रम निकला।

कार्यक्रम को कुछ सेकंड में पहला समाधान मिला, लेकिन फिर यह खत्म हो गया। "19186 सॉल्यूशंस" बॉक्स पर लिखा गया है, और निश्चित रूप से, मैं उन सभी को ढूंढना चाहता था (और एक ही समय में जांचें कि क्या लेखक सही ढंग से गिने जाते हैं)। मुद्रण सांख्यिकी ने निम्नलिखित दिखाया:

पहले 500 मिलियन सॉल्व कॉल ने 295 सेकंड पूरे किए, और केवल 44 समाधान पाए गए। यह 1.7 मिलियन कॉल प्रति सेकंड और 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; } 

सॉल्व में शामिल किए जाने के बाद, परिणाम बेहतर परिमाण का क्रम था: 1.9 मिलियन कॉल प्रति सेकंड और लगभग 1.8 समाधान प्रति सेकंड! आप 3 बजे मिल सकते हैं आप 2 और 3 कोशिकाओं के अलग-अलग क्षेत्रों की खोज करने का भी प्रयास कर सकते हैं, लेकिन आकृति विज्ञान यहां से सामना करना मुश्किल है, आपको पूर्ण त्रि-आयामी भरने की आवश्यकता है।

अगला प्रयास एक ऐसे सेल की खोज करना है, जो कम से कम संभव संख्या में तरीकों के साथ बंद हो, और इन विधियों को एन्यूमरेट करे। सॉल्व फंक्शन लगभग 20 गुना धीमी गति से काम करने लगा, लेकिन समाधान खोजने की समग्र गति बनी रही

पूर्व - प्रति सेकंड 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 गुना अधिक तेजी से निकला - यह प्रति सेकंड 95 समाधान पाता है, और पूरी पहेली की एक पूरी गणना 203 सेकंड में होती है। कारण अभी तक समझ में नहीं आया है। हल करने के लिए कॉल की संख्या में वृद्धि में खोज क्रम परिणामों को बदलने का कोई भी प्रयास। लेकिन तब समय को आधे से कम किया जा सकता है, यदि आप एक मुफ्त सेल की तलाश करते हैं, जो पिछली बार पाया जाता है:

 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 से अधिक उठाए गए बिट्स नहीं। यह निर्धारित करना आवश्यक है कि इन नंबरों की सबसे बड़ी संख्या में कौन सा बिट उठाया गया है। यह सबसे प्रभावी ढंग से कैसे करें?

दूसरा प्रश्न एक दार्शनिक है। कोशिकाओं को पंक्तियों में भरना और फिर परतों में सबसे प्रभावी क्यों है? मैंने कोने को भरने की कोशिश की, फिर पसलियों ... परिणाम लेक्सोग्राफिकल ऑर्डर के मामले में परिमाण की तुलना में खराब होने के कई आदेश थे। यहाँ क्या बात हो सकती है?