رياضيات سودوكو

رياضيات سودوكو

تتكون فئة الألغاز في سودوكو من شبكة جزئية مكتملة جزئياً من الخلايا المنقسمة إلى مناطق N لكل حجم من الخلايا N ، ليتم تعبئتها («محلولة») باستخدام مجموعة محددة من الرموز المتميزة N (عادة ما تكون الأرقام {1... N})، بحيث يحتوي كل صف وعمود ومنطقة على واحد بالضبط من كل عنصر في المجموعة. ويمكن دراسة خصائص الألغاز سودوكو وحلولها باستخدام الرياضيات وخوارزميات الكمبيوتر. نظرة عامة ينقسم تحليل سودوكو إلى مجالين رئيسيين: تحليل خصائص (1) الشبكات المكتملة و (2) الألغاز. درست أيضا خوارزميات الكمبيوتر لحل سودوكوس، وتطوير (أو البحث عن) سودوكوس جديد. ركز التحليل إلى حد كبير على تعداد الحلول، مع ظهور النتائج لأول مرة في عام 2004. [1] هناك العديد من المتغيرات سودوكو، تتميز جزئيا بالحجم (N)، وشكل مناطقها. ما لم يلاحظ، تفترض المناقشة في هذه المقالة سودوكو الكلاسيكية، أي N = 9 (شبكة 9 × 9 ومناطق 3 × 3). يستخدم مستطيل سودوكو مناطق مستطيلة ذات أعمدة صف صف R × C. تتضمن الأنواع الأخرى تلك ذات المناطق غير المنتظمة أو مع قيود إضافية (hypercube) أو أنواع قيود مختلفة (Samunamupure). اللغز هو شبكة مكتملة جزئياً، والقيم الأولية هي معطيات أو خيوط. تسمى المناطق أيضًا كتل أو مربعات. تعد الصفوف المتجاورة أفقيًا شريطًا، والأعمدة المجاورة عموديًا عبارة عن مجموعة مكدسة. لغز الصحيح لديه حل فريد من نوعه. انظر معجم سودوكو للمصطلحات الأخرى. [2] وقد تم استكشاف حل سودوكو من وجهة نظر لاعب في كتاب دينيس بيرتيير "The Hidden Logic of Sudoku" (2007) [3] الذي يدرس استراتيجيات مثل "xy-chains".

السياق الرياضي من المعروف أن المشكلة العامة لحل الألغاز سودوكو على شبكات n2 × n2 من كتل n * n تكون NP- كاملة. [4] ومع ذلك، بالنسبة إلى n = 3 (Sudoku الكلاسيكي)، تكون هذه النتيجة قليلة الصلة: فالخوارزميات مثل Dancing Links يمكنها حل الألغاز في أجزاء من الثانية.

يمكن التعبير عن اللغز كمشكلة تلوين الرسم البياني. [5] والهدف هو بناء 9 تلوين من رسم بياني معين، نظرا ل 9 صبغة جزئية. يحتوي الرسم البياني على 81 رأسًا، قمة رأس لكل خلية. يتم وسم القمم بأزواج مرتبة (x، y)، حيث x و y عبارة عن عدد صحيح بين 1 و 9. في هذه الحالة، يتم ضم قمتين مميزتين مصنفين بواسطة (x، y) و (x ′، y ′) بواسطة حافة إذا وفقط إذا:

x = x ′ (نفس العمود) أو y = y ′ (نفس الصف) أو ⌈ x / 3 ⌉ = ⌈ x ′ / 3 ⌉ و ⌈ y / 3 ⌉ = ⌈ y ′ / 3 ⌉ (نفس الخلية 3 × 3) ثم يتم إكمال اللغز عن طريق تعيين عدد صحيح بين 1 و 9 لكل قمة، وبهذه الطريقة لا تحتوي الرؤوس المرتبطة بحافة على نفس العدد الصحيح المخصص لها.

شبكة حل سودوكو هي أيضا ساحة لاتينية. [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 سودوكو غير معروف.

لا يعرف عدد الحد الأدنى من سودوكو على وجه التحديد (سودوكو حيث لا يمكن حذف أي فكرة دون فقدان الحل). ومع ذلك، تظهر التقنيات الإحصائية مقترنة بمولد («إحصائيات غير متحيزة لـ CSP - A-Control-Bias Generator»)، [8] أن هناك تقريبًا (مع خطأ نسبي 0.065٪):

3.10 × 1037 الألغاز الدنيا، 2.55 × 1025 الألغاز الدنيا غير المكافئة بشكل أساسي. استخدم مؤلفون آخرون أساليب أسرع وحسبوا إحصائيات توزيع دقيقة إضافية. [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}} _ 3 !). وهكذا وصلنا إلى سودوكو (إعادة تسمية الأزواج إلى أرقام 1 ... 9 إذا كنت ترغب). مع المثال وتقليب الصف أعلاه، نصل إلى الشبكة 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 (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) لكي تعمل هذه الطريقة، لا يحتاج المرء بشكل عام إلى منتج من مجموعتين متساويتين الحجم. ما يسمى بالتتابع الدقيق القصير للمجموعات المحدودة ذات الحجم المناسب يقوم بالفعل بهذه المهمة. جرب على سبيل المثال المجموعة {\ displaystyle \ mathbb {Z} _ {4}} {\ mathbb {Z}} _ قالب:4 مع quient- وزمرة جزئية {\ displaystyle \ mathbb {Z} _ {2}} \ mathbb {Z} _ {2}. يبدو واضحا (بالفعل من حجج التعداد)، أنه ليس كل سودوكو يمكن أن يتولد بهذه الطريقة.

تعداد حلول سودوكو الجواب على السؤال «كم عدد شبكات سودوكو هناك؟» يعتمد على تعريف عندما تعتبر حلول مماثلة مختلفة.

تعداد كل الحلول الممكنة سودوكو بالنسبة إلى تعداد جميع الحلول الممكنة، يُعتبر حلان مختلفان إذا اختلفت قيمهما المقابلة (81) خلية. يتم تجاهل العلاقات التماثلية بين الحلول المشابهة، على سبيل المثال، تعتبر الدورات من الحل متميزة. تلعب التماثلات دورًا مهمًا في إستراتيجية التعداد، ولكن ليس في حساب جميع الحلول الممكنة.

تم نشر أول حل معروف لإكمال التعداد بواسطة QSCGZ إلى مجموعة الأخبار rec.puzzles في عام 2003، [6] [10] [11] الحصول على 6,670,903,752,021,072,936,960 (6.67 × 1021) حلول متميزة.

في دراسة أجريت عام 2005، حلل Felgenhauer و Jarvis [12] تباديل النطاق الأعلى المستخدم في حلول صالحة. وبمجرد التعرف على تماثيل Band1 وفئات التكافؤ الخاصة بحلول الشبكة الجزئية، تم بناء إتمام النقطتين السفليتين وحسابهما لكل فئة من فئات التكافؤ. إن الجمع بين الإكمالات حول فصول التكافؤ، التي يتم ترجيحها حسب حجم الفصل، يعطي العدد الإجمالي للحلول 6,670,903,752,021,072,936,960، مما يؤكد القيمة التي حصلت عليها QSCGZ. تم تأكيد القيمة لاحقًا عدة مرات بشكل مستقل. تم تطوير تقنية تعداد ثانية تعتمد على توليد النطاق في وقت لاحق والتي تكون أقل بكثير بكثير من الحوسبة.

تعداد حلول سودوكو مختلفة جوهريا هناك نوعان من الشبكات الصالحة هي نفسها إذا كان يمكن اشتقاق أحدهما من الآخر. العمليات التالية هي سودوكو الحفاظ على التماثلات ودائما ترجمة شبكة صالحة في شبكة أخرى صالحة:

رموز إعادة التسمية (9!) تباديل الفرقة (3!) تباديل الصفوف داخل نطاق (3! 3) التباديل التكديس (3!) تباديل العمود داخل كومة (3! 3) انعكاس، تبديل وتناوب (2). (بالنظر إلى أي تبديل أو دوران ربع سنوي بالتزامن مع التباديل أعلاه، يمكن إنتاج أي توليفة من الانعكاسات والانتقال والتناوب، وبالتالي فإن هذه العمليات تساهم فقط في عامل 2.)

تحدد هذه العمليات علاقة التماثل بين الشبكات المكافئة. باستثناء عمليات إعادة التسمية، وفيما يتعلق بقيم خلية الشبكة 81، فإن العمليات تشكل مجموعة فرعية من المجموعة المتماثلة S81 ، من الترتيب 3! 8 × 2 = 3,359,232. تطبيق العمليات المذكورة أعلاه على غالبية نتائج الشبكات في 3! 8 × 2 × 9! شبكات مكافئة في الأساس. الاستثناءات هي Automorphic Sudokus التي تنتج عن تناظر إضافي غير تافه توليد شبكات أقل.

يمكن أيضًا تحديد عدد الحلول المتميزة باستخدام Lema. بالنسبة للحل، تشكل مجموعة الحلول المكافئة التي يمكن الوصول إليها باستخدام هذه العمليات (باستثناء إعادة التسمية)، مدارًا للمجموعة المتماثلة. عدد الحلول المختلفة في الأساس هو عدد المدارات التي يمكن حسابها باستخدام lemma في Burnside. النقاط الثابتة Burnside هي الحلول التي تختلف فقط عن طريق إعادة التسمية. باستخدام هذه التقنية، قام جارفيس / راسل [7] بحساب عدد الحلول المختلفة (المتميزة تناسقًا) بشكل أساسي مثل 5,472,730,538.

نتائج التعداد تم حساب نتائج التعداد للعديد من المتغيرات في سودوكو: تم تلخيصها أدناه.