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

सूडोकू

आपको एक सूडोकू ग्रिड दिया गया है, और आपको यह जाँचना है कि यह ग्रिड वैध (valid) है या नहीं।
एक वैध सूडोकू ग्रिड में निम्न शर्तें पूरी होनी चाहिए:
  • हर पंक्ति में 1 से 9 तक के सभी अंक शामिल हों।
  • हर स्तंभ में 1 से 9 तक के सभी अंक शामिल हों।
  • हर सेल में 1 से 9 तक के सभी अंक शामिल हों।
यदि सूडोकू ग्रिड अमान्य (not valid) है, तो इसमें ये समस्याएँ हो सकती हैं:
  • कुछ पंक्तियों में संख्याओं का दोहराव।
  • कुछ स्तंभों में संख्याओं का दोहराव।
  • कुछ सेल में संख्याओं का दोहराव।
notion image

Input

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

Output

यदि यह ग्रिड वैध हो, तो प्रोग्राम को Valid प्रिंट करना चाहिए, अन्यथा Not valid

Examples

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

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

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