بمجرد أن صادفت لعبة pentomino حيث كان من الضروري وضع 13 شخصية في مربع 8 × 8. بعد فترة زمنية معينة حاولت خلالها دون جدوى حل هذه المشكلة ، قررت أنه من الضروري كتابة برنامج من شأنه القيام بذلك من أجلي. للقيام بذلك ، كان من الضروري اختيار خوارزمية حل. أول ما يتبادر إلى الذهن هو الخوارزمية المعتادة للفروع والحدود ، عندما يتم تكديس الأشكال واحدة تلو الأخرى مجاورة لبعضها البعض (الخوارزمية ذات روابط الرقص ليست مناسبة هنا ، لأن الأشكال مختلفة). عادةً ما تُستخدم الاستدلالات المختلفة لتسريع هذه الخوارزمية ، على سبيل المثال ، يفضل التفرع مع أقل عدد من الخيارات. يمكنك التوصل إلى استدلالات أخرى وتنفيذها في هذه الخوارزمية ، ولكن هنا اعتقدت أن العديد من الحيل المختلفة لتسريع حل مثل هذه المشاكل قد تم تنفيذها بالفعل في محللات SAT. لذلك ، من الضروري ترجمة المهمة إلى اللغة الرياضية المناسبة واستخدام نوع ما من SAT حلالا. حول كيفية تنفيذ ذلك وما هي النتائج التي يمكن قراءتها تحت القطع.
في البداية أريد أن أذكركم ما هي لعبة البنتامينو. هذا حقل مربّع 8x8 ، يجب تجانبه بـ 13 شكلًا - 12 تمايلًا ، والذي يتكون من 5 مربعات وشكل 2x2:
هنا يجدر بنا أن نقول ما هي مشكلة مرضية منطقية أو مشكلة SAT. بشكل عام ، يمكن صياغته على أنه اكتشاف مثل هذه القيم للمتغيرات المنطقية التي يصبح فيها التعبير المحدد صحيحًا. بشكل عام ، هذه مهمة NP كاملة ، ومع ذلك ، هناك العديد من الحيل التي تساعد على حلها بشكل فعال. للقيام بذلك ، تم تطوير العديد من التطبيقات الخاصة تسمى SAT Solvers. سأستخدم حلالا SAT المسمى minisat. لحل هذه المشكلة ، من الضروري إعادة كتابة تعبير المدخلات في شكل عادي مقترن ، أي في شكل ناتج المبالغ المنطقية للمتغيرات. تسمى كل شريحة في شكل عادي مقترن هنا فقرة ، وهي "أو" المنطقية لبعض الحرف ، أي المتغيرات المنطقية أو إنكارها. على سبيل المثال:
(x1 V ليس x3) (x2 V x4) (x2 V x3 V ليس X4)
كنت بحاجة إلى ترجمة مهمة التجانب إلى مهمة SAT. خذ بعض أشكال البنتامينو وضعها في ساحة اللعب بكل الطرق الممكنة ، بما في ذلك التحولات والانعطافات والانعكاسات. لكل موقف من هذا الشكل ، نربط متغيرًا منطقيًا وسنفترض أنه إذا كان هذا الحل موجودًا في حلنا النهائي ، فسيكون المتغير صحيحًا ، وإذا لم يكن كذلك ، فسيكون خطأ. نفعل هذا لجميع الأرقام.
الآن دعونا نضع صيغة تصف مشكلتنا ، أي أننا سنفرض قيودًا بالفعل على متغيراتنا. أول شيء يجب فعله هو التأكد من أن جميع خلايا ملعبنا ستتم تغطيتها برقم واحد على الأقل. للقيام بذلك ، لكل خلية من 64 ، نجد جميع الأشكال والمواقف لهذه الأشكال التي تغطي هذه الخلية وتأليف فقرة من المتغيرات المخصصة لهذه المواقف من الأشكال. والشيء الثاني الذي يجب القيام به هو القضاء على تقاطع الأشكال. يمكن القيام بذلك في دورة مزدوجة ، ببساطة فرز جميع المواقف المحتملة لجميع الأشكال وتحديد ما إذا كان الزوج يحتوي على خلايا مشتركة. إذا كان هناك ، ثم تتقاطع وتحتاج إلى إضافة بند من النموذج (ليس x_i V وليس x_j) ، حيث x_i هو المتغير المعين للموضع الأول ، و x_j هو الموضع الثاني. يكون هذا الشرط صحيحًا عندما تكون x_i و x_j غير مساوية لواحد في نفس الوقت ، أي تستثني التقاطعات. وأخيرًا ، الشيء الثالث الذي يجب مراعاته هو أن كل شخصية يمكن أن تكون موجودة في الملعب مرة واحدة فقط. للقيام بذلك ، ننتقل أيضًا إلى جميع المواقف لكل شكل في دورة مزدوجة ولكل زوج من المواقف من نفس الرقم نقوم بوضع بند مماثل للفقرة السابقة ويتكون من سلبيين. أي عندما يظهر رقمان متطابقان (ولكن في مواقف مختلفة) ، فإن أحد هذه الشروط سيعطي خطأ ، وبالتالي ، سيستبعد مثل هذا الحل.
كانت كلها نظرية ، والآن دعنا ننتقل إلى الممارسة. كل رقم لديه رقم من 1 إلى د لتمييزه عن الآخرين وطبعه بسهولة. ثم قم بإنشاء مصفوفة لمجال اللعب وترميز الخلايا المقابلة لمجال اللعب على أنها مشغولة / غير مشغولة بالشكل:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. 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
ثم نقوم بتعيين متغير منطقي لكل موضع ممكن وننشئ صيغة ، كما هو موضح أعلاه. بعد ذلك ، نسمي minisat مباشرة من التطبيق ، والذي يعيد الحل - مجموعة من المتغيرات الخاصة بنا مع القيم المعينة صواب أو خطأ. بمعرفة المواضع التي تم تعيين هذه المتغيرات لها ، نقوم بطباعة الحل:
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
ما هي الخطوة التالية
بطبيعة الحال ، فإن الحديث عن هذا لن يكون مثيرا للاهتمام. لذلك ، كان السؤال الأول الذي طرح لي هو "كم عدد الحلول المختلفة الموجودة التي لا تختلف في المنعطفات التافهة وانعكاسات الملعب؟". للقيام بذلك ، هناك وضع في حلال SAT يسمح لك بإضافة عبارات دون فقدان المعلومات الحالية ، مما يسرع العملية بشكل كبير مقارنة كما لو تم البحث عن الحل من نقطة الصفر. يمكن العثور على الحل التالي بإضافة جملة تحتوي على نفي جميع المتغيرات الموجودة في الحل السابق. بعد إضافة هذا الإجراء ومقارنة الحل الجديد بالحل السابق ، مع مراعاة المنعطفات وانعكاسات مجال اللعب ، حصلت على 1364 خيارًا مختلفًا.
امتداد آخر مثير للاهتمام قمت بتطبيقه كان دراسة أشكال أخرى مختلفة من الملعب والأشكال. وأخيرًا ، كانت دراسة الملاعب ثلاثية الأبعاد مثيرة للاهتمام للغاية. لكن هذا موضوع لمقال آخر.
تحديث
بعد إضافة شرط إضافي: لكل شكل من فقرة واحدة - يجب أن يكون هناك موضع واحد على الأقل من هذا الرقم في الملعب ، أصبح الحساب أسرع بكثير. بالإضافة إلى ذلك ، تم إصلاح خطأ واحد ، ونتيجة لذلك كان عدد جميع الخيارات الفريدة الممكنة هو 16146.