एल्गोरिथ्म एक्स के साथ सुडोकू को हल करें

इस लेख में, हम नथुथ के "अल्गोरिथम एक्स" पर विचार करते हैं और सुडोकू को हल करने के लिए इसके आवेदन पर विचार करते हैं। एल्गोरिथ्म की सुंदरता यह है कि सुडोकू को किसी भी उन्नत समाधान तकनीकों की प्रोग्रामिंग के बिना जल्दी से हल किया जाता है।

यह सब शुरू हुआ, वास्तव में, प्रोजेक्ट यूलर के कार्यों के साथ, जहां, एक उत्तर प्राप्त करने के लिए, आपको 50 सुडोकू को हल करने की आवश्यकता है। और ऐसा लगता है कि उन्होंने एक मूर्खतापूर्ण खोज को हल करने के लिए एक कार्यक्रम लिखकर इसका उत्तर प्राप्त किया, लेकिन किसी तरह समाधान की गति के साथ कुछ असंतोष था। यह देखने के बाद कि सामान्य लोग सुडोकु को कैसे हल करते हैं, मैंने पाया कि डोनाल्ड नॉट द्वारा आविष्कार किया गया अल्गोरिथम एक्स का उपयोग इसके लिए किया जा रहा है।

एल्गोरिदम एक्स

यह एल्गोरिथ्म सेट को सही ढंग से कवर करने की समस्या को हल करता है। या, यदि आप चाहें, तो यह एक "असतत पहेली" एकत्र करता है, जो उपलब्ध टुकड़ों के आकार के बारे में जानकारी रखता है। औपचारिक रूप से:

• कई एस हैं
• इस सेट के सबसेट Y का एक सेट है
• कार्य वाई से चुनने के लिए है ऐसे तत्व वाई * कि एस से प्रत्येक तत्व वाई * में शामिल केवल एक सेट में निहित है।
• यही है, Y में सभी सेटों का मिलन सेट S को ढंकता है (कवर करता है), और Y * में एक ही समय में कोई जोड़-तोड़ करने वाले सेट नहीं हैं

उदाहरण के लिए, सेटों पर विचार करें
एस = {१, २, ३, ४, ५} और
Y = { A = {1, 2},
बी = {२, ३},
C = {1, 5},
D = {1, 4},
E = {5}}
सेट बी , डी, और ई सेट एस का एक सटीक कवर बनाते हैं ।

एक्स नथ एल्गोरिथ्म के लिए, सेट वाई को एक द्विआधारी मैट्रिक्स के रूप में दर्शाया जाता है, जहां पंक्तियों के तत्व वाई से मेल खाते हैं, और ए _{आई, जे} = 1, अगर एस _जे वाई में है । यानी ऊपर दिए गए उदाहरण के लिए:

सटीक कवरेज खोज एल्गोरिथ्म इस प्रकार है:

• इनपुट डेटा: सेट एस और वाई ; संभावित रूप से कवरेज में शामिल किए गए सेटों का Stack (शुरू में खाली हो सकता है या पहले से ही कुछ तत्व हो सकते हैं)
  
  1. यदि सेट एस खाली है, तो वांछित कवर स्टैक पर है।
  2. यदि सेट वाई खाली है, तो कवरिंग नहीं मिली।
  3. हम सेट S में उस तत्व की तलाश कर रहे हैं जो Y में सेट की न्यूनतम संख्या में शामिल है ।
  4. Y से चुनें सभी पंक्तियाँ हैं जिनमें X है ।
  5. प्रत्येक सेट एक्स के लिए, 6-9 दोहराएं।
  6. एक संभावित कवरेज तत्व के रूप में X को स्टैक में जोड़ें।
  7. हम S ' और Y' सेट करते हैं: S ' S वह है जिससे X में निहित सभी तत्व हटा दिए जाते हैं , Y' Y से ऐसे सेट होते हैं जो X के साथ प्रतिच्छेद नहीं करते हैं।
  8. हम एल्गोरिथ्म X को S ' , Y' और Stack ।
  9. यदि यह चरण 7 में पाया गया कि कवरेज असंभव है, तो Stack के शीर्ष से तत्व को हटा दें और अगले एक्स पर जाएं। यदि कोई समाधान पाया जाता है, तो हम उसे वापस कर देते हैं।
  10. यदि किसी एक्स के लिए कोई समाधान नहीं है, तो इस इनपुट के लिए कार्य हल नहीं है।

सामान्य तौर पर, कुछ भी विशेष रूप से जटिल नहीं है। अनिवार्य रूप से - गहराई में सामान्य खोज। वैसे, हम ध्यान दें कि यदि आप शुरू में स्टैक को गैर-रिक्त करने के लिए सेट करते हैं, तो समस्या को "सटीक कवरेज खोजें जिसमें पहले से ही स्टैक पर झूठ बोलने वाले तत्व शामिल हैं" के रूप में तैयार किया जा सकता है।

सूक्ष्मता यह है कि व्यवहार में इस एल्गोरिथ्म का उपयोग उन समस्याओं के लिए किया जाता है जहां वाई में सेट "छोटा" है, अर्थात। मैट्रिक्स बहुत विरल है, जिसके कारण, उदाहरण के लिए, मैट्रिक्स के रूप में मानक भंडारण के दौरान स्तंभों के बीच चौराहों की खोज करने में अस्वीकार्य रूप से लंबा समय लगता है।
इसलिए, नट इस एल्गोरिथ्म को "डांसिंग लिंक" तंत्र के साथ पूरक करता है । मैट्रिक्स को द्वि-आयामी दोगुनी लिंक्ड सूची के रूप में दर्शाया गया है: सूची में प्रत्येक पंक्ति के लिए केवल स्तंभ संख्याएं संग्रहीत हैं, जहां इस पंक्ति में इकाइयां हैं। सूची में पंक्ति और स्तंभ में अगले और पिछले तत्व के लिंक भी हैं। यह संगठन आपको दो-आयामी सरणी में संग्रहीत होने पर O ( m * n ) की तुलना में O (1) समय के दौरान एक विरल मैट्रिक्स से कॉलम और पंक्तियों को हटाने की अनुमति देता है।

यह दिलचस्प है कि अली असफ सहयोगी सूचियों का उपयोग करके डांसिंग लिंक के तंत्र के लिए एक विकल्प प्रदान करता है, जो आपको उच्च स्तर की भाषाओं में शाब्दिक रूप से कई दर्जन लाइनों में एक्स एल्गोरिथ्म को लागू करने की अनुमति देता है।

विचार, दोनों स्तंभों और मैट्रिक्स पंक्तियों को साहचर्य सूचियों में संग्रहीत करना है। स्तंभों में हम पंक्ति सूचकांकों को संग्रहीत करते हैं, चौराहे पर जिसमें पंक्तियों में, क्रमशः, स्तंभ सूचकांकों में गैर-अक्षीय तत्व होते हैं। इसके अलावा, हम अनुक्रमित तरीके से पंक्तियों में अनुक्रमित करेंगे, एक सरणी में, हम ध्यान दें कि नथ के एल्गोरिथ्म में, पंक्तियों को संशोधित करना आवश्यक नहीं है, इसलिए किसी पंक्ति से किसी तत्व को जल्दी से हटाने के लिए अनुकूलन की आवश्यकता नहीं है। लेकिन कॉलम सेट के रूप में सेट किए जाएंगे, क्योंकि मैट्रिक्स से एक पंक्ति हटाते समय, सभी स्तंभों से इसकी पहचानकर्ता को हटाना आवश्यक होता है (और जब इसे सभी स्तंभों से हटा दिया जाता है, तो पंक्ति "स्वयं" गायब हो जाती है)।

जूलिया पर एल्गोरिथ्म के कार्यान्वयन पर विचार करें।
उदाहरण से मैट्रिक्स अब इस तरह दिखेगा:

 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 साथ प्रतिच्छेद करते हैं, लेकिन पिछले पुनरावृत्तियों में देखे गए तत्वों को मैट्रिक्स से हटाया नहीं जाता है। यह सुनिश्चित करता है कि जब हम push!(columns[col], added_row) में columns[col] push!(columns[col], added_row) कॉल push!(columns[col], added_row) के समय अंतरतम लूप में, रिवर्स ऑर्डर में push!(columns[col], added_row) 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 

सुडोकू

एक एल्गोरिथ्म है, मामला छोटा है - सटीक कवरेज खोजने के कार्य के रूप में सुडोकू पेश करने के लिए।

हम उन आवश्यकताओं को तैयार करते हैं जिन्हें एक हल किए गए सुडोकू द्वारा पूरा किया जाना चाहिए:

1. प्रत्येक सेल में 1 से 9 तक की संख्या होती है (या एक अलग आकार के वर्ग हल होने पर n ^{2 तक} )।
2. प्रत्येक पंक्ति में, प्रत्येक संख्या एक बार होती है।
3. प्रत्येक कॉलम में, प्रत्येक संख्या एक बार होती है।
4. प्रत्येक चतुर्थांश में, प्रत्येक संख्या एक बार होती है।

इनमें से प्रत्येक आवश्यकताओं को ठीक 1 बार पूरा किया जाना चाहिए, अर्थात वे सेट बनाते हैं जिन्हें कवर करने की आवश्यकता होती है। इसमें 4 n ² तत्व (मैट्रिक्स में कॉलम) हैं।

जिन सबसेट्स पर हम विचार करते हैं, वे एक विशिष्ट सेल में एक विशिष्ट संख्या को प्रतिस्थापित करके बनते हैं। उदाहरण के लिए, 1 पंक्ति और 4 स्तंभों के चौराहे पर नंबर 9 सेल में "एक उपसमूह" को कवर करता है (1,4) एक संख्या है, 1 पंक्ति में एक नंबर 9 है, 4 स्तंभों में एक संख्या 9 है, 2 चतुर्थांशों में एक संख्या 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 

यह काम करने लगता है, और गति स्वीकार्य है।

यह ध्यान दिया जाना चाहिए कि विशेष रूप से सुडोकू के लिए कोई तकनीक (उदाहरण के लिए, यहां या यहां ) वांछित सेट और कवर तत्वों के एक विशिष्ट प्रतिनिधित्व को छोड़कर, एल्गोरिदम में रखी नहीं गई थी।