يحتوي لغز 9 X9 SUDOKU على القواعد التالية. يجب أن يحتوي كل صف وعمود على الأرقام بين 1 و 9 ويجب أن يحتوي كل مربع داخلي على الأرقام بين 1 و 9. يجب أن يظهر كل رقم في كل عمود وصف وفي كل مربع صغير مرة واحدة فقط.
دعنا فقط نحدد Xijk لجميع قيم I و j و k من 1 إلى 9 لتكون 1. إذا كانت الخلية (I ، j) تحتوي على الرقم k حيث I و j و k كلها تتراوح بين 1 و 9. هنا أشير يشير الصف ith و j إلى العمود j ويشير k إلى عدد صحيح بين 1 و 9. عندما يكون X134 = 1 ، فهذا يعني أن الخلية (1،3) تحتوي على الرقم 4. وهذا يعني أيضًا أنه لا يوجد عنصر من العناصر الأخرى في الصف الأول أو العمود الثالث باستثناء الخلية (1،3) يمكن أن تكون مساوية لـ 4.
من أجل تصميم SUDOKU ، سنستخدم ما مجموعه 729 متغيرًا.
دعونا الآن نصوغ جبريًا كل فئة من فئات القواعد الثلاثة.
يجب أن يحتوي كل صف على رقم بين 1 و 9 مرة واحدة فقط.
بالنسبة للصف الأول ، ستظهر هذه القاعدة على أنها (تسمى “قيد” في لغة البرمجة الصحيحة).
لكل أنا من 1 إلى 9 ولكل ك من 1 إلى 9 (أنا تمثيل رياضي لمتغير مضاد)
مجموع (Xijk) لجميع j من 1 إلى 9 = 1 ؛
مكتوب بشكل مطول للصف الأول لكل رقم بين 1 و 9
X111 + X121 + X131 + X141 + X151 + X161 + X171 + X181 + X191 = 1.
X112 + X122 + X132 + X142 + X152 + X162 + X172 + X182 + X192 = 1.
X113 + X123 + X133 + X143 + X153 + X163 + X173 + X183 + X193 = 1.
X114 + X124 + X134 + X144 + X154 + X164 + X174 + X184 + X194 = 1.
تتبع هذه المعادلات للمتغيرات التي تبدأ من X115 إلى X119.
على نحو مماثل ، دعونا نصيغ معادلات لقواعد كل رقم بين 1 و 9 تحدث مرة واحدة فقط في كل من الأعمدة التسعة.
مكتوبة في تدوين رياضي ،
مجموع X لكل j من 1 إلى 9 (لكل I و k بين 1 إلى 9) = 1
مكتوبًا بشكل مطول لعدة أعمدة لكل رقم بين 1 و 9
العمود 1
X111 + X211 + X311 + X411 + X511 + X611 + X711 + X811 + X911 = 1.
X112 + X212 + X312 + X412 + X512 + X612 + X712 + X812 + X912 = 1.
X113 + X213 + X313 + X413 + X513 + X613 + X713 + X813 + X913 = 1.
يجب ملء هذا لجميع الأرقام الأخرى من 4 إلى 9.
العمود 2
X121 + X221 + X321 + X421 + X521 + X621 + X721 + X821 + X921 = 1.
X122 + X222 + X322 + X422 + X522 + X622 + X722 + X822 + X922 = 1.
X123 + X223 + X323 + X423 + X523 + X623 + X723 + X823 + X923 = 1.
يجب ملء هذا لجميع الأرقام الأخرى من 4 إلى 9.
دعونا الآن نمثل المربعات الصغيرة (3 × 3) 9 مربعات في العدد.
لذلك في كل مربع 3 × 3 ، يجب أن يكون هناك واحد فقط أو 2 أو 3 أو 4 أو 5 أو 6 أو 7 أو 8 أو 9 وما إلى ذلك ،
تحدث الخلايا بين الأعمدة (من 1 إلى 3) والصفوف (من 1 إلى 3) والأعمدة (من 4 إلى 6) والصفوف (من 1 إلى 3) والأعمدة (من 7 إلى 9) صفوف (من 1 إلى 3). أيضًا لنفس مجموعة الأعمدة تحدث في الصفوف (4 إلى 6) و (6 إلى 9). لذلك دعونا نصيغ المعادلات لمربع صغير واحد فقط يقع بين الأعمدة (من 1 إلى 3) والصفوف (من 1 إلى 3). متغيرات القرار المقابلة للرقم “1” هي (9 في المجموع)
X111 ، X121 ، X131 ، X211 ، X221 ، X231 ، X311 ، X321 ، X331.
دعونا نصيغ المعادلة القائلة بأن هذا المربع (3 × 3) يحتوي على “1” واحد فقط.
إذن المعادلة
X111 + X121 + X131 + X211 + X221 + X231 + X311 + X321 + X331 = 1.
تشير المعادلة أعلاه إلى أن واحدًا فقط من هذه المتغيرات التسعة أو واحدة فقط من هذه الخلايا التسعة يمكن أن تأخذ القيمة 1.
وبالمثل يجب صياغة قيود للرقم “2” والرقم “3” وهكذا حتى 9.
بالنسبة لمشاكل برمجة الأعداد الصحيحة بالإضافة إلى المعادلات التي تصف القيود ، يجب أيضًا أن تكون هناك قيود صحيحة مفروضة على كل متغير بحيث في النهاية عندما يتم حل نظام المعادلات ، يحصل المرء إما على 0 أو 1 كحل للمتغير Xijk .
المعادل الهندسي لمشكلة البرمجة الخطية مع دالة موضوعية وبعض القيود ليس سوى متعدد السطوح الأبعاد حيث يمثل n عدد القيود في المشكلة. عادةً ما يتم العثور على الحل الأمثل في رؤوس polytope ، كما تتطلب قواعد بعض الطرق مثل SIMPLEX أن يكون polytope محدبًا بحيث يمكن للمرء الانتقال من قمة إلى قمة على طول الحواف ومعرفة الحل الأمثل.
إن فرض قيود عدد صحيح بالإضافة إلى ذلك يعني أن الحل الأمثل لن يكون على رؤوس polytope لأن الحل الموجود على الرأس قد لا يكون عددًا صحيحًا. لذلك ، بعد الأخذ في الاعتبار أن الحل الأمثل يجب أن يكون 0 أو 1 سيعني أن الحل هندسيًا سيكون في مكان ما داخل المنطقة المجدية من polytope المحدب وعلى أحد الخطوط المستقيمة العديدة الناشئة من المستوى الفائق المكافئ لـ Xi jk الذي يحتوي على عدد صحيح القيم.
لاحظ أن الحل أعلاه استخدم 729 متغير قرار و 81 صفًا قيودًا. 81 عمودًا من القيود و 729 قيودًا للمربعات الصغيرة بإجمالي 901 قيودًا. يمكن أن يكون هناك العديد من الوظائف الموضوعية ، ولكن يمكن للمرء أن يصوغ دالة موضوعية مثل إيجاد الحد الأدنى (مجموع جميع المتغيرات الـ 729). يمكن للمرء أن يقلل من عدد القيود من خلال إيجاد بعض التكرار.
لا يمكن حل هذه المعادلات أعلاه باستخدام لغات البرمجة مثل Visual Basic أو Pascal أو C. يمكن حل مشاكل البرمجة الصحيحة باستخدام برامج التحسين مثل CPLEX optimizer و Excel addin لحل مشاكل البرمجة الخطية و Lingo وما إلى ذلك.
