दिलचस्प पोस्ट
सी # वापसी त्रुटि "सभी कोड पथ एक मान वापस नहीं" जावा पूर्णांक तुलना करें () – क्यों तुलना बनाम घटाव का उपयोग करें? दो क्रमबद्ध सरणियों का अंतराल जावा में तारीखों में अंतर की गणना करना सत्र अपहरण को रोकना PHP के साथ आरएसएस / एटम फीड्स को पार्स करने का सबसे अच्छा तरीका फ़ंक्शन के नाम के ऑपरेटर के पते को लागू करने के समान फ़ंक्शन पॉइंटर के रूप में फ़ंक्शन नाम का उपयोग क्यों किया जा रहा है? एक फार्म के अंदर फार्म, ठीक है? स्विफ्ट भाषा NSClassFromString अक्षर की एक स्ट्रिंग में यूनिकोड एन्कोडिंग के साथ एक स्ट्रिंग कन्वर्ट कैसे करें एक "यह एप्लिकेशन एक पृष्ठभूमि थ्रेड से ऑटोलएवान इंजन को संशोधित कर रहा है" त्रुटि प्राप्त कर रहा है? NumPy सरणी के लिए पायथन अनुक्रम कन्वर्ट, अनुपलब्ध मानों को भरना मैं सी # में एक मल्टी-कैरेक्टर डिलीमीटर द्वारा स्ट्रिंग कैसे विभाजित करूं? डबल क्यों होता है। एनएएन == डबल। एनएएन झूठी वापसी क्यों करता है? क्या एक पूरे आवेदन के लिए संस्कृति स्थापित करने का एक तरीका है? सभी वर्तमान धागे और नए धागे?

अद्वितीय समाधान के साथ सुडोकू बोर्ड कैसे उत्पन्न करें

आप एक अद्वितीय समाधान के साथ एक सुडोकू बोर्ड कैसे उत्पन्न करते हैं? जो मैंने सोचा था कि एक यादृच्छिक बोर्ड शुरू करने के लिए और फिर कुछ संख्याओं को हटा दें। लेकिन मेरा प्रश्न यह है कि मैं एक समाधान की विशिष्टता कैसे बनाए रखूं?

वेब के समाधान से एकत्रित समाधान "अद्वितीय समाधान के साथ सुडोकू बोर्ड कैसे उत्पन्न करें"

आसान:

  1. एक कुशल बैक ट्रैकिंग एल्गोरिथम के साथ सभी समाधान ढूंढें
  2. यदि सिर्फ एक समाधान है, तो आप कर चुके हैं। अन्यथा अगर आपके पास एक से अधिक समाधान हैं, तो उस स्थान को खोजें जहां पर अधिकांश समाधान भिन्न होते हैं। इस स्थिति में नंबर जोड़ें
  3. 1 पर जाएं

मुझे संदेह है कि आप ऐसे समाधान पा सकते हैं जो इस से बहुत तेज होगा।

मेरे स्वयं के SuDoKu प्रोग्राम ऐसा तरीका है:


  1. एक पूर्ण, मान्य बोर्ड (81 नंबरों से भरा) से शुरू करें

  2. सभी 81 सेल पदों की एक सूची बनाओ और यह बेतरतीब ढंग से फेरबदल करें

  3. जब तक सूची रिक्त नहीं है, तब तक सूची से अगली स्थिति ले लीजिए और संबंधित सेल से संख्या निकालें

  4. एक तेज सॉल्वर का उपयोग करके विशिष्टता का परीक्षण करें (यदि आवश्यक हो तो बैक ट्रैकिंग के साथ) मेरा सॉल्वर सभी समाधानों की गणना करने में सक्षम है, लेकिन जब 1 से अधिक समाधान मिलते हैं तो यह बंद हो जाता है

  5. यदि मौजूदा बोर्ड में सिर्फ एक ही समाधान है, तो गोटो चरण 3) और दोहराएं।

  6. यदि मौजूदा बोर्ड में एक से अधिक समाधान हैं, तो अंतिम निष्कासन को रद्द करें (चरण 3), और सूची से अगली स्थिति के साथ चरण 3 को जारी रखें

  7. जब आप सभी 81 पदों का परीक्षण करते हैं तो रोकें।


यह आपको न केवल अद्वितीय बोर्ड प्रदान करता है, लेकिन बोर्ड जहां आप समाधान की अद्वितीयता को नष्ट किए बिना अधिक संख्याएं नहीं निकाल सकते।

बेशक, यह केवल एल्गोरिथम का दूसरा भाग है। पहली छमाही एक पूर्ण वैध बोर्ड पहले मिलनी है (बेतरतीब ढंग से भरा!) यह बहुत समान है, लेकिन "अन्य दिशा में":


  1. एक खाली बोर्ड से शुरू करें

  2. निशुल्क कोशिकाओं में से एक में एक यादृच्छिक संख्या जोड़ें (कक्ष बेतरतीब ढंग से चुना गया है, और संख्या को सुडोको नियमों के अनुसार इस सेल के लिए मान्य संख्याओं की सूची से बेतरतीब ढंग से चुना जाता है)

  3. जांचने के लिए बैक ट्रैकिंग सॉल्वर का उपयोग करें कि क्या वर्तमान बोर्ड में कम से कम एक वैध समाधान है। यदि नहीं, तो चरण 2 को वापस करें और दूसरे नंबर और सेल के साथ दोहराएं। ध्यान दें कि यह कदम अपने आप में पूर्ण वैध बोर्ड का उत्पादन कर सकता है, लेकिन वे किसी भी तरह यादृच्छिक नहीं हैं।

  4. दोबारा दोहराएं जब तक कि बोर्ड पूरी तरह से संख्याओं से भरा हो

आप धोखा दे सकते हैं एक मौजूदा सुडोकू बोर्ड के साथ आरंभ करें जिसे इसके साथ बेला किया जा सकता है।

आप किसी भी अन्य पंक्ति के साथ तीन 3×3 ब्लॉकों की किसी भी पंक्ति को स्वैप कर सकते हैं। आप किसी अन्य कॉलम के साथ तीन 3×3 ब्लॉकों के किसी भी कॉलम को स्वैप कर सकते हैं। प्रत्येक ब्लॉक पंक्ति या ब्लॉक कॉलम के भीतर आप एकल पंक्तियों और एकल कॉलम को स्वैप कर सकते हैं। आखिरकार आप संख्याओं को क्रमबद्ध कर सकते हैं ताकि पूर्ण पदों में अलग-अलग संख्याएं हो सकें, जब तक पूरे बोर्ड में क्रमचय संगत नहीं है।

इन परिवर्तनों में से कोई भी एक सुलझनीय योग्य बोर्ड नहीं करेगा।

जब तक पी = एनपी, कोई भी बहुपद-समय एल्गोरिथ्म नहीं है, जिसमें सामान्य सुडोकू समस्याएं एक ही समाधान के साथ उत्पन्न होती हैं।

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

एक तेजी से एल्गोरिथ्म के लिए अपनी उम्मीदों को खराब करने के लिए क्षमा करें!

एक सामान्य समाधान देना आसान नहीं है आपको एक विशेष प्रकार की सुडोकू उत्पन्न करने के लिए कुछ चीजें जानना चाहिए … उदाहरण के लिए, आप नौ से ज्यादा खाली 9-नंबर समूहों (पंक्तियां, 3×3 ब्लॉक या स्तंभ) के साथ सुडोकू नहीं बना सकते हैं। एक एकल समाधान सुडोकू में न्यूनतम दिए गए नंबर (यानी "सुराग") 17 माना जाता है, लेकिन अगर मैं गलत नहीं हूँ तो इस सुडोकू के लिए संख्याओं की स्थिति बहुत विशिष्ट है। सुडोकू के लिए सुराग की औसत संख्या लगभग 26 है, और मुझे यकीन नहीं है, लेकिन यदि आपने 26 पूर्ण होने तक पूर्ण ग्रिड की संख्या छोड़ दी है और उन्हें सममित तरीके से छोड़ दिया है, तो आपके पास एक मान्य सुडोकू हो सकता है दूसरी तरफ, आप पूरी तरह से ग्रिड से नंबरों को बेतरतीब ढंग से छोड़ सकते हैं और उन्हें जांचकर्ता या अन्य उपकरण के साथ परीक्षण नहीं कर सकते जब तक कि यह ठीक से नहीं आता।

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

लेकिन आप एक एसएटी-सॉल्वर का उपयोग भी कर सकते हैं, जैसा कि स्वयं के बैक-ट्रैकिंग एल्गोरिदम लिखने के विपरीत है। इस तरह, आप कुछ हद तक यह तय कर सकते हैं कि समाधान खोजने में कितना मुश्किल होगा: यदि आप निष्कर्ष के नियमों को प्रतिबंधित करते हैं जो एसएटी-सॉल्वर का उपयोग करता है, तो आप जांच सकते हैं कि आप आसानी से पहेली को हल कर सकते हैं या नहीं। बस "एसएटी को सुलझाने सुडोकू" के लिए Google

यहां एक क्लासिक सुडोकू पहेली बनाने का एक तरीका है (सुडोकू पहेली को एक और एकमात्र समाधान के साथ; पूर्व-भरे वर्गों को केंद्र वर्ग R5C5 के समरूप सममित किया जाता है)

1) एक पूर्ण ग्रिड के साथ शुरू करें (इसे आसानी से प्राप्त करने के लिए समूह भरने के लिए परिपत्र शिफ्ट का उपयोग करके)

2) दो सममित वर्गों से नंबरों को हटा दें यदि रिक्त वर्गों को शेष सुराग का उपयोग करके अनुमान लगाया जा सकता है।

3) दोहराने (2) जब तक सभी नंबरों की जांच नहीं की जाती।

इस पद्धति का उपयोग करके आप प्रोग्रामिंग के बिना या बिना एक बहुत आसान सुडोकू पहेली बना सकते हैं। आप इस पद्धति का उपयोग कठिन सुडोकू पहेलियाँ को शिल्प के लिए कर सकते हैं। आप उदाहरण के लिए एक कदम के लिए "क्लासिक सुडोकू बनाएं" खोजना चाहते हैं।