Tentai Show
टेंटाई शो, जिसे टेंटाइशो, आकाशगंगाओं, सर्पिल आकाशगंगाओं, या सिम-ए-पिक्स के नाम से भी जाना जाता है, निकोली द्वारा प्रकाशित एक द्विआधारी-निर्धारण तर्क पहेली है। नियम टेंटाई शो चौराहों के आयताकार ग्रिड पर खेला जाता है। ग्रिड पर तारों का प्रतिनिधित्व करने वाले बिंदु होते हैं, जो ग्रिड पर या तो एक सेल के केंद्र, एक किनारे या एक कोने पर पाए जा सकते हैं। पहेली का उद्देश्य ग्रिड को आकाशगंगाओं का प्रतिनिधित्व करने वाले क्षेत्रों में विभाजित करने के लिए डैश की गई रेखाओं के साथ रेखाएँ खींचना है। परिणामी ग्रिड में, सभी आकाशगंगाओं में 180° घूर्णन समरूपता होनी चाहिए और इसके केंद्र में बिल्कुल एक बिंदु होना चाहिए। बिंदुओं के रंग पहेली के तर्क को प्रभावित नहीं करते हैं और हल करते समय इसे नजरअंदाज किया जा सकता है। कई रंगीन बिंदुओं वाली पहेलियों में, एक चित्र को प्रकट करने के लिए तैयार ग्रिड के क्षेत्रों को संबंधित बिंदु रंगों से रंगा जा सकता है। समाधान विधियाँ टेंताई प्रदर्शित करें पहेलियों को निम्नलिखित चरणों का उपयोग करके हल किया जा सकता है। आस-पास की कोशिकाओं के बीच दीवारें बनाएँ जिनमें एक बिंदु या एक बिंदु का अंश हो। ये कोशिकाएँ अलग-अलग आकाशगंगाओं से संबंधित होनी चाहिए। घूर्णन समरूपता के अनुसार बिंदु के चारों ओर दीवारें बनाएँ। ग्रिड की सीमाओं को भी दीवारों के रूप में गिना जाता है। उन क्षेत्रों में कोशिकाओं का पता लगाएं जो एक बिंदु द्वारा 'कब्जा' किए गए हैं। ये ऐसी कोशिकाएँ हैं जिन तक किसी अन्य बिंदु द्वारा नहीं पहुँचा जा सकता है। ये कोशिकाएँ केवल उस बिंदु के लिए आकाशगंगा से संबंधित हो सकती हैं। उपरोक्त चरणों को तब तक दोहराया जा सकता है जब तक कि पहेली हल नहीं हो जाती। अधिक उन्नत पहेलियों में, घूर्णन समरूपता की छवि पर विचार करना आवश्यक हो सकता है। अपनी घूर्णन सममित कोशिका पर विचार करते समय ऐसी कोशिकाओं का पता लगाएं जिनमें केवल एक वैध बिंदु हो। एक कोशिका एक आकाशगंगा से संबंधित हो सकती है यदि उसकी सममित कोशिका भी उस आकाशगंगा से संबंधित हो सकती है। जापानी में व्याख्या करने पर पहेली के नाम, "टेंटाई शो" का दोहरा अर्थ है। "दस" का अर्थ है बिंदु, जबकि "ताई शो" का अर्थ है समरूपता। जापानी शब्द "टेंटाई" का उपयोग खगोलीय वस्तुओं को संदर्भित करने के लिए किया जाता है। एक साथ मिलकर, "टेंटाई शो" का अर्थ घूर्णन समरूपता और खगोलीय शो दोनों हो सकता है। कम्प्यूटेशनल जटिलता एन. पी.-पूर्णता यह निर्धारित करना कि क्या एक टेंटाई शो पहेली का कोई समाधान है, एन. पी.-पूर्ण के रूप में जाना जाता है। इसे फ्रीडमैन (2002) ने मनमाने बूलियन परिपथों के समतुल्य पहेलियों का निर्माण करके साबित किया था, जो बूलियन संतोषजनक समस्या के कारण एन. पी.-पूर्णता को दर्शाता है। फर्टिन, जमशिदी और कोमुसिविक्ज़ (2015) ने पहेली को एन. पी.-पूर्ण साबित करके इस परिणाम को मजबूत किया, जब सभी आकाशगंगाओं का आकार अधिकतम सात होता है। सबूत पहेली को पॉजिटिव प्लानर 1-इन-3-सैट तक कम कर देता है, जिसे एनपी-पूर्ण के रूप में जाना जाता है। डेमाइन, लॉफलर और श्मिट (2021) ने एन. पी.-पूर्णता को साबित करके इसे और मजबूत किया, भले ही सभी आकाशगंगाएँ 1 × 1,1 × 3, या 3 × 1 आकार के आयतों तक ही सीमित हों। उन्होंने यह भी दिखाया कि आकाशगंगाओं का एक न्यूनतम समूह खोजना जो किसी दिए गए आकार को बिल्कुल कवर करता है, एनपी-पूर्ण है। समाधान एल्गोरिदम टेंटाई ग्रिड के सभी संभावित विच्छेदनों से गुजरकर और यह जांचकर कि क्या यह एक वैध समाधान है, पहेली दिखाएँ जिसे घातीय समय में हल किया जा सकता है। फर्टिन, जमशिदी और कोमुसिविक्ज़ (2015) ने एक बहुपद-समय एल्गोरिथ्म दिखाया जो विभिन्न मामलों के लिए पहेली को हल कर सकता है, जैसे किः (ए) जब सभी आकाशगंगाओं का आकार अधिकतम दो होता है, (बी) जब सभी आकाशगंगाएं वर्ग होती हैं, और (सी) जब सभी आकाशगंगाएं तुच्छ रूप से जुड़ी होती हैं। यह भी देखें निकोली पहेली प्रकारों की सूची संदर्भ तर्क पहेली एन. पी.-पूर्ण समस्याएं