वांछित कठिनाई का एक सुडोकू उत्पन्न करना?

Question

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

मुझे क्या करना चाहते हैं, लेकिन इस पर कोई वास्तविक संसाधन खोजने में असमर्थ किया गया है क्या, एक "कठिनाई मूल्य" से एक पहेली उत्पन्न है (0-1.0 मूल्य, 0 सबसे आसान जा रहा है, और 1.0 सबसे मुश्किल रहा है)।

उदाहरण के लिए, मैं एक साधारण मुश्किल पहेली बनाना चाहता हूं, इसलिए मान .675 चुना गया है। अब उस मूल्य का उपयोग करके मैं एक मामूली मुश्किल पहेली उत्पन्न करने में सक्षम होना चाहता हूं।

किसी को इस तरह कुछ पता है? या शायद एक समान पद्धति के साथ कुछ?

Answer 1

यह आप क्या पूछना के रूप में के रूप में सुंदर नहीं है, लेकिन आप कैशिंग के साथ इस व्यवहार अनुकरण कर सकते हैं:

1. तय कितने "बकेट" आप पहेली के लिए चाहते हैं। उदाहरण के लिए, मान लें कि आप 20 चुनते हैं। इस प्रकार, आपकी बाल्टी में विभिन्न कठिनाई श्रेणियों के पहेली शामिल होंगे: 0 -05, .05-.1, .1 -15, .., .9-.95, .95- 1
2. एक पहेली
3. ग्रेड पहेली
4. उचित बाल्टी में यह रखो (या इसे फेंक जब बाल्टी भर गया है)
5. दोहराएँ उत्पन्न तक अपने बकेट "भरा" कर रहे हैं। बाल्टी का आकार और जहां वे संग्रहीत हैं, आपके आवेदन की ज़रूरतों पर आधारित होंगे।

फिर जब कोई उपयोगकर्ता किसी निश्चित कठिनाई पहेली का अनुरोध करता है, तो उन्हें अपनी बाल्टी से एक कैश किया जाता है। आप एक ही स्तर की कठिनाई के साथ समान पहेली उत्पन्न करने के लिए ज्ञात कठिनाइयों के साथ पहेली को बदलने और पहेली के उन्मुखीकरण पर विचार करना चाह सकते हैं। फिर उपरोक्त को दोहराएं जब आपको अपनी बाल्टी को नए पहेली के साथ फिर से भरना होगा।

Answer 2

ठीक है, आप यह नहीं जानते कि यह कैसे हल किया जाए, इससे पहले कि आप इसे कितना जटिल बनाते हैं। और सुडोकू को सुलझाने (और इसलिए कठिनाई रेटिंग) NP-C complexity class से संबंधित है, इसका मतलब है कि यह (सबसे अधिक संभावना) एक एल्गोरिदम खोजने के लिए तर्कसंगत रूप से असंभव है जो प्रस्तावित यादृच्छिक रूप से अनुमानित और अनुमान से तेज है (asymptotically)।

हालांकि, अगर आप एक मिल सकता है, तो आप P versus NP problem समाधान कर लिया है और Fields Medal के लिए एक अलमारी को स्पष्ट करना चाहिए ... :)

Answer 3

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

सूचना सिद्धांत की तरह लगता है, हाँ इसमें भी एप्लिकेशन हैं।

सुडोकू पहेली में एक अनूठा समाधान होना चाहिए। इसके अलावा सुडोकू पहेली में कुछ समरूपताएं होती हैं, यानी पंक्ति से, स्तंभ द्वारा और उप-वर्ग द्वारा।

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

यह सबसे कठिन/कठिन सुडोकू पहेली स्तर होगा (यानी न्यूनतम आवश्यक संख्याओं की संख्या)। फिर कम कठोर से आसान सभी अन्य कठिनाई का स्तर आवश्यक न्यूनतम राशि की तुलना में अधिक सुराग की अनुमति देकर उत्पन्न होता है।

यह ध्यान दिया जाना चाहिए कि सुडोकू कठिनाई का स्तर मानक नहीं है, जैसा ऊपर बताया गया है, किसी के पास जितना चाहें उतना या कुछ कठिनाई का स्तर हो सकता है। मानक क्या है न्यूनतम संकेत (और स्थिति) सुराग (जो सबसे कठिन स्तर है और जो सुडोकू समरूपता से संबंधित है) है, तो कोई भी कई कठिनाई के स्तर उत्पन्न कर सकता है क्योंकि कोई अतिरिक्त/अनावश्यक सुराग दिखने की अनुमति देकर बस चाहता है भी।

Answer 4

ऑन-द-फ्लाई वांछित कठिनाई के सुडोकू उत्पन्न करने के लिए एक और जवाब जोड़ना।

इसका मतलब यह है कि दूसरे दृष्टिकोण के विपरीत एल्गोरिथ्म केवल एक बार चलाता है और (पैदा करने के लिए (एक सीमा के भीतर या = 1 संभावना के साथ उच्च संभावना के साथ)

विभिन्न समाधान वांछित कठिनाई मिलान एक सुडोकू विन्यास रिटर्न और रेटिंग) एक सुडोकू कठिनाई को human-based techniques and approaches के साथ करना है, जो आसानी से रेट किया जा सकता है।

फिर

एक फिर से हल मानव की तरह solver के साथ सुडोकू और (एक सुडोकू विन्यास उत्पन्न होने के बाद) तकनीक solver इस्तेमाल किया पर निर्भर करता है (उदाहरण के लिए जोड़े, एक्स दक्षिणपंथी, स्वोर्डफ़िश आदि) एक कठिनाई दर भी सौंपा गया है। इस दृष्टिकोण साथ

समस्याएं (और उपयोग के मामले में मैं था के लिए आवश्यकताओं)

1. आदेश दिया कठिनाई के साथ एक सुडोकू उत्पन्न करने के लिए, एक एक सुडोकू दो बार हल करने के लिए (एक बार की जरूरत है पिछले विधि के साथ मूल एल्गोरिदम के साथ और एक बार मानव की तरह सॉल्वर के साथ)।

2. किसी को कई सूडोकस उत्पन्न करना पड़ता है जिसे को हल करने के बाद को मानव-सॉल्वर द्वारा हल किया जा सकता है। तो एक बार एक वांछित सुडोकू ऑन-द-फ्लाई उत्पन्न नहीं कर सकता है।

3. मानव-जैसे सॉल्वर जटिल हो सकता है और ज्यादातर मामलों में (यदि सभी नहीं) कसकर 9 x 9 सुडोकू ग्रिड के साथ मिलकर है। तो अन्य सुडोकस (उदाहरण 4x4, 16x16, 6x6 इत्यादि) के लिए कोई आसान सामान्यीकरण नहीं

4. मानव जैसी तकनीकों की कठिनाई रेटिंग बहुत ही व्यक्तिपरक है। उदाहरण के लिए x-wingछिपे हुए एकल से अधिक कठिन होने के लिए लिया गया है? (Personaly कई मुश्किल प्रकाशित सुडोकू पहेली manualy और कभी नहीं किया ऐसी तकनीकों को हल किया है)

एक और दृष्टिकोण जो निम्नलिखित लाभ है इस्तेमाल किया गया था:

1. मनमाना sudokus के लिए अच्छी तरह से generalises (9x9, 4x4, 6x6 , 16x16 आदि ..)
2. वांछित कठिनाई के साथ सुडोकू कॉन्फ़िगरेशन, एक बार और ऑन-द-फ्लाई
3. कठिनाई रेटिंग उद्देश्य है।

यह कैसे काम करता है?

सबसे पहले, सरल तथ्य यह है कि पहेली को और अधिक कठिन, जितना अधिक समय हल किया जाना चाहिए।

लेकिन हल होने का समय गहराई से दोनों सुराग (गिवेन्स) और प्रति खाली सेल की जांच के औसत विकल्पों से घनिष्ठ है।

विस्तार मेरी previous answer, यह उल्लेख किया गया था कि किसी भी सुडोकू पहेली के लिए सुराग की न्यूनतम संख्या पहेली का एक उद्देश्य संपत्ति है (उदाहरण के for 9x9 grids the minimum number of clues for having a valid sudoku is 17 के लिए)

एक वहाँ से शुरू करने और गणना कठिनाई प्रति सुराग की न्यूनतम संख्या कर सकते हैं स्तर (रैखिक सहसंबंध)।

इसके अलावा सुडोकू पीढ़ी प्रक्रिया के प्रत्येक चरण में, एक यकीन है कि औसत विकल्प (जांच की जा रही) खाली सेल प्रति दिए गए सीमा के भीतर है बना सकते हैं

कि क्या एल्गोरिथ्म पर निर्भर करता है (वांछित कठिनाई के एक समारोह के रूप में) बैकट्रैक का उपयोग करता है या नहीं (उपयोग किए गए मामले के लिए एल्गोरिदम कोई बैकट्रैकिंग नहीं करता है) वांछित कठिनाई या तो संभाव्यता = 1 या सीमाओं (क्रमशः) के भीतर उच्च संभावना के साथ पहुंचा जा सकता है।

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

(इस्तेमाल किया है इस ऑनलाइन sudoku solver (और यह भी this one) परीक्षण sudokus की कठिनाई दरों सहसंबंधी)

कोड उपलब्ध मुक्त on github sudoku.js (along with sample demo application), CrossWord.js में एक पेशेवर क्रॉसवर्ड बिल्डर का एक छोटा-डाउन संस्करण है जावास्क्रिप्ट, एक ही लेखक द्वारा