بوليومينو

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 10 صور
الموسوعة الحرة
قطع البنتومينو الثمانية عشر أحادية الجانب ، بما في ذلك 6 أزواج متطابقة.

البوليومينو هو شكل هندسي مستوٍ متصل ، يتكون من ضم عدد محدود من المربعات الوحدوية حافةً بحافة. ​​وهو شكل متعدد الأشكال تتكون خلاياه من مربعات . ويمكن اعتباره مجموعة فرعية محدودة ومتصلة من تبليط المربعات المنتظم .

استُخدمت قطع البوليومينو في الألغاز الشائعة منذ عام 1907 على الأقل، ويعود تاريخ تعداد قطع البنتومينو إلى العصور القديمة. [ 1 ] نُشرت العديد من النتائج التي تتضمن قطعًا مكونة من 1 إلى 6 مربعات لأول مرة في مجلة Fairy Chess Review بين عامي 1937 و1957، تحت مسمى "مسائل التقسيم". ابتكر سولومون دبليو. غولومب اسم "بوليومينو" عام 1953، [ 2 ] وشاع استخدامه بفضل مارتن غاردنر في عمود " الألعاب الرياضية " المنشور في مجلة Scientific American في نوفمبر 1960. [ 3 ]

ترتبط بالمتعددات الشكلية المعينية ، المُشكّلة من مثلثات متساوية الأضلاع ؛ والمتعددات السداسية ، المُشكّلة من سداسيات منتظمة ؛ وغيرها من الأشكال المستوية المتعددة . وقد تم تعميم المتعددات الشكلية إلى أبعاد أعلى عن طريق ضم المكعبات لتشكيل متعددات المكعبات ، أو المكعبات الفائقة لتشكيل متعددات المكعبات الفائقة.

في الفيزياء الإحصائية ، تُطبَّق دراسة البوليومينو ونظائرها ذات الأبعاد الأعلى (والتي يُشار إليها غالبًا باسم حيوانات الشبكة في هذا المجال) على مسائل في الفيزياء والكيمياء. وقد استُخدمت البوليومينو كنماذج للبوليمرات المتفرعة وتجمعات الترشيح . [ 4 ]

تظهر متعددات الحدود أيضًا في الجبر التبادلي . في هذا السياق، يمكن استخدام متعدد الحدود لتعريف مثالي ثنائي الحد مُوَلَّد بواسطة مُقَيِّمات ثنائية داخلية في حلقة متعددة الحدود، حيث تتوافق متغيراتها مع رؤوس متعدد الحدود، مما يُعمِّم المُثُل المُحدِّدة الكلاسيكية للمصفوفات. [ 5 ] [ 6 ]

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

تُعدّ البوليومينو ذات الثقوب غير ملائمة لبعض الأغراض، مثل مسائل التبليط. وفي بعض السياقات، تُستبعد البوليومينو ذات الثقوب، ويُسمح فقط باستخدام البوليومينو المتصلة ببساطة . [ 7 ]

تعداد البوليومينو

البوليومينو الحرة، أحادية الجانب، والثابتة

هناك ثلاث طرق شائعة لتمييز البوليومينو لأغراض التعداد: [ 8 ] [ 9 ]

  • تتميز البوليومينو الحرة بأنها لا تمثل تحويلاً جامداً ( إزاحة ، دوران ، انعكاس ، أو انعكاس انزلاقي ) لقطعة أخرى (قطع يمكن التقاطها وقلبها). ولا يؤدي إزاحة البوليومينو الحرة أو تدويرها أو انعكاسها أو انعكاسها الانزلاقي إلى تغيير شكلها.
  • تتميز قطع البوليومينو أحادية الجانب بأنها لا تمثل إزاحة أو دورانًا لقطعة أخرى (قطع لا يمكن قلبها). ولا يؤدي تحريك أو تدوير قطعة بوليومينو أحادية الجانب إلى تغيير شكلها.
  • تكون قطع البوليومينو الثابتة متميزة عندما لا يكون أي منها إزاحة لقطعة أخرى (قطع لا يمكن قلبها أو تدويرها). إزاحة قطعة بوليومينو ثابتة لن تغير شكلها.

يوضح الجدول التالي أعداد البوليومينو من أنواع مختلفة تحتوي على n خلية.

ناسمحرمن جانب واحدمُثَبَّت
المجموعمع ثقببدون ثقب
1مونومينو10111
2الدومينو10112
3ترومينو20226
4التترومينو505719
5بنتومينو120121863
6هيكسومينو3503560216
7هيبتومينو1081107196760
8أوكتومينو36963637042725
9نونومينو128537124825009910
10ديكومينو46551954460918936,446
11أونديكومينو17,07397916,09433896135,268
12دوديكومينو63,600466358,937126,759505,861
13ترايديكومينو238,59121,474217,117476,2701,903,890
 تسلسل OEISA000105A001419A000104A000988A001168

تم حصر عدد البوليومينو الثابتة في عام 2004 حتى n = 56 بواسطة إيوان جنسن، [ 10 ] وفي عام 2024 حتى n = 70 بواسطة جيل باريكيت وجيل بن شاشار. [ 11 ]

تم حصر عدد البوليومينو الحرة في عام 2007 حتى n = 28 بواسطة توماس أوليفيرا إي سيلفا، [ 12 ] وفي عام 2012 حتى n = 45 بواسطة توشيهيرو شيراكاوا، [ 13 ] وفي عام 2023 حتى n = 50 بواسطة جون ماسون، [ 14 ] وفي عام 2025 حتى n = 59 بواسطة توشيهيرو شيراكاوا. [ 15 ]

تتضمن تسلسلات OEIS المذكورة أعلاه، باستثناء A001419، العدد 1 لعدد البوليومينو الصفري؛ البوليومينو الصفري هو الذي يتكون من صفر مربعات.

تناظرات البوليومينو

المجموعة ثنائية السطوح D₄ هي مجموعة التناظرات ( مجموعة التناظر ) للمربع. تحتوي هذه المجموعة على أربعة دورانات وأربعة انعكاسات. وتتولد من خلال انعكاسات متناوبة حول المحور السيني وحول قطر. يقابل كل متعدد أشكال حر ثمانية متعددات أشكال ثابتة على الأكثر، وهي صوره تحت تناظرات D₄ . مع ذلك، لا تكون هذه الصور بالضرورة متميزة: فكلما زاد تناظر متعدد الأشكال الحر، قلّ عدد نظائره الثابتة المتميزة. لذلك، قد يقابل متعدد الأشكال الحر الثابت تحت بعض أو كل تناظرات D₄ غير التافهة أربعة أو اثنين أو متعدد أشكال ثابتة فقط. رياضياً، تُعد متعددات الأشكال الحرة فئات تكافؤ لمتعددات الأشكال الثابتة تحت المجموعة D₄ .

تتمتع البوليومينو بالتناظرات الممكنة التالية؛ [ 16 ] يتم تحديد أقل عدد من المربعات اللازمة في البوليومينو ذي هذا التناظر في كل حالة:

  • 8 قطع بوليومينو ثابتة لكل قطعة بوليومينو حرة:
    • لا يوجد تناظر (4)
  • 4 قطع بوليومينو ثابتة لكل قطعة بوليومينو حرة:
    • التناظر المرآوي بالنسبة لأحد اتجاهات خطوط الشبكة (4)
    • التناظر المرآوي بالنسبة لخط قطري (3)
    • التناظر الدوراني الثنائي: C 2 (4)
  • 2 بوليومينو ثابت لكل بوليومينو حر:
    • التناظر بالنسبة لاتجاهي خط الشبكة، وبالتالي التناظر الدوراني الثنائي: D 2 (2) (المعروف أيضًا باسم مجموعة كلاين الرباعية )
    • التناظر بالنسبة لكلا الاتجاهين القطريين، وبالتالي التناظر الدوراني الثنائي: D 2 (7)
    • التناظر الدوراني الرباعي: C 4 (8)
  • قطعة واحدة ثابتة من البوليومينو لكل قطعة بوليومينو حرة:
    • جميع تناظرات المربع: D 4 (1).

وبالمثل، يعتمد عدد البوليومينو أحادي الجانب على تناظر البوليومينو على النحو التالي:

  • 2 من البوليومينو أحادي الجانب لكل بوليومينو حر:
    • لا يوجد تناظر
    • تناظر دوراني ثنائي: C 2
    • التناظر الدوراني الرباعي: C 4
  • قطعة واحدة من البوليومينو أحادية الجانب لكل بوليومينو حر:
    • جميع تناظرات المربع: D 4
    • التناظر المرآوي بالنسبة لأحد اتجاهات خطوط الشبكة
    • التناظر المرآوي بالنسبة لخط قطري
    • التناظر بالنسبة لاتجاهي خطوط الشبكة، وبالتالي التناظر الدوراني الثنائي: D 2
    • التناظر بالنسبة لكلا الاتجاهين القطريين، وبالتالي التناظر الدوراني الثنائي: D 2 .

يوضح الجدول التالي أعداد البوليومينو التي تحتوي على n مربع، مرتبة حسب مجموعات التناظر.

نلا أحدمرآة 90 درجةمرآة بزاوية 45 درجةج 2D 2 90°D 2 45°ج 4د 4
100000001
200001000
300101000
411011001
552211001
6206252000
7849743100
8316235184111
911963826194002
1044619022738100
1116750147917310200
1262,8783417927815333
 تسلسل OEISA006749A006746A006748A006747A056877A056878A144553A142886

[ 17 ]

خوارزميات لحصر متعددات الأشكال الثابتة

الخوارزميات الاستقرائية

يمكن الحصول على كل متعدد الأشكال ذي الحجم n + 1 عن طريق إضافة مربع إلى متعدد الأشكال ذي الحجم n . وهذا يؤدي إلى خوارزميات لتوليد متعددات الأشكال استقرائيًا.

ببساطة، عند إعطاء قائمة من متعددات الأشكال (polyominoes) بحجم n ، يمكن إضافة مربعات بجوار كل متعدد أشكال في كل موضع ممكن، ثم يُضاف متعدد الأشكال الناتج بحجم n +1 إلى القائمة إذا لم يكن نسخة مكررة من متعدد أشكال موجود مسبقًا. يُقلل تحسين ترتيب عملية التعداد ووضع علامات على المربعات المتجاورة التي لا ينبغي أخذها في الاعتبار من عدد الحالات التي يجب فحصها بحثًا عن التكرارات. [ 18 ] يمكن استخدام هذه الطريقة لتعداد متعددات الأشكال الحرة أو الثابتة.

استخدم العديد من الباحثين طريقةً أكثر تطورًا، وصفها ريدلماير، ليس فقط لحساب عدد متعددات المربعات (دون الحاجة إلى تخزين جميع متعددات المربعات ذات الحجم n في مصفوفة size لحساب تلك ذات الحجم n +1)، بل أيضًا لإثبات حدود عليا لعددها. وتتلخص الفكرة الأساسية في البدء بمربع واحد، ثم إضافة المربعات إليه بشكل متكرر. وبحسب التفاصيل، قد يتم حساب كل متعدد مربعات n -omino عدد n من المرات، مرة واحدة بدءًا من كل مربع من مربعاته n ، أو قد يتم ترتيبها لحساب كل متعدد مربعات مرة واحدة فقط.

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

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

إذا رغب المرء في حساب عدد البوليومينو الحرة، فيمكنه التحقق من التناظرات بعد إنشاء كل بوليومينو من النوع n . مع ذلك، يُعدّ توليد البوليومينو المتناظرة بشكل منفصل (باستخدام صيغة معدلة من هذه الطريقة) أسرع [ 19 ] ، ومن ثم تحديد عدد البوليومينو الحرة باستخدام مبرهنة بيرنسايد .

طريقة مصفوفة النقل

تُعدّ الخوارزميات الأكثر فعالية حاليًا من ضمن نموذج مصفوفة النقل، ويُشار إليها اختصارًا بخوارزميات مصفوفة النقل (TMAs). قام أندرو كونواي [ 21 ] بتطبيق خوارزمية مصفوفة النقل لأول مرة في التسعينيات، وحسب 25 حدًا من متتالية البوليومينو الثابتة ( A001419 في OEIS). ثمّ قام إيوان جنسن بتحسين أساليب كونواي، وطبّق خوارزمية مصفوفة النقل بالتوازي لأول مرة في ورقتين بحثيتين في أوائل الألفية الثانية [ 22 ] [ 23 ] ، حيث حسب 56 حدًا. ونتيجةً لهذا العمل، تُعرف أي خوارزمية مصفوفة نقل أحيانًا باسم خوارزمية جنسن. وفي عام 2024، قدّم جيل باريكيت وطالبه جيل بن شاشار تحسينًا آخر من خلال تشغيل خوارزمية مصفوفة النقل على دوران 45 درجة للشبكة المربعة، وهي مسألة مكافئة ولكنها أسهل حسابيًا [ 24 ] . ويحمل هذا النهج الرقم القياسي في عدّ البوليومينو، حيث بلغ 70 حدًا.

كقاعدة عامة، تُعدّ طرق TMA أسرع بكثير من الطرق السابقة، ولكن وقت تشغيلها لا يزال يتناسب أُسّيًا مع n . ويتحقق ذلك تقريبًا بتحديد عرض (في حالة الأقطار، عرض قطري)، وحساب عدد الأشكال متعددة الأضلاع التي تقع ضمن مستطيلات بهذا العرض. عند القيام بذلك، يكفي تتبع حدود الشكل متعدد الأضلاع، وبما أن عدة أشكال متعددة الأضلاع يمكن أن تتوافق مع حد واحد، فإن هذه الطريقة أسرع من طريقة توليد كل شكل متعدد الأضلاع. بتكرار هذه العملية لكل عرض، نحصل على جميع الأشكال متعددة الأضلاع.

على الرغم من أن وقت تشغيلها ممتاز، إلا أن المقابل هو أن هذه الخوارزمية تستخدم كميات هائلة من الذاكرة (هناك حاجة إلى العديد من الجيجابايت من الذاكرة لـ n أعلى من 50)، وهي أصعب بكثير في البرمجة من الطرق الأخرى، ولا يمكن استخدامها حاليًا لحساب البوليومينو الحرة.

النمو التقاربي لعدد البوليومينو

متعددات الأضلاع الثابتة

تدعم الحجج النظرية والحسابات العددية التقدير لعدد البوليومينو الثابتة ذات الحجم n

أن∼جλنن{\displaystyle A_{n}\sim {\frac {c\lambda ^{n}}{n}}}

حيث λ = 4.0626 و c = 0.3169. [ 25 ] ومع ذلك، فإن هذه النتيجة غير مثبتة وقيم λ و c هي مجرد تقديرات.

إن النتائج النظرية المعروفة ليست دقيقةً كفايةً مقارنةً بهذا التقدير. وقد ثبت أن

ليمن→∞(أن)1ن=λ{\displaystyle \lim _{n\rightarrow \infty }(A_{n})^{\frac {1}{n}}=\lambda }

موجود. بعبارة أخرى، ينمو A n بشكل أُسّي . أفضل حد أدنى معروف لـ λ ، والذي تم التوصل إليه في عام 2016، هو 4.00253. [ 26 ] وأفضل حد أعلى معروف هو λ < 4.5252 . [ 27 ]

لتحديد الحد الأدنى، تُعدّ طريقة دمج متعددات الأومينو طريقةً بسيطةً وفعّالةً للغاية. يُعرَّف المربع العلوي الأيمن بأنه المربع الأقصى يمينًا في الصف العلوي من متعدد الأومينو. وبالمثل، يُعرَّف المربع السفلي الأيسر. عندئذٍ، يمكن ربط المربع العلوي الأيمن لأي متعدد أومينو بحجم n بالمربع السفلي الأيسر لأي متعدد أومينو بحجم m لإنتاج متعدد أومينو فريد بحجم ( n + m ). هذا يُثبت أن A <sub>n </sub> · A <sub>m</sub> ≤ A <sub>n + m </sub> . باستخدام هذه المتباينة، يمكن إثبات أن λ ≥ ( A <sub>n</sub> ) 1/ n لجميع قيم n . تُنتج تحسينات هذه الطريقة، بالإضافة إلى بيانات A <sub> n</sub>، الحد الأدنى المذكور أعلاه.

يُمكن الوصول إلى الحد الأعلى بتعميم الطريقة الاستقرائية لحصر متعددات المربعات. فبدلاً من إضافة مربع واحد في كل مرة، تُضاف مجموعة من المربعات في كل مرة. ويُشار إلى هذه العملية غالبًا بإضافة فروع . بإثبات أن كل متعدد مربعات من النوع n هو سلسلة من الفروع، وبإثبات حدود تركيبات الفروع الممكنة، يُمكن الحصول على حد أعلى لعدد متعددات المربعات من النوع n . على سبيل المثال، في الخوارزمية الموضحة أعلاه، يجب في كل خطوة اختيار عدد أكبر، ويُضاف ثلاثة أعداد جديدة على الأكثر (لأن ثلاثة مربعات غير مرقمة على الأكثر مجاورة لأي مربع مرقم). يُمكن استخدام هذه الطريقة للحصول على حد أعلى قدره 6.75. باستخدام 2.8 مليون فرع، حصل كلارنر وريفست على حد أعلى قدره 4.65، [ 28 ] والذي حسّنه لاحقًا باريكيت وشالاه إلى 4.5252. [ 27 ]

قطع البوليومينو المجانية

ترتبط تقديرات عدد البوليومينو الثابتة والبوليومينو الحرة ارتباطًا بسيطًا. يُقابل البوليومينو الحر الذي لا يمتلك أي تناظر (دوران أو انعكاس) ثمانية بوليومينو ثابتة مختلفة، وبالنسبة لقيم n الكبيرة ، فإن معظم البوليومينو من النوع n لا تمتلك أي تناظر. لذلك، فإن عدد البوليومينو الثابتة من النوع n يُقارب ثمانية أضعاف عدد البوليومينو الحرة من النوع n . علاوة على ذلك، تزداد دقة هذا التقدير بشكل أُسّي مع ازدياد قيمة n . [ 16 ]

فئات خاصة من البوليومينو

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

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

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

تم تعداد متعددات الأضلاع الموجهة، [ 30 ] متعددات الأضلاع المحدبة العمودية (أو الصفية)، [ 31 ] ومتعددات الأضلاع المحدبة [ 32 ] بشكل فعال بواسطة المساحة n ، وكذلك بواسطة بعض المعلمات الأخرى مثل المحيط، باستخدام الدوال المولدة .

يكون شكل البوليومينو متساوي الأبعاد إذا كانت مساحته تساوي محيطه. يجب أن يتكون شكل البوليومينو المتساوي الأبعاد من عدد زوجي من المربعات؛ أي عدد زوجي أكبر من 15 ممكن. على سبيل المثال، يُعد كل من شكل البوليومينو ذي الـ 16 مربعًا على شكل مربع 4  ×  4 وشكل البوليومينو ذي الـ 18 مربعًا على شكل مستطيل 3  ×  6 متساوي الأبعاد. أما بالنسبة لأشكال البوليومينو التي تحتوي على 15 مربعًا أو أقل، فإن المحيط دائمًا ما يتجاوز المساحة. [ 33 ]

التبليط باستخدام البوليومينو

في الرياضيات الترفيهية ، غالبًا ما يتم طرح تحديات لتغطية منطقة محددة، أو المستوى بأكمله، باستخدام البوليومينو، [ 34 ] ويتم التحقيق في المشكلات ذات الصلة في الرياضيات وعلوم الكمبيوتر .

تبليط المناطق بمجموعات من البوليومينو

تتطلب الألغاز عادةً تبليط منطقة معينة بمجموعة معينة من قطع البوليومينو، مثل قطع البنتومينو الاثنتي عشرة. يحتوي كتابا غولومب وغاردنر على العديد من الأمثلة. من الألغاز الشائعة تبليط مستطيل أبعاده 6×10 باستخدام قطع البنتومينو الاثنتي عشرة؛ وقد تم التوصل إلى 2339 حلاً لهذا اللغز في عام 1960. [ 35 ] عندما يُسمح بنسخ متعددة من قطع البوليومينو في المجموعة، يُعرّف غولومب تسلسلاً هرمياً للمناطق المختلفة التي يمكن تبليطها بمجموعة معينة، مثل المستطيلات والشرائط والسطح المستوي بأكمله، ويُبين أن إمكانية تبليط السطح باستخدام قطع البوليومينو من مجموعة معينة أمر غير قابل للتقرير ، وذلك من خلال ربط مجموعات من قطع وانغ بمجموعات من قطع البوليومينو. [ 36 ]

نظرًا لأن مشكلة تبليط مناطق من المستوى بمجموعات من البوليومينو تُصنف ضمن فئة NP-complete ، [ 37 ] فإن التبليط بأكثر من بضع قطع يصبح معقدًا للغاية، مما يستدعي استخدام الحاسوب. يعتمد النهج التقليدي لتبليط مناطق محدودة من المستوى على تقنية في علوم الحاسوب تُسمى التراجع . [ 38 ] أما النهج الجبري البديل، فيُخصص متغيرًا ثنائيًا لكل موضع ممكن للبلاطة، بحيث يمكن صياغة متطلبات التبليط الصحيح - بما في ذلك تغطية كل خلية مرة واحدة فقط، واستيفاء أي قيود محددة على استخدام البلاطات - كمسألة برمجة خطية ثنائية ، وحلها باستخدام برامج التحسين العامة. [ 39 ] [ 40 ]

في لعبة سودوكو الصور المقطوعة، يتم تبليط شبكة مربعة بمناطق على شكل متعدد الأضلاع (التسلسل A172477 في OEIS ) .

تبليط المناطق بنسخ من متعدد واحد

يتناول نوع آخر من المسائل ما إذا كان بإمكان نسخ من متعددات الأشكال المعطاة تبليط مستطيل ، وإذا كان الأمر كذلك، فما هي المستطيلات التي يمكنها تبليطها. [ 41 ] وقد دُرست هذه المسائل على نطاق واسع لمتعددات أشكال معينة، [ 42 ] وتتوفر جداول نتائج لمتعددات أشكال فردية. [ 43 ] وقد أثبت كلارنر وغوبل أنه لأي متعدد أشكال، توجد مجموعة منتهية من المستطيلات الأولية التي يبلطها، بحيث يمكن تبليط جميع المستطيلات الأخرى التي يبلطها بتلك المستطيلات الأولية. [ 44 ] [ 45 ] كما أثبت كامينتسكي وكوك كيف يمكن لمتعددات أشكال منفصلة (تُسمى "مثقوبة") تبليط مستطيلات. [ 46 ]

بالإضافة إلى المستطيلات، وضع غولومب تصنيفه الهرمي لقطع البوليومينو المفردة: قد تُغطي قطعة البوليومينو مستطيلاً، أو نصف شريط، أو شريطًا منحنيًا، أو نسخة مكبرة منها، أو ربع دائرة، أو شريطًا، أو نصف مستوى ، أو المستوى بأكمله، أو تركيبات معينة، أو لا تُغطي أيًا من هذه. تتضمن هذه التصنيفات دلالات معينة، بعضها واضح (على سبيل المثال، إذا غطت قطعة البوليومينو نصف المستوى، فإنها تُغطي المستوى بأكمله)، وبعضها الآخر أقل وضوحًا (على سبيل المثال، إذا غطت قطعة البوليومينو نسخة مكبرة منها، فإنها تُغطي ربع الدائرة). تُصنف قطع البوليومينو التي يصل حجمها إلى 6 ضمن هذا التصنيف الهرمي (مع اعتبار قطعة سداسية واحدة، والتي تبين لاحقًا أنها تُغطي مستطيلاً، أمرًا لم يُحسم في ذلك الوقت). [ 47 ]

In 2001 Cristopher Moore and John Michael Robson showed that the problem of tiling one polyomino with copies of another is NP-complete.[48][49]

Tiling the plane with copies of a single polyomino

The two tiling nonominoes not satisfying the Conway criterion.

Tiling the plane with copies of a single polyomino has also been much discussed. It was noted in 1965 that all polyominoes up to hexominoes[50] and all but four heptominoes tile the plane.[51] It was then established by David Bird that all but 26 octominoes tile the plane.[52] Rawsthorne found that all but 235 polyominoes of size 9 tile,[53] and such results have been extended to higher area by Rhoads (to size 14)[54] and others. Polyominoes tiling the plane have been classified by the symmetries of their tilings and by the number of aspects (orientations) in which the tiles appear in them.[55][56]

The study of which polyominoes can tile the plane has been facilitated using the Conway criterion: except for two nonominoes, all tiling polyominoes up to size 9 form a patch of at least one tile satisfying it, with higher-size exceptions more frequent.[57]

Several polyominoes can tile larger copies of themselves, and repeating this process recursively gives a rep-tile tiling of the plane. For instance, for every positive integer n, it is possible to combine n2 copies of the L-tromino, L-tetromino, or P-pentomino into a single larger shape similar to the smaller polyomino from which it was formed.[58]

Tiling a common figure with various polyominoes

A minimal compatibility figure for the T and W pentominoes.

تتمثل مشكلة التوافق في إيجاد شكل يمكن تبليطه باستخدام كل من قطع البوليومينو، وذلك باختيار قطعتين أو أكثر. وقد حظي توافق البوليومينو باهتمام واسع في الدراسات منذ تسعينيات القرن الماضي. نشر كل من خورخي لويس ميريلس وجيوفاني ريستا مواقع إلكترونية تتضمن نتائج منهجية [ 59 ] [ 60 ] ، كما عرض ليفيو زوكا نتائج لبعض الحالات المعقدة، مثل ثلاث قطع بنتومينو مختلفة [ 61 ] . قد تكون المشكلة العامة صعبة. نُشر أول شكل توافق لقطع البنتومينو من النوعين L وX في عام 2005، واحتوى على 80 بلاطة من كل نوع [ 62 ] . وقد ثبت عدم توافق العديد من أزواج البوليومينو من خلال الاستنفاد المنهجي. ولا توجد خوارزمية معروفة لتحديد ما إذا كانت قطعتان من البوليومينو متوافقتين أم لا.

قطع البوليومينو في الألغاز والألعاب

إضافةً إلى مسائل التبليط المذكورة أعلاه، توجد ألغاز رياضية ترفيهية تتطلب طي قطعة متعددة الأشكال (بوليومينو) لتكوين أشكال أخرى. [ 63 ] [ 64 ] اقترح غاردنر عدة ألعاب بسيطة باستخدام مجموعة من قطع البنتومينو الحرة ولوحة شطرنج . [ 3 ] تستخدم بعض أنواع لعبة سودوكو مناطق غير متعددة الأشكال على الشبكة. تعتمد لعبة الفيديو تتريس على قطع التترومينو السبعة أحادية الجانب (المكتوبة "تتريمينو" في اللعبة)، وتستخدم لعبة بلوكوس اللوحية جميع قطع البوليومينو الحرة حتى البنتومينو.

أصل الكلمة

كلمة "بوليومينو" وأسماء أحجامها المختلفة مشتقة من كلمة "دومينو" ، وهي قطعة لعب شائعة تتكون من مربعين. يُعتقد أن اسم "دومينو" لهذه القطعة مشتق من كلمة "دومينو" اللاتينية، وهي تعني رداءً مرقطًا يُستخدم في حفلات التنكر . [ 65 ] على الرغم من هذا الأصل اللغوي، عند تسمية البوليومينو، يُفسَّر الحرف الأول "د" من كلمة "دومينو" تفسيرًا مجازيًا على أنه نسخة من البادئة "دي " التي تعني "اثنان"، ويُستبدل ببادئات عددية أخرى .

انظر أيضاً

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

ملحوظات

  1. ↑ يكتب غولومب ( مقدمة الطبعة الأولى من كتاب Polyominoes ) "إن الملاحظة التي تفيد بوجود اثني عشر نمطًا مميزًا (الخماسي) يمكن تشكيلها بواسطة خمسة أحجار متصلة على لوحة لعبة Go ... تنسب إلى أحد أساتذة تلك اللعبة القدماء".
  2. ↑ غولومب، سولومون و. (1994). البوليومينو (  الطبعة الثانية). برينستون، نيوجيرسي: مطبعة جامعة برينستون. ISBN 978-0-691-02444-8.
  3. 1 2 غاردنر، م. (نوفمبر 1960). "المزيد عن الأشكال التي يمكن تكوينها باستخدام قطع الدومينو المعقدة (الألعاب الرياضية)". مجلة ساينتفك أمريكان . 203 (5): 186-201 . doi : 10.1038/scientificamerican1160-186 . JSTOR 24940703 . 
  4. ↑ ويتينغتون، إس جي؛ سوتيروس، سي إي (1990). "حيوانات الشبكة: نتائج دقيقة وتخمينات جامحة". في غريمت، جي؛ ويلش، دي (محرران). الاضطراب في الأنظمة الفيزيائية . مطبعة جامعة أكسفورد.
  5. ↑ J. Herzog, T. Hibi, H. Ohsugi, Binomial Ideals , Graduate Texts in Mathematics 279, Springer, 2018, Chapter 8.
  6. ↑ AA Qureshi, “Ideals generated by 2-minors, collections of cells and stack polyominoes”, Journal of Algebra 357 (2012), 279–303.
  7. ↑ غرونباوم، برانكو ؛ شيبارد، جي سي (1987). التبليط والأنماط . نيويورك: دبليو إتش فريمان وشركاه. ISBN 978-0-7167-1193-3.
  8. ↑ ريدلماير، د. هيو (1981). "عدّ البوليومينو: هجوم آخر" . الرياضيات المتقطعة . 36 (2): 191-203 . doi : 10.1016/0012-365X(81)90237-5 .
  9. ↑ غولومب، الفصل 6
  10. ↑ إيوان جنسن. "سلسلة لحيوانات الشبكة أو البوليومينو" . مؤرشف من الأصل بتاريخ 12-06-2007 . تم الاطلاع عليه بتاريخ 06-05-2007 .
  11. ↑ باريكيت، جيل؛ بن شاشار، جيل (يناير 2024). "إعادة النظر في عدّ البوليومينو" . وقائع ندوة هندسة الخوارزميات والتجارب (ALENEX) لعام 2024 - إعادة النظر في عدّ البوليومينو . جمعية الرياضيات الصناعية والتطبيقية. الصفحات 133-143 . doi : 10.1137/1.9781611977929.10 . ISBN  978-1-61197-792-9.
  12. ↑ توماس أوليفيرا إي سيلفا. "تعداد الحيوانات على التبليط الإقليدي {4,4}" . مؤرشف من الأصل بتاريخ 23 أبريل 2007. تم الاطلاع عليه بتاريخ 6 مايو 2007 .
  13. ↑ "المربع السحري التوافقي، تعداد متعددات الأشكال مع مراعاة التناظر" (PDF) .
  14. ↑ "حساب حجم البوليومينو 50" (ملف PDF) .
  15. ↑ شيراكاوا، توشيهيرو (2025). "حصر البوليومينو حتى الحجم N=59". arXiv : 2510.22446 [ math.CO ].
  16. 1 2 ريدلماير، القسم 3
  17. ↑ ريدلماير، د. هيو (1981). "عدّ البوليومينو: هجوم آخر" . الرياضيات المتقطعة . 36 (2): 191-203 . doi : 10.1016/0012-365X(81)90237-5 .
  18. ↑ غولومب، الصفحات 73-79
  19. ↑ ريدلماير، القسم 4
  20. ↑ ريدلماير، القسم 6
  21. ↑ كونواي، أندرو (1995). "حصر متسلسلات الترشيح ثنائية الأبعاد باستخدام طريقة الشبكة المحدودة: النظرية". مجلة الفيزياء أ: الرياضية والعامة . 28 (2): 335-349 . Bibcode : 1995JPhA...28..335C . doi : 10.1088/0305-4470/28/2/011 . Zbl 0849.05003 . 
  22. ↑ جنسن، إيوان (2001). "إحصاء حيوانات وأشجار الشبكة". مجلة الفيزياء الإحصائية . 102 (1): 865-881 . arXiv : cond-mat/0007239 . Bibcode : 2001JSP...102..865J . doi : 10.1023/A:1004855020556 .
  23. ↑ جنسن، إيوان (2003). عدّ البوليومينو: تطبيق متوازٍ للحوسبة العنقودية . المؤتمر الدولي لعلوم الحاسوب (ICCS). الصفحات 203-212 . doi : 10.1007/3-540-44863-2_21 . 
  24. ↑ باريكيت، جيل؛ بن شاشار، جيل (2003). عدّ البوليومينو، إعادة نظر . ندوة هندسة الخوارزميات والتجارب (SIAM). ص 133-143 . arXiv : 2310.20632 . doi : 10.1137/1.9781611977929.1 . 
  25. ↑ جنسن، إيوان؛ غوتمان، أنتوني ج. (2000). "إحصاءات حيوانات الشبكة (البوليومينو) والمضلعات". مجلة الفيزياء أ: الرياضية والعامة . 33 (29): L257– L263. arXiv : cond-mat/0007238v1 . Bibcode : 2000JPhA...33L.257J . doi : 10.1088/0305-4470/33/29/102 . S2CID 6461687 . 
  26. ↑ باريكيت، جيل؛ روت، غونتر؛ شالاح، ميرا. "λ > 4: حد أدنى مُحسَّن لثابت نمو البوليومينو". اتصالات ACM . 59 (7): 88-95 . doi : 10.1145/2851485 .
  27. 1 2 باريكيت، جيل؛ شالاح، ميرا (2022). "تحسين الحدود العليا لثوابت نمو متعددات الأومينو ومتعددات المكعبات" . Algorithmica . 84 (12): 3559–3586 . arXiv : 1906.11447 . doi : 10.1007/s00453-022-00948-6 .
  28. ↑ كلارنر، د.أ.؛ ريفست، ر.ل. (1973). "إجراء لتحسين الحد الأعلى لعدد قطع الأومينو من الرتبة n " (ملف PDF) . المجلة الكندية للرياضيات . 25 (3): 585-602 . CiteSeerX 10.1.1.309.9151 . doi : 10.4153/CJM-1973-060-4 . S2CID 121448572. مؤرشف من النسخة الأصلية (ملف PDF لتقرير فني) بتاريخ 26-11-2006 . تم الاطلاع عليه بتاريخ 11-05-2007 .  
  29. ↑ ويلف، هربرت س. (1994). علم وظائف التوليد ( الطبعة الثانية). بوسطن، ماساتشوستس: دار النشر الأكاديمية. ص 151. ISBN   978-0-12-751956-2. Zbl 0831.05001 . 
  30. ↑ بوسكيه-ميلو، ميريل (1998). "نتائج تعدادية جديدة حول الحيوانات الموجهة ثنائية الأبعاد" . الرياضيات المتقطعة . 180 ( 1-3 ): 73-106 . doi : 10.1016/S0012-365X(97)00109-X .
  31. ↑ ديليست، م.-ب. (1988). "دوال توليد متعددة الأضلاع المحدبة عمودياً" . مجلة نظرية التوافيق، السلسلة أ . 48 (1): 12-31 . doi : 10.1016/0097-3165(88)90071-4 .
  32. ↑ بوسكيه-ميلو، ميريل ؛ فيدو، جان مارك (1995). "الدالة المولدة للمتعددات المحدبة: حل نظام تفاضلي من الرتبة q " . الرياضيات المتقطعة . 137 ( 1-3 ): 53-75 . doi : 10.1016/0012-365X(93)E0161-V .
  33. ^ بيكشيوتو ، هنري (1999)، مختبرات الهندسة ، MathEducationPage.org، ص. 208 .
  34. ↑ مارتن، جورج إي. (1996). البوليومينو: دليل للألغاز والمسائل في التبليط ( الطبعة الثانية). الجمعية الرياضية الأمريكية . ISBN  978-0-88385-501-0.
  35. ↑ سي بي هاسلجروف؛ جينيفر هاسلجروف (أكتوبر 1960). "برنامج حاسوبي لقطع البنتومينو" (ملف PDF) . يوريكا . 23 : 16-18 .
  36. ↑ غولومب، سولومون و. (1970). "التبليط بمجموعات من البوليومينو" . مجلة نظرية التوافيق . 9 : 60-71 . doi : 10.1016/S0021-9800(70)80055-2 .
  37. ↑ إي دي ديمين؛ إم إل ديمين (يونيو 2007). "ألغاز الصور المقطوعة، ومطابقة الحواف، وتعبئة البوليومينو: الروابط والتعقيد" . الرسوم البيانية والتوافقية . 23 : 195-208 . doi : 10.1007/s00373-007-0713-4 . S2CID 17190810 . 
  38. ↑ إس دبليو غولومب؛ إل دي بومرت (1965). "برمجة التراجع" . مجلة ACM . 12 (4): 516-524 . doi : 10.1145/321296.321300 .
  39. ↑ غارفي، ماركوس ر.؛ بوركاردت، جون (2020). "نموذج رياضي جديد لتبليط المناطق المحدودة من المستوى باستخدام متعددات المربعات" . مساهمات في الرياضيات المتقطعة . 15 (2): 95-131 . doi : 10.55016/ojs/cdm.v15i2.62866 .
  40. ↑ غارفي، ماركوس ر.؛ بوركاردت، جون (2022). "نهج برمجة خطية عددية متوازية لتبليط مناطق محدودة من المستوى باستخدام متعددات الأشكال" . الخوارزميات . 15 (5) 164. doi : 10.3390/a15050164 .
  41. ↑ غولومب، بوليومينو ، الفصل 8
  42. ↑ ريد، مايكل. "مراجع لبوليومينو قابلة للتصحيح" . مؤرشف من الأصل في 16 يناير 2004. تم الاطلاع عليه في 11 مايو 2007 .
  43. ↑ ريد، مايكل. "قائمة المستطيلات الأولية المعروفة لمختلف أشكال البوليومينو" . مؤرشف من الأصل بتاريخ 16 أبريل 2007. تم الاطلاع عليه بتاريخ 11 مايو 2007 .
  44. ^ كلارنر، دا. جوبل، ف. (1969). “صناديق التعبئة ذات الأشكال المتطابقة”. Indagationes Mathematicae . 31 : 465 - 472.
  45. ↑ كلارنر، ديفيد أ. (فبراير 1973). "إعادة النظر في نظرية الأساس المحدود" (ملف PDF) . تقرير فني من جامعة ستانفورد STAN-CS-73–338. مؤرشف من الأصل (ملف PDF) بتاريخ 23 أكتوبر 2007. تم الاطلاع عليه بتاريخ 12 مايو 2007 .
  46. ↑ كامينتسكي، ديمتري؛ كوك، تريستروم (2015). "تبليط المستطيلات باستخدام متعددات الأشكال المثقوبة". arXiv : 1411.2699 [ cs.CG ].
  47. ↑ غولومب، سولومون و. (1966). "التبليط باستخدام البوليومينو" . مجلة نظرية التوافيق . 1 (2): 280-296 . doi : 10.1016/S0021-9800(66)80033-9 .
  48. ↑ مور، كريستوفر ؛ روبسون، جون مايكل (2001). "مشاكل التبليط الصعبة مع البلاط البسيط" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 17-06-2013.
  49. ↑ بيترسن، إيفارز (25 سبتمبر 1999)، "رحلة رياضية: التبليط باستخدام البوليومينو" ، أخبار العلوم ، مؤرشف من الأصل في 20 مارس 2008 ، تم استرجاعه في 11 مارس 2012.
  50. ↑ غاردنر، مارتن (يوليو 1965). "حول العلاقة بين الرياضيات والأنماط المنظمة لفن الأوب". مجلة ساينتفك أمريكان . 213 (1): 100-104 . doi : 10.1038/scientificamerican1265-100 .
  51. ↑ غاردنر، مارتن (أغسطس 1965). "أفكار حول مهمة التواصل مع الكائنات الذكية في عوالم أخرى". مجلة ساينتفك أمريكان . 213 (2): 96-100 . doi : 10.1038/scientificamerican0865-96 .
  52. ↑ غاردنر، مارتن (أغسطس 1975). "المزيد حول تبليط المستوى: إمكانيات البوليومينو، والبولياموند، والبوليهيكس". مجلة ساينتفك أمريكان . 233 (2): 112-115 . doi : 10.1038/scientificamerican0875-112 .
  53. ↑ راوسترون، دانيال أ. (1988). "تعقيد تبليط قطع أومينو الصغيرة ( n < 10)" . الرياضيات المتقطعة . 70 : 71-75 . doi : 10.1016/0012-365X(88)90081-7 .
  54. ↑ رودز، جلين سي. (2003). التبليط المستوي والبحث عن بلاطة أولية غير دورية . أطروحة دكتوراه، جامعة روتجرز.
  55. ↑ غرونباوم وشيبارد، القسم 9.4
  56. ↑ كيتينغ، ك.؛ فينس، أ. (1999). "تبليط متعدد الأوجه متساوي الأوجه للمستوى" . الهندسة المنفصلة والحسابية . 21 (4): 615-630 . doi : 10.1007/PL00009442 .
  57. ↑ رودز، جلين سي. (2005). "التبليط المستوي بواسطة متعددات الأومينو، ومتعددات السداسيات، ومتعددات المعينات" . مجلة الرياضيات الحسابية والتطبيقية . 174 (2): 329-353 . Bibcode : 2005JCoAM.174..329R . doi : 10.1016/j.cam.2004.05.002 .
  58. ^ نيتشيتشا، فيوريل (2003). “إعادة النظر في بلاط الممثلين”. اختيار الشامل . بروفيدانس، RI: جمعية الرياضيات الأمريكية. ص 205 – 217. السيد 2027179 .  
  59. ^ ميريليس، جي إل، “Poly 2 ominoes”
  60. ^ “ريستا، ج.، “بوليبوليومينوس”تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 22 فبراير 2011. تم الاطلاع عليه بتاريخ 2 يوليو 2010 .
  61. ^ "زوكا، إل.، "بنتومينو الثلاثي""تم الاطلاع عليه بتاريخ 20 أبريل 2023 .
  62. ↑ باربانز، أولديس؛ سيبوليس، أندريس؛ لي، جيلبرت؛ ليو، آندي؛ واينرايت، روبرت (2005). "نظرية أعداد البوليومينو (3)". في: سيبرا، باري آرثر ؛ ديمين، إريك د.؛ ديمين، مارتن ل.؛ رودجرز، توم (محررون). تكريم لساحر رياضيات . ويليسلي، ماساتشوستس: إيه كيه بيترز. ص 131-136 . ISBN  978-1-56881-204-5.
  63. ↑ غولومب، سولومون و. (7 أبريل 1996). البوليومينو: ألغاز، أنماط، مسائل، وتعبئة . مطبعة جامعة برينستون. ص 8. ISBN  978-0-691-02444-8.
  64. ↑ إتزيون، توفي (28-12-2020)، "ألغاز وبلاط ؟ مملكة سليمان غولومب الرائعة" ، حكمة سليمان ، وورلد ساينتيفيك، ص 145-160 ، doi : 10.1142/9789811234378_0013 ، ISBN   978-981-12-3436-1تم الاطلاع عليه بتاريخ 21 ديسمبر 2025
  65. ↑ قاموس أكسفورد الإنجليزي ، الطبعة الثانية، مدخل دومينو