الغلاف الدقيق

في المجال الرياضي للتوافقيات ، إذا أعطيت مجموعة من المجموعات الفرعية لمجموعة ، فإن الغطاء الدقيق هو مجموعة فرعية بحيث يكون كل عنصر في موجودًا في مجموعة فرعية واحدة بالضبط في . يقال أن كل عنصر في مغطى بمجموعة فرعية واحدة بالضبط في . ^[1] الغطاء الدقيق هو نوع من الغطاء . إنه غير حتمي متعدد الحدود (NP) كامل وله مجموعة متنوعة من التطبيقات، تتراوح من تحسين جداول رحلات الطيران والحوسبة السحابية وتصميم الدوائر الإلكترونية . ^[2]${\displaystyle {\mathcal {S}}}$ ${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}}$${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle X}$ ${\displaystyle {\mathcal {S}}^{*}}$

بمعنى آخر، هو قسم يتكون من مجموعات فرعية موجودة في . ${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle X}$${\displaystyle {\mathcal {S}}}$

إن مشكلة الغلاف الدقيق لإيجاد غلاف دقيق هي نوع من مشكلة إشباع القيود . تمثل عناصر الخيارات وتمثل عناصر القيود. ${\displaystyle {\mathcal {S}}}$${\displaystyle X}$

تتضمن مشكلة الغلاف الدقيق العلاقة بين المجموعات الفرعية والعناصر. ولكن يمكن تمثيل مشكلة الغلاف الدقيق بأي علاقة غير متجانسة بين مجموعة من الخيارات ومجموعة من القيود. على سبيل المثال، تعادل مشكلة الغلاف الدقيق مشكلة مجموعة الضرب الدقيقة ، أو مصفوفة الحدوث ، أو الرسم البياني ثنائي الأجزاء .

في علوم الكمبيوتر ، مشكلة الغطاء الدقيق هي مشكلة قرار لتحديد ما إذا كان الغطاء الدقيق موجودًا أم لا. مشكلة الغطاء الدقيق هي NP-complete ^[3] وهي واحدة من 21 مشكلة NP-complete لكارب . ^[4] إنها NP-complete حتى عندما تحتوي كل مجموعة فرعية في S على ثلاثة عناصر بالضبط؛ تُعرف هذه المشكلة المقيدة بالغطاء الدقيق بثلاث مجموعات ، وغالبًا ما يتم اختصارها X3C. ^[3]

خوارزمية Knuth's X هي خوارزمية تبحث عن جميع الحلول لمشكلة غلاف دقيقة. DLX هو الاسم الذي يُطلق على خوارزمية X عندما يتم تنفيذها بكفاءة باستخدام تقنية Dancing Links الخاصة بـ Donald Knuth على جهاز كمبيوتر. ^[5]

يمكن تعميم مشكلة الغطاء الدقيق بشكل طفيف بحيث لا تشمل فقط القيود التي تتعلق بالحد الأقصى مرة واحدة ولكن أيضًا القيود التي تتعلق بالحد الأقصى مرة واحدة .

يعد العثور على بلاطات Pentomino وحل Sudoku من الأمثلة الجديرة بالملاحظة على مشكلات الغطاء الدقيق. تعد مشكلة n queens مشكلة غطاء دقيق معممة.

بالنظر إلى مجموعة من المجموعات الفرعية لمجموعة ، فإن الغلاف الدقيق لـ هو مجموعة فرعية لـ تلبي شرطين: ${\displaystyle {\mathcal {S}}}$${\displaystyle X}$${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}}$

• تقاطع أي مجموعتين فرعيتين متميزتين في فارغ ، أي أن المجموعتين الفرعيتين في منفصلتين زوجيًّا . بعبارة أخرى، كل عنصر في موجود في مجموعة فرعية واحدة على الأكثر في .${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$
• اتحاد المجموعات الفرعية في هو ، أي المجموعات الفرعية في cover . بعبارة أخرى، كل عنصر في موجود في مجموعة فرعية واحدة على الأقل في .${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle X}$${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$

باختصار، يكون الغلاف الدقيق دقيقًا بمعنى أن كل عنصر في موجود في مجموعة فرعية واحدة بالضبط في . ${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$

وعلى نحو مماثل، فإن الغلاف الدقيق هو عبارة عن مجموعة فرعية من تلك الأقسام . ${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}}$ ${\displaystyle X}$

لكي يكون هناك غطاء دقيق ، فمن الضروري أن: ${\displaystyle X}$

• اتحاد المجموعات الفرعية في هو . بمعنى آخر، كل عنصر في موجود في مجموعة فرعية واحدة على الأقل في .${\displaystyle {\mathcal {S}}}$${\displaystyle X}$${\displaystyle X}$${\displaystyle {\mathcal {S}}}$

إذا كانت المجموعة الفارغة موجودة في ، فلا يوجد فرق سواء كانت موجودة في أي غلاف دقيق أم لا. وبالتالي فمن المعتاد أن نفترض أن: ${\displaystyle \emptyset }$${\displaystyle {\mathcal {S}}}$

• المجموعة الفارغة ليست في . بمعنى آخر، تحتوي كل مجموعة فرعية في على عنصر واحد على الأقل.${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}^{*}}$

ليكن مجموعة من المجموعات الجزئية لمجموعة بحيث: ${\displaystyle {\mathcal {S}}=\{N,O,P,E\}}$${\displaystyle X=\{1,2,3,4\}}$

• ${\displaystyle N=\{\}}$,
• ${\displaystyle O=\{1,3\}}$,
• ${\displaystyle P=\{1,2,3\}}$، و
• ${\displaystyle E=\{2,4\}}$.

المجموعة الفرعية هي غلاف دقيق لـ ، نظرًا لأن المجموعات الفرعية و منفصلة واتحادهما هو . ${\displaystyle \{O,E\}}$${\displaystyle X}$${\displaystyle O=\{1,3\}}$${\displaystyle E=\{2,4\}}$${\displaystyle X=\{1,2,3,4\}}$

المجموعة الفرعية هي أيضًا غلاف دقيق لـ . لا يشكل تضمين المجموعة الفارغة أي فرق، لأنها منفصلة عن جميع المجموعات الفرعية ولا تغير الاتحاد. ${\displaystyle \{N,O,E\}}$${\displaystyle X}$${\displaystyle N=\{\}}$

المجموعة الفرعية ليست غلافًا دقيقًا لـ . على الرغم من أن اتحاد المجموعات الفرعية و هو ، فإن تقاطع المجموعات الفرعية و ، ليس فارغًا. وبالتالي فإن المجموعات الفرعية و لا تلبي متطلبات الانفصال للغلاف الدقيق. ${\displaystyle \{E,P\}}$${\displaystyle X}$${\displaystyle E}$${\displaystyle P}$${\displaystyle \{1,2,3,4\}=X}$${\displaystyle E}$${\displaystyle P}$${\displaystyle \{2\}}$${\displaystyle E}$${\displaystyle P}$

المجموعة الفرعية ليست أيضًا غلافًا دقيقًا لـ . على الرغم من أن و منفصلان، فإن اتحادهما ليس ، وبالتالي يفشلان في تلبية متطلبات الغلاف . ${\displaystyle \{N,P\}}$${\displaystyle X}$${\displaystyle N}$${\displaystyle P}$${\displaystyle X}$

من ناحية أخرى، لا يوجد غطاء دقيق - في الواقع، ليس حتى غطاء - لـ لأن مجموعة فرعية مناسبة من : لا تحتوي أي من المجموعات الفرعية في على العنصر 5. ${\displaystyle Y=\{1,2,3,4,5\}}$${\displaystyle \bigcup {\mathcal {S}}=\{1,2,3,4\}}$${\displaystyle Y}$${\displaystyle {\mathcal {S}}}$

ليكن S = { A , B , C , D , E , F } مجموعة من المجموعات الجزئية للمجموعة X = {1, 2, 3, 4, 5, 6, 7} بحيث:

• أ = {1، 4، 7}؛
• ب = { 1 ، 4 }؛
• ج = {4، 5، 7}؛
• د = { 3 ، 5 ، 6 }؛
• هـ = {2، 3، 6، 7}؛ و
• ف = { 2 ، 7 }.

المجموعة الفرعية S ^* = { B , D , F } عبارة عن غلاف دقيق، حيث أن كل عنصر مغطى (موجود في) بمجموعة فرعية محددة واحدة على وجه التحديد، كما يوضح التمييز.

علاوة على ذلك، فإن { B ، D ، F } هو الغلاف الدقيق الوحيد، كما يوضح الحجة التالية: نظرًا لأن A و B هما المجموعتان الفرعيتان الوحيدتان اللتان تحتويان على العنصر 1، فيجب أن يحتوي الغلاف الدقيق على A أو B ، ولكن ليس كليهما. إذا كان الغلاف الدقيق يحتوي على A ، فإنه لا يحتوي على B أو C أو E أو F ، حيث تحتوي كل من هذه المجموعات الفرعية على العنصر 1 أو 4 أو 7 المشترك مع A. إذن، D هي المجموعة الفرعية المتبقية الوحيدة، لكن المجموعة الفرعية { A ، D } لا تغطي العنصر 2. وفي الختام، لا يوجد غلاف دقيق يحتوي على A. من ناحية أخرى، إذا كان الغلاف الدقيق يحتوي على B ، فإنه لا يحتوي على A أو C ، حيث تحتوي كل من هذه المجموعات الفرعية على العنصر 1 أو 4 المشترك مع B. ونظرًا لأن D هي المجموعة الفرعية المتبقية الوحيدة التي تحتوي على العنصر 5، فيجب أن تكون D جزءًا من الغلاف الدقيق. إذا احتوى الغلاف الدقيق على D ، فإنه لا يحتوي على E ، حيث إن E يحتوي على العنصرين 3 و6 المشتركين مع D. عندئذٍ تكون F هي المجموعة الفرعية المتبقية الوحيدة، والمجموعة الفرعية { B ، D ، F } هي في الواقع غلاف دقيق. راجع المثال في المقالة حول خوارزمية Knuth's X للحصول على نسخة قائمة على المصفوفة لهذه الحجة.

تُعرَّف مشكلة الغلاف الدقيقة بالعلاقة غير المتجانسة التي تحتوي عليها مجموعة S من المجموعات الجزئية ومجموعة X من العناصر. ولكن لا يوجد شيء أساسي فيما يتعلق بالمجموعات الجزئية والعناصر.

ينشأ تمثيل لمشكلة الغلاف الدقيق كلما كانت هناك علاقة غير متجانسة R ⊆ S × X بين مجموعة S من الخيارات ومجموعة X من القيود والهدف هو تحديد مجموعة فرعية S * ^من S بحيث يكون كل عنصر في X مرتبطًا بـ R T ^بعنصر واحد بالضبط في S ^* . هنا R ^T هو عكس R.

بشكل عام، R ^T المقيدة بـ X × S ^* هي دالة من X إلى S ^* ، والتي تربط كل عنصر في X بالعنصر الفريد في S ^* الذي يرتبط R بهذا العنصر في X. هذه الدالة موجودة على ، ما لم تحتوي S ^* على عنصر (مشابه للمجموعة الفارغة) غير مرتبط R بأي عنصر في X.

تتضمن تمثيلات مشكلة الغطاء الدقيق مشكلة مجموعة الضرب الدقيقة، ومصفوفة الوقوع، ورسم بياني ثنائي الأجزاء.

في الرياضيات ، إذا كانت لدينا مجموعة S ومجموعة X من المجموعات الجزئية لـ S ، فإن المجموعة الدقيقة S ^* هي مجموعة جزئية لـ S بحيث تحتوي كل مجموعة جزئية في X على عنصر واحد فقط في S ^* . ويُقال إن كل مجموعة جزئية في X تحتوي على عنصر واحد فقط في S ^* .

مشكلة مجموعة الضرب الدقيقة هي تمثيل لمشكلة غطاء دقيقة تتضمن العلاقة الموجودة في بدلاً من تحتوي على .

على سبيل المثال، دع S = { a , b , c , d , e , f } تكون مجموعة و X = { I , II , III , IV , V , VI , VII } تكون مجموعة من المجموعات الجزئية لـ S بحيث:

• أنا = { أ ، ب }
• II = { هـ , و }
• III = { د ، هـ }
• الرابع = { أ ، ب ، ج }
• ف = { ج , د }
• السادس = { د ، هـ }
• 7 = { أ ، ج ، هـ ، و }

ثم S ^* = { b , d , f } هي مجموعة ضرب دقيقة، حيث أن كل مجموعة فرعية في X تصطدم بعنصر واحد فقط في S ^* (تحتوي على عنصر واحد فقط) كما يوضح التمييز.

هذا المثال الدقيق لمجموعة الضرب هو في الأساس نفس المثال التفصيلي أعلاه. إن عرض العلاقة الموجودة في (∈) من العناصر إلى المجموعات الفرعية يوضح أننا ببساطة استبدلنا المجموعات الفرعية المرمزة بالأحرف بالعناصر والعناصر المرقمة بالمجموعات الفرعية:

• أ ∈ I ، IV ، VII ؛
• ب ∈ I ، IV ؛
• ج ∈ الرابع ، الخامس ، السابع ؛
• د ∈ III ، V ، VI ؛
• ه ∈ الثاني , الثالث , السادس , السابع ; و
• ف ∈ II ، VII .

يمكن تمثيل العلاقة المضمنة بمصفوفة الوقوع .

تتضمن المصفوفة صفًا واحدًا لكل مجموعة فرعية في S وعمودًا واحدًا لكل عنصر في X. يكون الإدخال في صف وعمود معينين 1 إذا كانت المجموعة الفرعية المقابلة تحتوي على العنصر المقابل، ويكون 0 بخلاف ذلك.

في تمثيل المصفوفة، يكون الغطاء الدقيق عبارة عن مجموعة مختارة من الصفوف بحيث يحتوي كل عمود على 1 في صف محدد واحد فقط. يمثل كل صف خيارًا ويمثل كل عمود قيدًا.

على سبيل المثال، يمكن تمثيل العلاقة الواردة في المثال التفصيلي أعلاه بمصفوفة وقوع 6×7:

	1	2	3	4	5	6	7
أ	1	0	0	1	0	0	1
ب	1	0	0	1	0	0	0
ج	0	0	0	1	1	0	1
د	0	0	1	0	1	1	0
هـ	0	1	1	0	0	1	1
ف	0	1	0	0	0	0	1

مرة أخرى، المجموعة الفرعية S ^* = { B , D , F } هي غلاف دقيق، حيث يحتوي كل عمود على 1 في صف واحد محدد بالضبط، كما يوضح التمييز.

راجع المثال الموجود في المقالة حول خوارزمية Knuth X للحصول على حل قائم على المصفوفة للمثال المفصل أعلاه.

وبدوره، يمكن رؤية مصفوفة الحدوث أيضًا على أنها تصف رسمًا بيانيًا زائدًا . يتضمن الرسم البياني الزائد عقدة واحدة لكل عنصر في X وحافة واحدة لكل مجموعة فرعية في S ؛ يتم تضمين كل عقدة في حافة واحدة فقط من الحواف التي تشكل الغطاء.

يمكن تمثيل العلاقة المضمنة بواسطة رسم بياني ثنائي الأجزاء .

تنقسم رؤوس الرسم البياني إلى مجموعتين منفصلتين، واحدة تمثل المجموعات الفرعية في S والأخرى تمثل العناصر في X. إذا كانت المجموعة الفرعية تحتوي على عنصر، فإن الحافة تربط الرؤوس المقابلة في الرسم البياني.

في التمثيل البياني، يكون الغطاء الدقيق عبارة عن مجموعة مختارة من الرؤوس المقابلة لمجموعات فرعية بحيث يكون كل رأس مطابق لعنصر متصلًا برأس محدد واحد فقط.

على سبيل المثال، يمكن تمثيل العلاقة الواردة في المثال التفصيلي أعلاه من خلال رسم بياني ثنائي الأجزاء يحتوي على 6+7 = 13 رأسًا:

مرة أخرى، المجموعة الفرعية S ^* = { B , D , F } هي غلاف دقيق، حيث أن الرأس المقابل لكل عنصر في X متصل برأس محدد واحد على وجه التحديد، كما يوضح التمييز.

الخوارزمية X هو الاسم الذي أطلقه دونالد كنوث على "أكثر أساليب التجربة والخطأ وضوحًا" لإيجاد جميع الحلول لمشكلة الغلاف الدقيقة. [ ^5] من الناحية الفنية، تعد الخوارزمية X خوارزمية متكررة وغير حتمية وتعتمد على العمق أولاً وتتتبع إلى الوراء .

عندما يتم تنفيذ الخوارزمية X بكفاءة باستخدام تقنية Dancing Links لدونالد كنوث على جهاز كمبيوتر، يطلق عليها كنوث اسم DLX. وهي تستخدم تمثيل المصفوفة للمشكلة، والتي يتم تنفيذها كسلسلة من القوائم المرتبطة بشكل مزدوج من 1s من المصفوفة: كل عنصر 1 له رابط إلى 1 التالي أعلاه، وأسفل، وإلى اليسار، وإلى اليمين منه. ولأن مشاكل الغطاء الدقيق تميل إلى أن تكون متفرقة، فإن هذا التمثيل يكون عادة أكثر كفاءة من حيث الحجم ووقت المعالجة المطلوب. ثم يستخدم DLX تقنية Dancing Links لتحديد تبديلات الصفوف بسرعة كحلول ممكنة والتراجع بكفاءة عن التخمينات الخاطئة. ^[5]

في مشكلة الغطاء الدقيق القياسية، يجب تلبية كل قيد مرة واحدة بالضبط. ومن السهل تعميم هذا الشرط قليلاً والسماح بإمكانية تلبية بعض القيود الأولية باختيار واحد فقط ، ولكن يمكن تلبية القيود الثانوية الأخرى باختيار واحد على الأكثر .

كما يوضح كنوث، يمكن تحويل مشكلة الغلاف الدقيق المعممة إلى مشكلة غلاف دقيق مكافئة ببساطة عن طريق إلحاق صف واحد لكل عمود ثانوي، يحتوي على 1 واحد في هذا العمود. ^[6] إذا تم استيفاء عمود ثانوي معين في حل مرشح معين، فلن تكون هناك حاجة إلى الصف المضاف. ولكن إذا لم يتم استيفاء العمود الثانوي، كما هو مسموح به في المشكلة المعممة ولكن ليس في المشكلة القياسية، فيمكن تحديد الصف المضاف لضمان استيفاء العمود.

لكن كنوث يواصل شرحه قائلاً إنه من الأفضل العمل مع المشكلة المعممة بشكل مباشر، لأن الخوارزمية المعممة أبسط وأسرع: يسمح التغيير البسيط في خوارزميته X بالتعامل مع الأعمدة الثانوية بشكل مباشر.

تعتبر مشكلة الملكات N مثالاً لمشكلة الغطاء الدقيق المعممة، حيث أن القيود المقابلة لأقطار رقعة الشطرنج لها عدد أقصى وليس عدد دقيق للملكات.

بسبب اكتمالها من النوع NP، يمكن تقليص أي مشكلة من النوع NP إلى مشاكل تغطية دقيقة، والتي يمكن حلها بعد ذلك باستخدام تقنيات مثل Dancing Links. ومع ذلك، بالنسبة لبعض المشاكل المعروفة، يكون التخفيض مباشرًا بشكل خاص. على سبيل المثال، يمكن اعتبار مشكلة تبليط لوحة من الخماسيات وحل لعبة Sudoku كمشكلات تغطية دقيقة.

تعتبر مشكلة تبليط لوحة مربعة مكونة من 60 مربعًا بـ 12 شكلًا مختلفًا من أشكال البنتومينو الحرة مثالاً لمشكلة الغطاء الدقيق، كما يوضح دونالد كنوث في بحثه "الروابط الراقصة". ^[5]

على سبيل المثال، ضع في اعتبارك مشكلة تبليط رقعة شطرنج 8×8 بمربعات خماسية الشكل مع إزالة المربعات المركزية الأربعة:

11	12	13	14	15	16	17	18
21	22	23	24	25	26	27	28
31	32	33	34	35	36	37	38
41	42	43			46	47	48
51	52	53			56	57	58
61	62	63	64	65	66	67	68
71	72	73	74	75	76	77	78
81	82	83	84	85	86	87	88

تتضمن المشكلة نوعين من القيود:

البنتومينو: لكل من البنتومينو الاثني عشر، هناك قيد يقضي بوضعه مرة واحدة بالضبط. قم بتسمية هذه القيود بعد البنتومينو المقابلة: FILPNTUVWXY Z. ^[7]

المربع: لكل من المربعات الستين، هناك قيد مفاده أنه يجب أن يتم تغطيته بواسطة البنتومينو مرة واحدة فقط. قم بتسمية هذه القيود بعد المربعات المقابلة في اللوحة: ij ، حيث i هي الرتبة و j هو الملف.

وبالتالي، هناك 12+60 = 72 قيدًا في المجموع.

نظرًا لأن كلا النوعين من القيود عبارة عن قيود مرة واحدة بالضبط ، فإن المشكلة هي مشكلة غطاء دقيق.

تتضمن المشكلة العديد من الخيارات، خيار واحد لكل طريقة لوضع البنتومينو على اللوحة. ومن المناسب اعتبار كل خيار على أنه يلبي مجموعة من 6 قيود: قيد واحد لوضع البنتومينو و5 قيود للمربعات الخمسة التي يتم وضعها فيها.

في حالة رقعة شطرنج 8×8 بدون المربعات المركزية الأربعة، يوجد 1568 خيارًا من هذا القبيل، على سبيل المثال:

• {ف، 12، 13، 21، 22، 32}
• {ف، 13، 14، 22، 23، 33}
• …
• {أنا، 11، 12، 13، 14، 15}
• {أنا، 12، 13، 14، 15، 16}
• …
• {ل، 11، 21، 31، 41، 42}
• {ل، 12، 22، 32، 42، 43}
• …

أحد الحلول العديدة لمشكلة الغطاء هذه بالضبط هو المجموعة التالية المكونة من 12 خيارًا:

• {أنا، 11، 12، 13، 14، 15}
• {ن، 16، 26، 27، 37، 47}
• {ل، 17، 18، 28، 38، 48}
• {و، 21، 22، 31، 41، 42}
• {X، 23، 32، 33، 34، 43}
• {و، 24، 25، 35، 36، 46}
• {ص، 51، 52، 53، 62، 63}
• {ف، 56، 64، 65، 66، 75}
• {ز، 57، 58، 67، 76، 77}
• {ت، 61، 71، 72، 73، 81}
• {V، 68، 78، 86، 87، 88}
• {ي، 74، 82، 83، 84، 85}

تتوافق هذه المجموعة من الخيارات مع الحل التالي لمشكلة بلاط البنتومينو:

من الطبيعي أن يُنظر إلى مشكلة بلاط البنتومينو على أنها مشكلة غطاء دقيقة أكثر من مشكلة مجموعة ضرب دقيقة، لأنه من الطبيعي أكثر أن ننظر إلى كل خيار كمجموعة من القيود بدلاً من كل قيد كمجموعة من الخيارات.

كل خيار يتعلق بستة قيود فقط، والتي من السهل حصرها. ومن ناحية أخرى، فإن كل قيد يتعلق بالعديد من الخيارات، والتي من الصعب حصرها.

سواء تم النظر إليها كمشكلة غطاء دقيق أو مشكلة مجموعة ضرب دقيقة، فإن تمثيل المصفوفة هو نفسه، حيث يحتوي على 1568 صفًا يتوافق مع الخيارات و72 عمودًا يتوافق مع القيود. يحتوي كل صف على رقم 1 واحد في العمود الذي يحدد البنتومينو وخمسة أرقام 1 في الأعمدة التي تحدد المربعات المغطاة بالبنتومينو.

وباستخدام المصفوفة، يستطيع الحاسوب العثور على كافة الحلول بسرعة نسبية، على سبيل المثال، باستخدام Dancing Links .

 المقالات الرئيسية: سودوكو ، رياضيات سودوكو ، خوارزميات حل سودوكو

تكمن المشكلة في لعبة السودوكو في تعيين أرقام (أو أرقام أو قيم أو رموز) للخلايا (أو المربعات) في الشبكة من أجل تلبية قيود معينة.

في نسخة Sudoku القياسية 9×9، هناك أربعة أنواع من القيود:

الصف والعمود: يجب أن يحتوي كل تقاطع بين الصف والعمود، أي كل خلية، على رقم واحد بالضبط.

رقم الصف: يجب أن يحتوي كل صف على كل رقم مرة واحدة بالضبط

رقم العمود: يجب أن يحتوي كل عمود على كل رقم مرة واحدة بالضبط.

رقم المربع: يجب أن يحتوي كل مربع على كل رقم مرة واحدة بالضبط.

ورغم أن القيد الأول قد يبدو تافهاً، إلا أنه ضروري لضمان وجود رقم واحد فقط في كل خلية. وبطبيعة الحال، فإن وضع رقم في خلية يحظر وضع أي رقم آخر في الخلية المشغولة الآن.

حل لعبة سودوكو هو مشكلة تغطية دقيقة. وبشكل أكثر دقة، حل لعبة سودوكو هو مشكلة مجموعة إصابة دقيقة ، وهو ما يعادل مشكلة تغطية دقيقة، عندما يُنظر إليها كمشكلة اختيار الاحتمالات بحيث تحتوي كل مجموعة قيود على (أي يتم إصابتها) باحتمالية واحدة محددة بالضبط.

كل تعيين محتمل لرقم معين لخلية معينة هو احتمال (أو مرشح). عندما يتم لعب لعبة السودوكو باستخدام قلم رصاص وورقة، غالبًا ما تسمى الاحتمالات علامات قلم رصاص.

في متغير Sudoku القياسي 9×9، حيث يتم تعيين رقم واحد من 9 أرقام لكل خلية من خلايا 9×9، هناك 9×9×9=729 احتمالية. باستخدام تدوين واضح للصفوف والأعمدة والأرقام، يمكن تسمية الاحتمالات

R1C1#1، R1C1#2، …، R9C9#9.

إن حقيقة أن كل نوع من القيود يتضمن واحدًا فقط من شيء ما هي ما يجعل لعبة سودوكو مشكلة مجموعة ضرب دقيقة. يمكن تمثيل القيود بواسطة مجموعات القيود . تكمن المشكلة في تحديد الاحتمالات بحيث تحتوي كل مجموعة قيود على (أي يتم ضربها) على احتمال محدد واحد فقط.

في متغير Sudoku القياسي 9×9، هناك أربعة أنواع من مجموعات القيود المقابلة للأنواع الأربعة من القيود:

الصف والعمود: تحتوي مجموعة قيود الصف والعمود على جميع الاحتمالات الخاصة بتقاطع صف وعمود معينين، أي خلية. على سبيل المثال، تحتوي مجموعة القيود الخاصة بالصف 1 والعمود 1، والتي يمكن تسميتها R1C1، على الاحتمالات التسعة للصف 1 والعمود 1 ولكن بأرقام مختلفة:

R1C1 = { R1C1#1، R1C1#2، R1C1#3، R1C1#4، R1C1#5، R1C1#6، R1C1#7، R1C1#8، R1C1#9 }.

رقم الصف: تحتوي مجموعة قيود رقم الصف على جميع الاحتمالات لصف ورقم معينين. على سبيل المثال، تحتوي مجموعة القيود للصف 1 والرقم 1، والتي يمكن تسميتها R1#1، على الاحتمالات التسعة للصف 1 والرقم 1 ولكن بأعمدة مختلفة:

R1#1 = { R1C1#1، R1C2#1، R1C3#1، R1C4#1، R1C5#1، R1C6#1، R1C7#1، R1C8#1، R1C9#1 }.

العمود-الرقم: تحتوي مجموعة قيود العمود-الرقم على جميع الاحتمالات لعمود ورقم معينين. على سبيل المثال، تحتوي مجموعة القيود للعمود 1 والرقم 1، والتي يمكن تسميتها C1#1، على الاحتمالات التسعة للعمود 1 والرقم 1 ولكن الصفوف مختلفة:

C1#1 = { R1C1#1, R2C1#1, R3C1#1, R4C1#1, R5C1#1, R6C1#1, R7C1#1, R8C1#1, R9C1#1 }.

مجموعة قيود رقم الصندوق: تحتوي مجموعة قيود رقم الصندوق على جميع الاحتمالات الخاصة بصندوق ورقم معينين. على سبيل المثال، تحتوي مجموعة القيود الخاصة بالصندوق 1 (في الزاوية العلوية اليسرى) والرقم 1، والتي يمكن تسميتها B1#1، على الاحتمالات التسع للخلايا الموجودة في الصندوق 1 والرقم 1:

ب1#1 = { R1C1#1، R1C2#1، R1C3#1، R2C1#1، R2C2#1، R2C3#1، R3C1#1، R3C2#1، R3C3#1}.

نظرًا لوجود 9 صفوف و9 أعمدة و9 مربعات و9 أرقام، فهناك 9×9=81 مجموعة قيود صف-عمود، و9×9=81 مجموعة قيود رقم صف، و9×9=81 مجموعة قيود رقم عمود، و9×9=81 مجموعة قيود رقم مربع: 81+81+81+81=324 مجموعة قيود في المجموع.

باختصار، فإن متغير Sudoku القياسي 9×9 عبارة عن مشكلة مجموعة ضرب دقيقة تحتوي على 729 احتمالًا و324 مجموعة قيود. وبالتالي، يمكن تمثيل المشكلة بمصفوفة 729×324.

على الرغم من صعوبة تقديم مصفوفة 729×324 كاملة، إلا أنه من الممكن رؤية الطبيعة العامة للمصفوفة من خلال عدة لقطات:

قيود الصف والعمود ر1 ج1 ر1 ج2 … ر1س1#1 1 0 ⋯ ر1ج1#2 1 0 ⋯ ر1ج1#3 1 0 ⋯ ر1ج1#4 1 0 ⋯ ر1ج1#5 1 0 ⋯ ر1ج1#6 1 0 ⋯ ر1ج1#7 1 0 ⋯ ر1ج1#8 1 0 ⋯ ر1ج1#9 1 0 ⋯ ر1ج2#1 0 1 ⋯ ر1ج2#2 0 1 ⋯ ر1ج2#3 0 1 ⋯ ر1ج2#4 0 1 ⋯ ر1ج2#5 0 1 ⋯ ر1ج2#6 0 1 ⋯ ر1ج2#7 0 1 ⋯ ر1ج2#8 0 1 ⋯ ر1ج2#9 0 1 ⋯ ⋮ ⋮ ⋮ ⋱

قيود رقم الصف ر1 #1 ر1 #2 … ر1س1#1 1 0 ⋯ ر1ج1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر1ج2#1 1 0 ⋯ ر1ج2#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر1ج3#1 1 0 ⋯ ر1ج3#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر1ج4#1 1 0 ⋯ ر1ج4#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر1ج5#1 1 0 ⋯ ر1ج5#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر1ج6#1 1 0 ⋯ ر1ج6#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر1ج7#1 1 0 ⋯ ر1ج7#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر1ج8#1 1 0 ⋯ ر1ج8#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر1ج9#1 1 0 ⋯ ر1ج9#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱

قيود رقم العمود ج1 #1 ج1 #2 … ر1س1#1 1 0 ⋯ ر1ج1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر2س1#1 1 0 ⋯ ر2س1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر3ج1#1 1 0 ⋯ ر3ج1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر4ج1#1 1 0 ⋯ ر4ج1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر5ج1#1 1 0 ⋯ ر5ج1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر6ج1#1 1 0 ⋯ ر6ج1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر7س1#1 1 0 ⋯ ر7س1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر8 سي 1#1 1 0 ⋯ ر8ج1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر9س1#1 1 0 ⋯ ر9س1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱

قيود رقم الصندوق ب1 #1 ب1 #2 ⋯ ر1س1#1 1 0 ⋯ ر1ج1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر1ج2#1 1 0 ⋯ ر1ج2#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر1ج3#1 1 0 ⋯ ر1ج3#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر2س1#1 1 0 ⋯ ر2س1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر2س2#1 1 0 ⋯ ر2س2#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر2س3#1 1 0 ⋯ ر2س3#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر3ج1#1 1 0 ⋯ ر3ج1#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر3ج2#1 1 0 ⋯ ر3ج2#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱ ر3ج3#1 1 0 ⋯ ر3ج3#2 0 1 ⋯ ⋮ ⋮ ⋮ ⋱

المصفوفة الكاملة 729×324 متاحة من روبرت هانسون. ^[8]

لاحظ أن مجموعة الاحتمالات R x C y # z يمكن ترتيبها كمكعب 9×9×9 في فضاء ثلاثي الأبعاد بإحداثيات x و y و z . ثم يكون كل صف R x أو عمود C y أو رقم # z عبارة عن "شريحة" 9×9×1 من الاحتمالات؛ وكل مربع B w عبارة عن "أنبوب" 9x3×3 من الاحتمالات؛ وكل مجموعة قيود صف-عمود R x C y أو مجموعة قيود رقم الصف R x # z أو مجموعة قيود رقم العمود C y # z عبارة عن "شريط" 9x1×1 من الاحتمالات؛ وكل مجموعة قيود رقم مربع B w # z عبارة عن "مربع" 3x3×1 من الاحتمالات؛ وكل احتمال R x C y # z عبارة عن "مكعب" 1x1×1 يتكون من احتمالية واحدة. علاوة على ذلك، فإن كل مجموعة قيود أو احتمالية هي تقاطع المجموعات المكونة. على سبيل المثال، R1C2#3 = R1 ∩ C2 ∩ #3، حيث يشير ∩ إلى تقاطع المجموعة.

على الرغم من أن إصدارات Sudoku الأخرى تحتوي على أعداد مختلفة من الصفوف والأعمدة والأرقام و/أو أنواع مختلفة من القيود، إلا أنها جميعًا تنطوي على إمكانيات ومجموعات قيود، وبالتالي يمكن اعتبارها مشكلات مجموعة ضرب دقيقة.

مشكلة N ملكة هي مشكلة وضع n ملكة شطرنج على رقعة شطرنج n×n بحيث لا تهدد ملكتان بعضهما البعض. يتطلب الحل عدم مشاركة ملكتين في نفس الصف أو العمود أو القطر. إنها مثال لمشكلة تغطية دقيقة معممة. ^[5]

تتضمن المشكلة أربعة أنواع من القيود:

الرتبة: لكل من الرتب N ، يجب أن يكون هناك ملكة واحدة فقط.

الملف: بالنسبة لكل ملف من الملفات N ، يجب أن يكون هناك ملكة واحدة فقط.

الأقطار: بالنسبة لكل من الأقطار 2 N  − 1، يجب أن يكون هناك ملكة واحدة على الأكثر.

الأقطار المعكوسة: بالنسبة لكل من الأقطار المعكوسة 2 N  − 1، يجب أن يكون هناك ملكة واحدة على الأكثر.

لاحظ أن 2 N رتبة وصفوف تشكل القيود الأولية، بينما تشكل 4 N  − 2 قطري وقطري معكوس القيود الثانوية. علاوة على ذلك، نظرًا لأن كل قطري أول وأخير وقطري معكوس يتضمن مربعًا واحدًا فقط على رقعة الشطرنج، فيمكن حذفها وبالتالي يمكن للمرء تقليل عدد القيود الثانوية إلى 4 N  − 6. تحتوي مصفوفة مشكلة N ملكة على N ² صفًا و6 N  − 6 أعمدة، كل صف لوضع ملكة محتمل على كل مربع على رقعة الشطرنج، وكل عمود لكل قيد.

• مشكلة إرضاء القيود
• روابط الرقص
• خوارزمية خريطة الفروق
• مسائل كارب 21 NP-كاملة
• خوارزمية كنوث X
• قائمة مسائل NP-complete
• تقسيم المجموعة
• المطابقة المثالية والمطابقة ثلاثية الأبعاد هي حالات خاصة لمشكلة الغلاف الدقيق

• تنفيذ برنامج مجاني لحل مشكلة Exact Cover بلغة C - يستخدم Algorithm X وDancing Links. يتضمن أمثلة على ألغاز Sudoku والشبكات المنطقية.
• مُحلل الغلاف الدقيق بلغة Golang - يستخدم خوارزمية X والروابط الراقصة. يتضمن أمثلة لسودوكو وN ملكات.
• الغلاف الدقيق - مشروع مرجع الرياضيات