📰 🛤️ 🤰🏾 Pentamino उदाहरण का उपयोग करके सैट सॉल्वर का उपयोग करके टाइलिंग समस्या का समाधान करना 🕧 🤸🏿 💃🏼

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

शुरुआत में मैं आपको याद दिलाना चाहता हूं कि खेल पेंटामिनो है। यह एक वर्ग 8x8 फ़ील्ड है, जिसे 13 आंकड़ों के साथ टाइल किया जाना चाहिए - 12 स्क्विगल्स, जिसमें 5 वर्ग और एक 2x2 का आंकड़ा शामिल है:

यहाँ यह कहने योग्य है कि बूलियन संतोषजनक समस्या या SAT समस्या क्या है। सामान्य शब्दों में, इसे बूलियन चर के ऐसे मूल्यों की खोज के रूप में तैयार किया जा सकता है जिसमें दी गई अभिव्यक्ति सत्य हो जाती है। सामान्यतया, यह एक एनपी पूर्ण कार्य है, हालांकि, कई चालें हैं जो इसे प्रभावी ढंग से हल करने में मदद करती हैं। ऐसा करने के लिए, एसएटी सॉल्वर नामक कई विशेष एप्लिकेशन विकसित किए गए हैं। मैं मिनीसैट नाम के एक सैट सॉल्वर का इस्तेमाल करूंगा। इस समस्या को हल करने के लिए, संयुग्मित सामान्य रूप में इनपुट अभिव्यक्ति को फिर से लिखना आवश्यक है, अर्थात, चर के तार्किक योगों के उत्पाद के रूप में। यहां सामान्य रूप में प्रत्येक ब्रैकेट को एक खंड कहा जाता है, जो कुछ शाब्दिक अर्थों का तार्किक "या" है, अर्थात् बूलियन चर या उनके खंडन। उदाहरण के लिए:

(एक्स 1 वी नहीं एक्स 3) (एक्स 2 वी एक्स 4) (एक्स 2 वी एक्स 3 वी एक्स 4 नहीं)

मुझे SAT कार्य में टाइलिंग कार्य का अनुवाद करने की आवश्यकता थी। कुछ पेंटामिनो आंकड़ा लें और इसे सभी संभावित तरीकों से खेल के मैदान में डालें, जिसमें बदलाव, बदलाव और प्रतिबिंब शामिल हैं। आकृति की ऐसी प्रत्येक स्थिति के लिए हम एक बूलियन चर को जोड़ते हैं और हम मान लेंगे कि यदि हमारे अंतिम समाधान में यह आंकड़ा इस विशेष स्थिति में मौजूद है, तो चर सच होगा, और यदि नहीं, तो गलत है। हम सभी आंकड़ों के लिए ऐसा करते हैं।

अब हमारी समस्या का वर्णन करने वाले एक सूत्र को तैयार करते हैं, अर्थात हम वास्तव में अपने चर पर प्रतिबंध लगाएंगे। पहली बात यह सुनिश्चित करना है कि हमारे खेल मैदान की सभी कोशिकाएं कम से कम एक आकृति के साथ कवर की जाएंगी। ऐसा करने के लिए, 64 के प्रत्येक सेल के लिए, हम इन आंकड़ों के सभी आंकड़ों और पदों को खोजते हैं जो इस सेल को कवर करते हैं और उन वेरिएबल्स से एक क्लॉज बनाते हैं, जो इन आंकड़ों के पदों को सौंपा गया है। दूसरी बात यह है कि आकृतियों के प्रतिच्छेदन को समाप्त करना है। यह एक डबल चक्र में किया जा सकता है, बस सभी आंकड़ों के सभी संभावित पदों को छांटना और यह निर्धारित करना कि क्या जोड़ी में सामान्य कोशिकाएं हैं। यदि वहाँ है, तो वे प्रतिच्छेद करते हैं और आपको फॉर्म का एक खंड जोड़ना होगा (x_i V नहीं x_j), जहाँ x_i पहले स्थान पर दिया गया चर है, और x_j दूसरा स्थान है। यह खंड सत्य है जब x_i और x_j एक ही समय में एक के बराबर नहीं होते हैं, अर्थात, चौराहों को बाहर करता है। और अंत में, विचार करने वाली तीसरी बात यह है कि प्रत्येक आकृति केवल एक बार खेल मैदान पर मौजूद हो सकती है। ऐसा करने के लिए, हम एक डबल चक्र में प्रत्येक आकृति के सभी पदों से गुजरते हैं और उसी आकृति के पदों की प्रत्येक जोड़ी के लिए हम पिछले एक के समान एक खंड बनाते हैं और दो नकारात्मक से मिलकर बनाते हैं। यही है, जब दो समान आंकड़े दिखाई देते हैं (लेकिन अलग-अलग स्थिति में), इनमें से एक खंड गलत देगा और तदनुसार, इस तरह के समाधान को बाहर कर देगा।

यह सब एक सिद्धांत था, और अब अभ्यास करने के लिए आगे बढ़ते हैं। प्रत्येक आकृति में 1 से d तक की संख्या है जो इसे दूसरों से अलग करती है और आसानी से प्रिंट करती है। फिर खेल मैदान का एक मैट्रिक्स बनाएं और खेल मैदान की संबंधित कोशिकाओं को एनकोड करें जैसा कि चित्र द्वारा कब्जा किया गया है / कब्जा नहीं किया गया है:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. 1 1 . . . . .
1 1 . . . . . .
. 1 . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
2 . . . . . . .
2 . . . . . . .
2 . . . . . . .
2 . . . . . . .
2 . . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
3 . . . . . . .
3 . . . . . . .
3 . . . . . . .
3 3 . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
4 . . . . . . .
4 . . . . . . .
4 4 . . . . . .
. 4 . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
5 5 . . . . . .
5 5 . . . . . .
5 . . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
6 6 6 . . . . .
. 6 . . . . . .
. 6 . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
7 . 7 . . . . .
7 7 7 . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
8 . . . . . . .
8 . . . . . . .
8 8 8 . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . 9 . . . . .
. 9 9 . . . . .
9 9 . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. a . . . . . .
aaa . . . . .
. a . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
b . . . . . . .
bb . . . . . .
b . . . . . . .
b . . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. cc . . . . .
. c . . . . . .
cc . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
dd . . . . . .
dd . . . . . .

अब, प्रत्येक टुकड़े के लिए, खेल के मैदान पर बदलाव, मोड़ और प्रतिबिंब के माध्यम से सभी संभावित पदों को खोजना आवश्यक है। आइए मुड़ें और प्रतिबिंब के साथ शुरू करें। कुल मिलाकर, घुमाव और प्रतिबिंब के 8 संभावित रूपांतरण हैं, जिसमें एक तुच्छ परिवर्तन शामिल है जो आंकड़ा बरकरार रहता है। इन परिवर्तनों के लिए, मैं नीचे दिए गए अनुसार 8 संबंधित मैट्रिक्स बनाता हूं। रोटेशन या प्रतिबिंब के बाद, आकृति खेल मैदान से परे जा सकती है, इसलिए इसे वापस खेल मैदान में वापस करना आवश्यक है। यह भी ध्यान में रखा जाना चाहिए कि कुछ आंकड़े परिवर्तन के बाद खुद में बदल सकते हैं, और ऐसे मामलों को बाहर रखा जाना चाहिए। मैं ओरिएंटेशन वर्ग के लिए अद्वितीय विकल्प जोड़ता हूं। परिणाम निम्नलिखित कोड है:

  int dimension_ = 2; const unsigned int MATRIX_SIZE = dimension_ * dimension_; int * matrix = new int[ MATRIX_SIZE ]; for( unsigned int i = 0; i < MATRIX_SIZE; i++ ) { matrix[ i ] = 0; } for( unsigned int i = 0; i < dimension_; i++ ) { int * matrix1 = new int[ MATRIX_SIZE ]; std::copy( matrix, matrix + MATRIX_SIZE, matrix1 ); matrix1[ i ] = 1; for( unsigned int j = dimension_; j < 2 * dimension_; j++ ) { if( !matrix1[ j - dimension_ ] ) { int * matrix2 = new int[ MATRIX_SIZE ]; std::copy( matrix1, matrix1 + MATRIX_SIZE, matrix2 ); matrix2[ j ] = 1; unsigned int NUMBER = 1 << dimension_; for( unsigned int l = 0; l < NUMBER; l++ ) { int * matrix3 = new int[ MATRIX_SIZE ]; std::copy( matrix2, matrix2 + MATRIX_SIZE, matrix3 ); if( l & 1 ) { for( unsigned int l1 = 0; l1 < dimension_; l1++ ) { matrix3[ l1 ] = -matrix3[ l1 ]; } } if( l & 2 ) { for( unsigned int l1 = dimension_; l1 < 2 * dimension_; l1++ ) { matrix3[ l1 ] = -matrix3[ l1 ]; } } Orientation * orientation = new Orientation( figure ); for( std::vector<Point *>::const_iterator h = figure->points().begin(); h != figure->points().end(); ++h ) { const Point * p = *h; int x = 0; for( unsigned int i1 = 0; i1 < dimension_; i1++ ) { x = x + p->coord( i1 ) * matrix3[ i1 ]; } int y = 0; for( unsigned int i1 = 0; i1 < dimension_; i1++ ) { y = y + p->coord( i1 ) * matrix3[ dimension_ + i1 ]; } Point p1( x, y ); orientation->createPoint( p1.coord( 0 ), p1.coord( 1 ) ); } orientation->moveToOrigin(); if( isUnique( orientations, orientation ) ) { orientations.push_back( orientation ); } else { delete orientation; } delete [] matrix3; } delete [] matrix2; } } delete [] matrix1; }

यह कोड प्रत्येक आंकड़े पर लागू होता है, और फिर, प्राप्त अद्वितीय अभिविन्यास x और y अक्ष के साथ स्थानांतरित किए जाते हैं जो प्रत्येक आंकड़े के सभी संभावित पदों का निर्माण करते हैं। परिणामस्वरूप, हमारे पास प्रत्येक आंकड़े के लिए विभिन्न पदों की संख्या है:

---------- Figure 1
Count = 288
---------- Figure 2
Count = 64
---------- Figure 3
Count = 280
---------- Figure 4
Count = 280
---------- Figure 5
Count = 336
---------- Figure 6
Count = 144
---------- Figure 7
Count = 168
---------- Figure 8
Count = 144
---------- Figure 9
Count = 144
---------- Figure a
Count = 36
---------- Figure b
Count = 280
---------- Figure c
Count = 144
---------- Figure d
Count = 49

फिर हम प्रत्येक संभावित स्थिति में बूलियन चर निर्दिष्ट करते हैं और एक सूत्र बनाते हैं, जैसा कि ऊपर वर्णित है। उसके बाद, हम सीधे आवेदन से मिनीसैट कहते हैं, जो एक समाधान लौटाता है - असाइन किए गए मानों के साथ हमारे चर का एक सेट सही या गलत। यह जानते हुए कि इन चरों को किस पद के लिए सौंपा गया है, हम समाधान को मुद्रित करते हैं:

bbbb 3 3 3 3
ddbc 8 8 8 3
dd 1 ccc 8 2
5 5 1 1 1 c 8 2
5 5 5 1 4 4 4 2
7 7 a 4 4 9 6 2
7 aaa 9 9 6 2
7 7 a 9 9 6 6 6

आगे क्या है

स्वाभाविक रूप से, इस पर निवास करना इतना दिलचस्प नहीं होगा। इसलिए, मेरे लिए पहला सवाल यह था कि "कितने अलग-अलग समाधान मौजूद हैं जो खेल के मैदान के मामूली बदलाव और प्रतिबिंब में भिन्न नहीं हैं?"। ऐसा करने के लिए, एसएटी सॉल्वर में एक मोड है जो आपको मौजूदा जानकारी को खोए बिना क्लॉज जोड़ने की अनुमति देता है, जो कि इस प्रक्रिया की तुलना में काफी तेजी से होता है जैसे कि समाधान को खरोंच से खोजा गया था। निम्नलिखित समाधान को एक क्लॉज जोड़कर पाया जा सकता है जिसमें पिछले समाधान में मौजूद सभी चर की उपेक्षा है। इस प्रक्रिया को जोड़ने और पिछले वाले के साथ नए समाधान की तुलना करने के बाद, खेल के मैदान के घुमाव और प्रतिबिंबों को ध्यान में रखते हुए, मुझे 1364 अलग-अलग विकल्प मिले।

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

अद्यतन

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

Pentamino उदाहरण का उपयोग करके सैट सॉल्वर का उपयोग करके टाइलिंग समस्या का समाधान करना

आगे क्या है

अद्यतन

More articles: