वैध सुडोकू (LeetCode 36): पायथन समाधान, बॉक्स इंडेक्स, और एज केस

Valid Sudoku (LeetCode 36) में आपको 9 बाय 9 का आंशिक रूप से भरा हुआ बोर्ड दिया जाता है और पूछा जाता है कि क्या भरी हुई कोशिकाएँ सुडोकू के किसी नियम को तोड़ती हैं। आपको पहेली हल करने की ज़रूरत नहीं है। आपको बस यह जाँचना है कि किसी पंक्ति, स्तंभ या 3 बाय 3 बॉक्स में कोई अंक दोहराया नहीं गया है। देखे गए अंकों के तीन सेट के साथ एक ही पास में यह O(81) में हो जाता है, जो कि स्थिर है।

समस्या

बोर्ड 9 बाय 9 का ग्रिड है जिसमें हर अक्षर 1 से 9 तक का अंक या खाली के लिए . होता है। यदि भरी हुई कोशिकाएँ इन नियमों का पालन करती हैं तो true लौटाएँ:

• किसी पंक्ति में कोई अंक दोहराया नहीं जाता।
• किसी स्तंभ में कोई अंक दोहराया नहीं जाता।
• किसी 3 बाय 3 बॉक्स में कोई अंक दोहराया नहीं जाता।

कोई बोर्ड वैध हो सकता है भले ही उसका कोई हल न हो। केवल भरी हुई कोशिकाओं की जाँच की जाती है।

दृष्टिकोण: प्रत्येक इकाई के लिए तीन सेट

प्रत्येक पंक्ति, प्रत्येक स्तंभ और प्रत्येक बॉक्स के लिए देखे गए अंकों का एक सेट रखें। प्रत्येक भरी हुई कोशिका के लिए, अंक के लिए तीनों सेट जाँचें, और यदि यह नया है तो इसे जोड़ें।

केवल बॉक्स इंडेक्स पर विचार करना पड़ता है। पंक्ति r और स्तंभ c पर स्थित कोशिका के लिए, बॉक्स संख्या (r // 3) * 3 + c // 3 होती है। यह बॉक्स को बाएँ से दाएँ, ऊपर से नीचे, 0 से 8 तक गिनता है।

def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == ".":
                continue
            b = (r // 3) * 3 + c // 3
            if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
                return False
            rows[r].add(ch)
            cols[c].add(ch)
            boxes[b].add(ch)
    return True

ट्रेस

मान लीजिए पंक्ति 0 में स्तंभ 0 पर 5 है और स्तंभ 4 पर एक और 5 है। पहला 5 rows[0], cols[0] और boxes[0] में जोड़ा जाता है। स्तंभ 4 पर, जाँच ch in rows[0] सत्य है, इसलिए फ़ंक्शन तुरंत false लौटाता है। एक ही बॉक्स या स्तंभ में समान अंक अन्य दो सेटों द्वारा उसी तरह पकड़े जाते हैं।

जटिलता

बोर्ड हमेशा 9 बाय 9 होता है, इसलिए समय स्थिर है, 81 कोशिका विज़िट। यदि आप इसे n बाय n बोर्ड तक सामान्यीकृत करते हैं, तो यह O(n squared) समय और O(n squared) स्थान है। दोनों बताएँ, क्योंकि साक्षात्कारकर्ता अक्सर पूछते हैं कि यह कैसे स्केल होता है।

विविधताएँ जो साक्षात्कारकर्ता पूछते हैं

बिटमास्क संस्करण प्रत्येक सेट को एक पूर्णांक से बदल देता है। mask & (1 << d) एक अंक का परीक्षण करता है और mask |= 1 << d इसे रिकॉर्ड करता है। यह तेज़ है, लेकिन सेट संस्करण समय के दबाव में सही करना आसान है, इसलिए पहले वही लिखें।

सामान्य गलतियाँ

• पंक्तियों और स्तंभों की जाँच करना लेकिन बॉक्स भूल जाना।
• गलत बॉक्स सूत्र, जैसे r // 3 + c // 3, जो विभिन्न बॉक्स को एक ही इंडेक्स देता है।
• . को अंक मानना, जिससे दो खाली कोशिकाएँ दोहराव के रूप में गिनी जाती हैं।
• बोर्ड को हल करने की कोशिश करना जब प्रश्न केवल वैधता माँगता है।

परीक्षण के लिए एज केस

साक्षात्कार में इसे कैसे समझाएँ

1. नियमों को दोहराएँ और कहें कि आप केवल सत्यापन करते हैं, हल नहीं।
2. तीन इकाइयों के नाम बताएँ और कहें कि प्रत्येक को एक देखे-गए सेट की आवश्यकता है।
3. बॉक्स इंडेक्स सूत्र दें और इसे एक उदाहरण से समझाएँ।
4. एकल पास और अर्ली रिटर्न लिखें।
5. जटिलता बताएँ और पूछे जाने पर बिटमास्क संस्करण प्रस्तुत करें।

मैंने प्रकाशन से पहले 20,000 यादृच्छिक बोर्डों पर ऊपर दिए गए कोड का परीक्षण एक साधारण पंक्ति, स्तंभ और बॉक्स जाँच के विरुद्ध किया, कुछ वैध और कुछ जानबूझकर तोड़े गए। इस तरह की त्वरित यादृच्छिक जाँच अभ्यास करते समय एक अच्छी आदत है।

संबंधित अभ्यास

जटिलता शब्दों के लिए हमारी Big O चीट शीट देखें, आगे क्या अभ्यास करना है इसके लिए LeetCode Blind 75 सूची देखें, और अभ्यास कैसे करें इसके लिए कोडिंग साक्षात्कार सहायक गाइड देखें।

कोड करते समय अपना दृष्टिकोण ज़ोर से बोलें। एक ट्रांसक्रिप्ट दिखाता है कि क्या आपने लिखने से पहले मुख्य अवलोकन बताया था। किसी भी लाइव मूल्यांकन में AI टूल्स पर नियोक्ता के नियमों का पालन करें।