حل سودوكو مع خوارزمية X

في هذه المقالة ، نعتبر Knuth "Algorithm X" وتطبيقه لحل sudoku. جمال الخوارزمية هو أن سودوكو يتم حلها بسرعة دون برمجة أي تقنيات حل متقدمة.

بدأ كل شيء ، في الواقع ، مع المهام من Project Euler ، حيث للحصول على الجواب ، تحتاج إلى حل 50 سودوكو. ويبدو أنه تلقى إجابة عليه من خلال كتابة برنامج لحل عملية بحث غبية إلى حد ما ، ولكن بطريقة ما كان هناك بعض الاستياء من سرعة الحل. بعد أن رأيت كيف يحل الأشخاص العاديون سودوكو ، وجدت أن الخوارزمية X ، التي ابتكرها دونالد كنوت ، تستخدم لهذا الغرض.

خوارزمية X

هذه الخوارزمية تحل مشكلة تغطية المجموعة بدقة. أو ، إذا أردت ، فهو يجمع "لغزًا منفصلاً" ، يحتوي على معلومات حول شكل القطع المتوفرة. بشكل رسمي أكثر:

• هناك العديد من ق
• هناك مجموعة من مجموعات فرعية Y من هذه المجموعة
• المهمة هي أن تختار من Y هذه العناصر Y * بحيث يتم تضمين كل عنصر من العناصر S في واحدة فقط من المجموعات المدرجة في Y *
• أي أن اتحاد جميع المجموعات في Y * يشكل (يغطي) المجموعة S ، وفي الوقت نفسه في Y * لا توجد مجموعات متقاطعة

على سبيل المثال ، ضع في اعتبارك المجموعات
S = {1 ، 2 ، 3 ، 4 ، 5} و
Y = { A = {1 ، 2} ،
ب = {2 ، 3} ،
C = {1 ، 5} ،
D = {1 ، 4} ،
E = {5}}
تشكل المجموعات B و D و E غطاءًا دقيقًا للمجموعة S.

بالنسبة إلى خوارزمية X Knuth ، يتم تمثيل المجموعة Y كمصفوفة ثنائية ، حيث تتوافق الصفوف مع العناصر Y ، و A _{i ، j} = 1 ، إذا كانت S _j في Y _i . أي على سبيل المثال أعلاه:

خوارزمية البحث عن التغطية الدقيقة هي كما يلي:

• إدخال البيانات: مجموعات S و Y ؛ Stack مجموعات يحتمل أن تكون مدرجة في التغطية (قد تكون في البداية فارغة أو لديها بالفعل بعض العناصر)
  
  1. إذا كانت المجموعة S فارغة ، فإن الغطاء المرغوب يكون في المجموعة.
  2. إذا كانت المجموعة Y فارغة ، فلن يتم العثور على الغطاء.
  3. نحن نبحث عن العنصر s في المجموعة S المضمنة في الحد الأدنى لعدد المجموعات في Y.
  4. اختر من Y جميع الأسطر X التي تحتوي على s .
  5. لكل مجموعة X ، كرر 6-9.
  6. أضف X إلى المكدس كعنصر تغطية محتمل.
  7. نقوم بتشكيل المجموعتين S ' و Y' : S ' هي S ، حيث تتم إزالة جميع العناصر الموجودة في X ، Y عبارة عن مجموعات من Y لا تتقاطع مع X.
  8. نسمي الخوارزمية X لـ S ' و Y' و Stack .
  9. إذا وجد في الخطوة 7 أن التغطية مستحيلة ، فقم بإزالة العنصر من أعلى Stack ثم تابع إلى علامة X التالية . إذا تم العثور على حل ، فإننا نعيده.
  10. إذا لم يكن هناك حل لأي X ، فلن يتم حل المهمة لهذا الإدخال.

بشكل عام ، لا شيء معقد للغاية. أساسا - البحث المعتاد في العمق. بالمناسبة ، نلاحظ أنه في حالة تعيين المكدس في البداية على أنه غير فارغ ، يمكن صياغة المشكلة على أنها "العثور على التغطية الدقيقة التي تتضمن عناصر موجودة بالفعل في الحزمة."

تتمثل الدقة في أن هذه الخوارزمية يتم استخدامها في الواقع العملي للمشاكل التي تكون فيها المجموعات في Y "صغيرة" ، أي المصفوفة متناثرة للغاية ، بسببها ، على سبيل المثال ، يستغرق البحث عن التقاطعات بين الأعمدة أثناء التخزين القياسي في شكل مصفوفة وقتًا طويلاً بشكل غير مقبول.
لذلك ، يكمل Knut هذه الخوارزمية بآلية "ارتباط الرقص" . يتم تمثيل المصفوفة في شكل قائمة ثنائية الأبعاد مرتبطة: في كل صف في القائمة ، يتم تخزين أرقام الأعمدة فقط ، حيث يحتوي هذا الصف على وحدات. تحتوي القائمة أيضًا على روابط للعنصر التالي والسابق في صف وعمود. تسمح لك هذه المؤسسة بإزالة الأعمدة والصفوف من مصفوفة متفرق خلال وقت O (1) مقارنةً بـ O ( m * n ) عند تخزينها في صفيف ثنائي الأبعاد.

من المثير للاهتمام أن علي عساف يقدم بديلاً لآلية روابط الرقص باستخدام القوائم الترابطية ، والتي تتيح لك تنفيذ خوارزمية X بعشرات الأسطر حرفيًا بلغات عالية المستوى.

تتمثل الفكرة في تخزين كل من الأعمدة وصفوف المصفوفة في القوائم الترابطية. في الأعمدة نقوم بتخزين مؤشرات الصفوف ، عند التقاطع الذي توجد به عناصر غير صفرية ، في الصفوف ، على التوالي ، فهارس الأعمدة. علاوة على ذلك ، سنقوم بتخزين الفهارس في الصفوف بطريقة منظمة ، في صفيف ، نلاحظ أنه في خوارزمية Knuth ، ليس من الضروري تعديل الصفوف ، وبالتالي لا يلزم تحسين حذف عنصر من صف بسرعة. ولكن سيتم تعيين الأعمدة في شكل مجموعات ، لأن عند حذف صف من مصفوفة ، من الضروري إزالة معرفه من جميع الأعمدة (وعند حذفه من جميع الأعمدة ، يختفي الصف "بمفرده").

النظر في تنفيذ الخوارزمية على جوليا.
المصفوفة من المثال ستبدو الآن كما يلي:

 Y = Dict( 'A' => [1, 2], 'B' => [2, 3], 'C' => [1, 5], 'D' => [1, 4], 'E' => [5] ) S = Dict( 1 => Set(['A', 'C', 'D']), 2 => Set(['A', 'B']), 3 => Set(['B']), 4 => Set(['D']), 5 => Set(['C', 'E']) ) 

لكي تعمل الخوارزمية ، فأنت بحاجة إلى وظيفة تستخرج أسطرًا من المصفوفة التي تتقاطع مع المرسومة ، ووظيفة تُرجع هذه السطور إلى مكانها.

 function extract_intersects!(rows, columns, base_row) buf = [] for elt in rows[base_row] #        push!(buf, pop!(columns, elt)) #         for intersecting_row in buf[end] for other_elt in rows[intersecting_row] if other_elt != elt delete!(columns[other_elt], intersecting_row) end end end end return buf end function restore_intersects!(rows, columns, base_row, buf) #       base_row  ,      for elt in Iterators.reverse(rows[base_row]) columns[elt] = pop!(buf) for added_row in columns[elt] for col in rows[added_row] push!(columns[col], added_row) end end end end 

لكي تعمل هاتان الوظيفتان كما ينبغي ، كان مطلوبًا تخزين العناصر المطلوبة فقط في صفوف المصفوفة. في الدالة extract_intersects!() ، عند كل تكرار للحلقة الخارجية ، تتم إزالة تلك الصفوف التي تتقاطع مع base_row ولكنها لا تحتوي على عناصر تم عرضها في التكرارات السابقة من المصفوفة. هذا يضمن أنه عندما نقوم بإدراج الأعمدة في restore_intersects!() بالترتيب العكسي ، في الحلقة الداخلية في وقت push!(columns[col], added_row) المكالمة push!(columns[col], added_row) سيتم إرجاع العمود columns[col] بالفعل إلى المصفوفة ، وسيتم حذف جميع الأعمدة في المصفوفة extract_intersects!() سيتم إرجاع العناصر من الأعمدة إلى مكانها الأصلي.

الآن الخوارزمية X نفسها:

 function algorithm_x(rows, columns, cover = []) if isempty(columns) return cover else #       m, c = findmin(Dict(k => length(v) for (k, v) in columns)) for subset in collect(columns[c]) push!(cover, subset) #     #   subset  buf_cols = extract_intersects!(rows, columns, subset) s = algorithm_x(rows, columns, cover) #     - ,  s == nothing || return s restore_intersects!(rows, columns, subset, buf_cols) pop!(cover) end #      columns[c] , #        return nothing end end 

سودوكو

هناك خوارزمية ، الأمر صغير - تقديم Sudoku كمهمة لإيجاد التغطية الدقيقة.

نقوم بصياغة المتطلبات التي يجب الوفاء بها من خلال سودوكو حلها:

1. يوجد في كل خلية رقم من 1 إلى 9 (أو حتى n ² إذا تم حل المربعات ذات الأحجام المختلفة).
2. في كل سطر ، يحدث كل رقم مرة واحدة.
3. في كل عمود ، يحدث كل رقم مرة واحدة.
4. في كل رباعي ، يحدث كل رقم مرة واحدة.

يجب الوفاء بكل من هذه المتطلبات مرة واحدة بالضبط ، أي أنها تشكل المجموعة التي تحتاج إلى تغطيتها. لديها بالضبط 4 ن ² عناصر (أعمدة في المصفوفة).

يتم تشكيل المجموعات الفرعية التي نعتبرها باستبدال رقم معين في خلية معينة. على سبيل المثال ، الرقم 9 عند تقاطع صف واحد و 4 أعمدة "يغطي" مجموعة فرعية "في الخلية (1،4) عبارة عن رقم ، في صف واحد يوجد رقم 9 ، في 4 أعمدة يوجد رقم 9 ، في رباعين يوجد رقم 9" (ضمناً المعتاد سودوكو 9 × 9).

بعد ذلك ، تتم كتابة خوارزمية الحل بشكل تافه.

 #    9×9,      #   -   (row, col, num) #  : # (0, row, col) -   row  col   # (1, row, num) -   row   num # (2, col, num) -   col   num # (3, q, num) -   q   num function xsudoku(puzzle::AbstractMatrix{Int}) rows = Dict() cols = Dict() #   for row in 1:9, col in 1:9, num in 1:9 r = [] quad = ((row-1)÷3)*3 + (col-1)÷3 + 1 push!(r, (0, row, col), (1, row, num), (2, col, num), (3, quad, num)) rows[(row, col, num)] = r end #   for type in 0:3, n1 in 1:9, n2 in 1:9 cols[(type, n1, n2)] = Set() end for (rk, rv) in rows for v in rv push!(cols[v], rk) end end # s -    #  ,     ,    s = [] for i in 1:9, j in 1:9 if puzzle[i, j] > 0 elt = (i, j, puzzle[i,j]) push!(s, elt) #    ,       extract_intersects!(rows, cols, elt) end end # ,   -   success = algorithm_x(rows, cols, s) success != nothing || return nothing #      ret = similar(puzzle) for (i, j, num) in s ret[i,j] = num end return ret end 

دعونا نتحقق من بعض الأمثلة:

  julia> @time xsudoku([0 0 0 0 0 0 4 0 0; 3 0 6 0 0 0 0 0 0; 0 0 0 1 9 6 0 3 0; 0 7 0 0 0 0 0 1 0; 8 0 0 2 5 0 0 9 0; 0 4 0 0 0 0 8 0 0; 0 6 0 4 0 9 0 0 8; 0 0 5 0 0 0 0 2 0; 0 0 0 5 0 0 0 0 7]) 0.006326 seconds (54.91 k allocations: 3.321 MiB) 9×9 Array{Int64,2}: 1 5 7 8 3 2 4 6 9 3 9 6 7 4 5 2 8 1 2 8 4 1 9 6 7 3 5 6 7 2 9 8 4 5 1 3 8 3 1 2 5 7 6 9 4 5 4 9 6 1 3 8 7 2 7 6 3 4 2 9 1 5 8 4 1 5 3 7 8 9 2 6 9 2 8 5 6 1 3 4 7 

يبدو للعمل ، والسرعة مقبولة.

تجدر الإشارة إلى أنه لم يتم وضع أي تقنيات خاصة بسودوكو (على سبيل المثال ، هنا أو هنا ) في الخوارزمية ، باستثناء تمثيل محدد للمجموعة المرغوبة وعناصر التغطية.