
_START_ARTICLE_
رياضيات سودوكو
_START_PARAGRAPH_
رياضيات سودوكو_NEWLINE_تتكون فئة الألغاز في سودوكو من شبكة جزئية مكتملة جزئياً من الخلايا المنقسمة إلى مناطق N لكل حجم من الخلايا N ، ليتم تعبئتها ("محلولة") باستخدام مجموعة محددة من الرموز المتميزة N (عادة ما تكون الأرقام {1 ، ... ، N}) ، بحيث يحتوي كل صف وعمود ومنطقة على واحد بالضبط من كل عنصر في المجموعة. ويمكن دراسة خصائص الألغاز سودوكو وحلولها باستخدام الرياضيات وخوارزميات الكمبيوتر._NEWLINE_نظرة عامة_NEWLINE_ينقسم تحليل سودوكو إلى مجالين رئيسيين: تحليل خصائص (1) الشبكات المكتملة و (2) الألغاز. درست أيضا خوارزميات الكمبيوتر لحل سودوكوس ، وتطوير (أو البحث عن) سودوكوس جديد. ركز التحليل إلى حد كبير على تعداد الحلول ، مع ظهور النتائج لأول مرة في عام 2004. [1] هناك العديد من المتغيرات سودوكو ، تتميز جزئيا بالحجم (N) ، وشكل مناطقها. ما لم يلاحظ ، تفترض المناقشة في هذه المقالة سودوكو الكلاسيكية ، أي N = 9 (شبكة 9 × 9 ومناطق 3 × 3). يستخدم مستطيل سودوكو مناطق مستطيلة ذات أعمدة صف صف R × C. تتضمن الأنواع الأخرى تلك ذات المناطق غير المنتظمة أو مع قيود إضافية (hypercube) أو أنواع قيود مختلفة (Samunamupure)._NEWLINE_اللغز هو شبكة مكتملة جزئياً ، والقيم الأولية هي معطيات أو خيوط. تسمى المناطق أيضًا كتل أو مربعات. تعد الصفوف المتجاورة أفقيًا شريطًا ، والأعمدة المجاورة عموديًا عبارة عن مجموعة مكدسة. لغز الصحيح لديه حل فريد من نوعه. انظر معجم سودوكو للمصطلحات الأخرى. [2] وقد تم استكشاف حل سودوكو من وجهة نظر لاعب في كتاب دينيس بيرتيير "The Hidden Logic of Sudoku" (2007) [3] الذي يدرس استراتيجيات مثل "xy-chains"._NEWLINE_السياق الرياضي_NEWLINE_من المعروف أن المشكلة العامة لحل الألغاز سودوكو على شبكات n2 × n2 من كتل n * n تكون NP- كاملة. [4] ومع ذلك ، بالنسبة إلى n = 3 (Sudoku الكلاسيكي) ، تكون هذه النتيجة قليلة الصلة: فالخوارزميات مثل Dancing Links يمكنها حل الألغاز في أجزاء من الثانية._NEWLINE_يمكن التعبير عن اللغز كمشكلة تلوين الرسم البياني. [5] والهدف هو بناء 9 تلوين من رسم بياني معين ، نظرا ل 9 صبغة جزئية. يحتوي الرسم البياني على 81 رأسًا ، قمة رأس لكل خلية. يتم وسم القمم بأزواج مرتبة (x، y) ، حيث x و y عبارة عن عدد صحيح بين 1 و 9. في هذه الحالة ، يتم ضم قمتين مميزتين مصنفين بواسطة (x، y) و (x ′، y ′) بواسطة حافة إذا وفقط إذا:_NEWLINE_x = x ′ (نفس العمود) أو_NEWLINE_y = y ′ (نفس الصف) أو_NEWLINE_⌈ x / 3 ⌉ = ⌈ x ′ / 3 ⌉ و ⌈ y / 3 ⌉ = ⌈ y ′ / 3 ⌉ (نفس الخلية 3 × 3)_NEWLINE_ثم يتم إكمال اللغز عن طريق تعيين عدد صحيح بين 1 و 9 لكل قمة ، وبهذه الطريقة لا تحتوي الرؤوس المرتبطة بحافة على نفس العدد الصحيح المخصص لها._NEWLINE_شبكة حل سودوكو هي أيضا ساحة لاتينية. [5] هناك عدد أقل بكثير من شبكات سودوكو من المربعات اللاتينية لأن سودوكو يفرض قيودًا إقليمية إضافية. ومع ذلك ، فقد تم حساب عدد شبكات سودوكو بواسطة بيرترام فيلغينهاير و فريزر جارفيس في عام 2005 ليكون 6،670،903،752،021،072،936،960 [6] (التسلسل A107739 في OEIS). وأكد الرقم الذي تم حسابه من قبل Felgenhauer and Jarvis نتيجة تم تحديدها لأول مرة بواسطة QSCGZ في سبتمبر 2003. [6] هذا الرقم يساوي 9! × 722 × 27 × 27،704،267،971 ، وآخر عامل منها رئيس. وقد استمدت النتيجة من خلال حساب القوة المنطقية والوحشية. أظهر راسل و جارفيس أيضا أنه عندما تم أخذ التماثلات في الاعتبار ، كان هناك 5،472،730،538 حلولا [7] (تسلسل A109741 في OEIS). عدد الشبكات لمدة 16 × 16 سودوكو غير معروف._NEWLINE_لا يعرف عدد الحد الأدنى من سودوكو على وجه التحديد (سودوكو حيث لا يمكن حذف أي فكرة دون فقدان الحل). ومع ذلك ، تظهر التقنيات الإحصائية مقترنة بمولد ("إحصائيات غير متحيزة لـ CSP - A-Control-Bias Generator") ، [8] أن هناك تقريبًا (مع خطأ نسبي 0.065٪):_NEWLINE_3.10 × 1037 الألغاز الدنيا ،_NEWLINE_2.55 × 1025 الألغاز الدنيا غير المكافئة بشكل أساسي._NEWLINE_استخدم مؤلفون آخرون أساليب أسرع وحسبوا إحصائيات توزيع دقيقة إضافية. [9]_NEWLINE_الآن ، لإعطاء سودوكو ، دعونا نحيد الصفوف (أو مكافئ للأعمدة) بهذه الطريقة ، أن كل كتلة يعاد توزيعها مرة واحدة بالضبط في كل كتلة - على سبيل المثال أمرهم {\ displaystyle 1،4،7،2،5 ، 8،3،6،9} 1،4،7،2،5،8،3،6،9. هذا بالطبع يحافظ على خاصية مربع اللاتينية. علاوة على ذلك ، في كل كتلة ، يكون للخطوط المكون الأول المتميز بالبناء وكل سطر في كتلة له مداخل مميزة عن طريق المكون الثاني ، لأن المكونات الثانية للكتل شكلت في الأصل مربعًا لاتينيًا للترتيب {\ displaystyle 3} 3 (من المجموعة الفرعية {\ displaystyle \ mathbb {Z} _ {3}} {\ mathbb {Z}} _ ). وهكذا وصلنا إلى سودوكو (إعادة تسمية الأزواج إلى أرقام 1 ... 9 إذا كنت ترغب). مع المثال وتقليب الصف أعلاه ، نصل إلى الشبكة 2_NEWLINE_Grid 1 - The addition table in_NEWLINE_(0,0)(0,1)(0,2)_NEWLINE_(0,1)(0,2)(0,0)_NEWLINE_(0,2)(0,0)(0,1)_NEWLINE_(1,0)(1,1)(1,2)_NEWLINE_(1,1)(1,2)(1,0)_NEWLINE_(1,2)(1,0)(1,1)_NEWLINE_(2,0)(2,1)(2,2)_NEWLINE_(2,1)(2,2)(2,0)_NEWLINE_(2,2)(2,0)(2,1)_NEWLINE_(1,0)(1,1)(1,2)_NEWLINE_(1,1)(1,2)(1,0)_NEWLINE_(1,2)(1,0)(1,1)_NEWLINE_(2,0)(2,1)(2,2)_NEWLINE_(2,1)(2,2)(2,0)_NEWLINE_(2,2)(2,0)(2,1)_NEWLINE_(0,0)(0,1)(0,2)_NEWLINE_(0,1)(0,2)(0,0)_NEWLINE_(0,2)(0,0)(0,1)_NEWLINE_(2,0)(2,1)(2,2)_NEWLINE_(2,1)(2,2)(2,0)_NEWLINE_(2,2)(2,0)(2,1)_NEWLINE_(0,0)(0,1)(0,2)_NEWLINE_(0,1)(0,2)(0,0)_NEWLINE_(0,2)(0,0)(0,1)_NEWLINE_(1,0)(1,1)(1,2)_NEWLINE_(1,1)(1,2)(1,0)_NEWLINE_(1,2)(1,0)(1,1)_NEWLINE_Grid 2 - Generating a Sudoku_NEWLINE_(0,0)(0,1)(0,2)_NEWLINE_(1,0)(1,1)(1,2)_NEWLINE_(2,0)(2,1)(2,2)_NEWLINE_(1,0)(1,1)(1,2)_NEWLINE_(2,0)(2,1)(2,2)_NEWLINE_(0,0)(0,1)(0,2)_NEWLINE_(2,0)(2,1)(2,2)_NEWLINE_(0,0)(0,1)(0,2)_NEWLINE_(1,0)(1,1)(1,2)_NEWLINE_(0,1)(0,2)(0,0)_NEWLINE_(1,1)(1,2)(1,0)_NEWLINE_(2,1)(2,2)(2,0)_NEWLINE_(1,1)(1,2)(1,0)_NEWLINE_(2,1)(2,2)(2,0)_NEWLINE_(0,1)(0,2)(0,0)_NEWLINE_(2,1)(2,2)(2,0)_NEWLINE_(0,1)(0,2)(0,0)_NEWLINE_(1,1)(1,2)(1,0)_NEWLINE_(0,2)(0,0)(0,1)_NEWLINE_(1,2)(1,0)(1,1)_NEWLINE_(2,2)(2,0)(2,1)_NEWLINE_(1,2)(1,0)(1,1)_NEWLINE_(2,2)(2,0)(2,1)_NEWLINE_(0,2)(0,0)(0,1)_NEWLINE_(2,2)(2,0)(2,1)_NEWLINE_(0,2)(0,0)(0,1)_NEWLINE_(1,2)(1,0)(1,1)_NEWLINE_لكي تعمل هذه الطريقة ، لا يحتاج المرء بشكل عام إلى منتج من مجموعتين متساويتين الحجم. ما يسمى بالتتابع الدقيق القصير للمجموعات المحدودة ذات الحجم المناسب يقوم بالفعل بهذه المهمة. جرب على سبيل المثال المجموعة {\ displaystyle \ mathbb {Z} _ {4}} {\ mathbb {Z}} _  مع quient- و subgroup {\ displaystyle \ mathbb {Z} _ {2}} \ mathbb {Z} _ {2}. يبدو واضحا (بالفعل من حجج التعداد) ، أنه ليس كل سودوكو يمكن أن يتولد بهذه الطريقة._NEWLINE_تعداد حلول سودوكو_NEWLINE_الجواب على السؤال "كم عدد شبكات سودوكو هناك؟" يعتمد على تعريف عندما تعتبر حلول مماثلة مختلفة._NEWLINE_تعداد كل الحلول الممكنة سودوكو_NEWLINE_بالنسبة إلى تعداد جميع الحلول الممكنة ، يُعتبر حلان مختلفان إذا اختلفت قيمهما المقابلة (81) خلية. يتم تجاهل العلاقات التماثلية بين الحلول المشابهة ، على سبيل المثال ، تعتبر الدورات من الحل متميزة. تلعب التماثلات دورًا مهمًا في استراتيجية التعداد ، ولكن ليس في حساب جميع الحلول الممكنة._NEWLINE_تم نشر أول حل معروف لإكمال التعداد بواسطة QSCGZ إلى مجموعة الأخبار rec.puzzles في عام 2003 ، [6] [10] [11] الحصول على 6،670،903،752،021،072،936،960 (6.67 × 1021) حلول متميزة._NEWLINE_في دراسة أجريت عام 2005 ، حلل Felgenhauer و Jarvis [12] تباديل النطاق الأعلى المستخدم في حلول صالحة. وبمجرد التعرف على تماثيل Band1 وفئات التكافؤ الخاصة بحلول الشبكة الجزئية ، تم بناء إتمام النقطتين السفليتين وحسابهما لكل فئة من فئات التكافؤ. إن الجمع بين الإكمالات حول فصول التكافؤ ، التي يتم ترجيحها حسب حجم الفصل ، يعطي العدد الإجمالي للحلول 6،670،903،752،021،072،936،960 ، مما يؤكد القيمة التي حصلت عليها QSCGZ. تم تأكيد القيمة لاحقًا عدة مرات بشكل مستقل. تم تطوير تقنية تعداد ثانية تعتمد على توليد النطاق في وقت لاحق والتي تكون أقل بكثير بكثير من الحوسبة._NEWLINE_تعداد حلول سودوكو مختلفة جوهريا_NEWLINE_هناك نوعان من الشبكات الصالحة هي نفسها إذا كان يمكن اشتقاق أحدهما من الآخر. العمليات التالية هي سودوكو الحفاظ على التماثلات ودائما ترجمة شبكة صالحة في شبكة أخرى صالحة:_NEWLINE_رموز إعادة التسمية (9!)_NEWLINE_تباديل الفرقة (3!)_NEWLINE_تباديل الصفوف داخل نطاق (3! 3)_NEWLINE_التباديل التكديس (3!)_NEWLINE_تباديل العمود داخل كومة (3! 3)_NEWLINE_انعكاس ، تبديل وتناوب (2). (بالنظر إلى أي تبديل أو دوران ربع سنوي بالتزامن مع التباديل أعلاه ، يمكن إنتاج أي توليفة من الانعكاسات والانتقال والتناوب ، وبالتالي فإن هذه العمليات تساهم فقط في عامل 2.)_NEWLINE_تحدد هذه العمليات علاقة التماثل بين الشبكات المكافئة. باستثناء عمليات إعادة التسمية ، وفيما يتعلق بقيم خلية الشبكة 81 ، فإن العمليات تشكل مجموعة فرعية من المجموعة المتماثلة S81 ، من الترتيب 3! 8 × 2 = 3،359،232. تطبيق العمليات المذكورة أعلاه على غالبية نتائج الشبكات في 3! 8 × 2 × 9! شبكات مكافئة في الأساس. الاستثناءات هي Automorphic Sudokus التي تنتج عن تناظر إضافي غير تافه توليد شبكات أقل._NEWLINE_يمكن أيضًا تحديد عدد الحلول المتميزة باستخدام Lema. بالنسبة للحل ، تشكل مجموعة الحلول المكافئة التي يمكن الوصول إليها باستخدام هذه العمليات (باستثناء إعادة التسمية) ، مدارًا للمجموعة المتماثلة. عدد الحلول المختلفة في الأساس هو عدد المدارات التي يمكن حسابها باستخدام lemma في Burnside. النقاط الثابتة Burnside هي الحلول التي تختلف فقط عن طريق إعادة التسمية. باستخدام هذه التقنية ، قام جارفيس / راسل [7] بحساب عدد الحلول المختلفة (المتميزة تناسقًا) بشكل أساسي مثل 5،472،730،538._NEWLINE_نتائج التعداد_NEWLINE_تم حساب نتائج التعداد للعديد من المتغيرات في سودوكو: تم تلخيصها أدناه.