رياضيات سودوكو
المحتويات

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