एल्गोरिथ्म्स और डेटा स्ट्रक्चर्स

सुडोकू बोर्ड

आपको एक 9x9 सुडोकू बोर्ड दिया गया है, जिसमें कुछ खाने पहले से भरे हुए हैं। आपका काम इस सुडोकू बोर्ड को हल करना और एक वैध समाधान ढूँढ़ना है। यदि एक से अधिक वैध समाधान मौजूद हैं, तो आप उन सभी में से कोई भी समाधान प्रिंट कर सकते हैं।
सुडोकू बोर्ड एक 9x9 ग्रिड होता है, जिसे नौ 3x3 उप-ग्रिड में बाँटा जाता है। इस ग्रिड के प्रत्येक खाने में 1 से 9 तक कोई भी संख्या हो सकती है। सुडोकू का उद्देश्य बोर्ड में खाली स्थानों को इस तरह भरना है कि हर पंक्ति, हर स्तंभ और हर 3x3 उप-ग्रिड में 1 से 9 तक की सभी संख्याएँ बिना दोहराव के आ सकें।

इनपुट

इनपुट में 9 पंक्तियाँ होती हैं, जिनमें से प्रत्येक में 9 स्पेस-सेपरेटेड पूर्णांक होते हैं, जो सुडोकू बोर्ड की स्थिति दर्शाते हैं। दिए गए नंबर 1 से 9 के बीच होते हैं, और खाली खाना 0 द्वारा दर्शाया जाता है।

आउटपुट

नौ पंक्तियाँ प्रिंट करें, जिनमें से प्रत्येक पंक्ति में नौ स्पेस-सेपरेटेड पूर्णांक हों, जो दिए गए सुडोकू बोर्ड का एक समाधान दर्शाएँ। अगर एक से ज्यादा वैध समाधान उपलब्ध हों, तो आप किसी भी एक को प्रिंट कर सकते हैं।

उदाहरण

Input
Output
9 8 0 0 0 0 3 2 1 0 0 0 0 0 3 0 8 5 0 0 1 0 2 0 0 0 0 0 0 0 5 0 7 0 0 0 0 0 4 0 0 0 1 0 0 0 9 0 0 0 0 0 0 0 5 1 0 0 0 0 0 7 3 0 0 2 0 1 0 0 0 0 8 6 0 0 4 0 0 0 9
9 8 7 6 5 4 3 2 1 2 4 6 1 7 3 9 8 5 3 5 1 9 2 8 7 4 6 1 2 8 5 3 7 6 9 4 6 3 4 8 9 2 1 5 7 7 9 5 4 6 1 8 3 2 5 1 9 2 8 6 4 7 3 4 7 2 3 1 9 5 6 8 8 6 3 7 4 5 2 1 9

Constraints

Time limit: 50 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue