تضامنًا مع حق الشعب الفلسطيني |
رياضيات سودوكو
![](https://upload.wikimedia.org/wikipedia/commons/thumb/b/b9/Sudoku00.png/200px-Sudoku00.png)
[1] رياضيات سودوكو
تتكون فئة الألغاز في سودوكو من شبكة جزئية مكتملة جزئياً من الخلايا المنقسمة إلى مناطق 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}} _ ). وهكذا وصلنا إلى سودوكو (إعادة تسمية الأزواج إلى أرقام 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.
نتائج التعداد تم حساب نتائج التعداد للعديد من المتغيرات في سودوكو: تم تلخيصها أدناه.
مراجع
- ^ 1. Lin, Keh Ying (2004), "Number Of Sudokus", Journal of Recreational Mathematics, 33 (2): 120–24. 2. ^ Jump up to:a b "Basic terms : About the New Sudoku Players' Forum". Forum.enjoysudoku.com. 16 May 2006. Retrieved 20 October 2013. 3. Jump up^ Berthier, Denis (November 2007). The Hidden Logic of Sudoku (Second, revised and extended ed.). Lulu.com. ISBN 978-1-84799-214-7. Retrieved 2017-11-21. 4. Jump up^ "NP complete – Sudoku" (PDF). Imai.is.su-tokyo.ac.jp. Retrieved 20 October 2013. 5. ^ Jump up to:a b Lewis, R. A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers, 2015. 6. ^ Jump up to:a b c d "Sudoku enumeration problems". Afjarvis.staff.shef.ac.uk. Retrieved 20 October2013. 7. ^ Jump up to:a b c d "Sudoku enumeration: the symmetry group". Afjarvis.staff.shef.ac.uk. 7 September 2005. Retrieved 20 October 2013. 8. Jump up^ Berthier, Denis (4 December 2009). "Unbiased Statistics of a CSP – A Controlled-Bias Generator". Retrieved 4 December 2009. 9. Jump up^ "Counting minimal puzzles: subsets, supersets, etc". Forum.enjoysudoku.com. 2013-06-11. Retrieved 2017-04-18. 10. Jump up^ "Google Discussiegroepen". Groups.google.com. Retrieved 2013-10-20. 11. Jump up^ "6670903752021072936960 is old hat : General". Forum.enjoysudoku.com. Retrieved 2013-10-20. 12. ^ Jump up to:a b c d Felgenhauer, Bertram; Jarvis, Frazer (June 20, 2005), Enumerating possible Sudoku grids (PDF). 13. ^ Jump up to:a b "Su-Doku's maths : General - Page 36". Forum.enjoysudoku.com. Retrieved 2013-10-20. 14. ^ Jump up to:a b Sloane, N.J.A. (ed.). "Sequence A107739 (Number of (completed) sudokus (or Sudokus) of size n^2 X n^2)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. Retrieved 14 April 2017. 15. Jump up^ "Sudoku maths - can mortals work it out for the 2x2 square ? : General". Forum.enjoysudoku.com. Retrieved 2013-10-20. 16. ^ Jump up to:a b c "Su-Doku's maths : General - Page 28". Forum.enjoysudoku.com. Retrieved 2013-10-20. 17. Jump up^ "Su-Doku's maths : General - Page 29". Forum.enjoysudoku.com. Retrieved 2013-10-20. 18. Jump up^ "Su-Doku's maths : General - Page 29". Forum.enjoysudoku.com. Retrieved 2013-10-20. 19. Jump up^ "6x2 counting : General". Forum.enjoysudoku.com. Retrieved 2013-10-20. 20. Jump up^ "4x3 Sudoku counting : General - Page 2". Forum.enjoysudoku.com. Retrieved 2013-10-20. 21. Jump up^ "Su-Doku's maths : General - Page 38". Forum.enjoysudoku.com. Retrieved 2013-10-20. 22. ^ Jump up to:a b "Su-Doku's maths : General - Page 36". Forum.enjoysudoku.com. Retrieved 2013-10-20. 23. ^ Jump up to:a b c "Su-Doku's maths : General - Page 38". Forum.enjoysudoku.com. Retrieved 2013-10-20. 24. ^ Jump up to:a b c "RxC Sudoku band counting algorithm : General". Forum.enjoysudoku.com. Retrieved 2013-10-20. 25. Jump up^ "Su-Doku's maths : General - Page 3". Forum.enjoysudoku.com. Retrieved 2013-10-20. 26. Jump up^ "RxC Sudoku band counting algorithm : General". Forum.enjoysudoku.com. Retrieved 2013-10-20. 27. ^ Jump up to:a b c d "RxC Sudoku band counting algorithm : General". Forum.enjoysudoku.com. Retrieved 2013-10-20. 28. Jump up^ "Su-Doku's maths : General - Page 37". Forum.enjoysudoku.com. Retrieved 2013-10-20. 29. Jump up^ "RxC Sudoku band counting algorithm : General". Forum.enjoysudoku.com. Retrieved 2013-10-20. 30. ^ Jump up to:a b c "Su-Doku's maths : General - Page 37". Forum.enjoysudoku.com. Retrieved 2013-10-20. 31. Jump up^ "RxC Sudoku band counting algorithm : General". Forum.enjoysudoku.com. Retrieved 2013-10-20. 32. Jump up^ "RxC Sudoku band counting algorithm : General". Forum.enjoysudoku.com. Retrieved 2013-10-20. 33. Jump up^ "Properties, isomorphisms and enumeration of 2-Quasi-Magic Sudoku grids". Discrete Mathematics. 311: 1098–1110. 2011-07-06. doi:10.1016/j.disc.2010.09.026. Retrieved 2013-10-20. 34. Jump up^ "Su-Doku's maths : General - Page 27". Forum.enjoysudoku.com. Retrieved 2013-10-20. 35. Jump up^ "Su-Doku's maths : General - Page 13". Forum.enjoysudoku.com. Retrieved 2013-10-20. 36. Jump up^ "Su-Doku's maths : General - Page 27". Forum.enjoysudoku.com. Retrieved 2013-10-20. 37. Jump up^ "Sudoku Programmers :: View topic - Number of "magic sudokus" (and random generation)". Setbb.com. Archived from the original on 6 February 2012. Retrieved 20 October 2013.