Valid Sudoku

+10

تحصل على لوحة سودوكو بحجم 9 × 9 باسم board، وهي قائمة من 9 سلاسل، تحتوي كل سلسلة منها على 9 أحرف، سلسلة واحدة لكل صف. كل حرف هو رقم من 1 إلى 9 أو . للدلالة على خلية فارغة. أعد true إذا لم يظهر أي رقم مرتين في صف أو عمود أو مربع بحجم 3 × 3، وfalse خلاف ذلك. يتم التحقق من الخلايا المملوءة فقط: ليس من الضروري أن تكون اللوحة قابلة للحل.

الدالة

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 سلاسل، يتكون كل منها من 9 أحرف، سلسلة واحدة في كل صف، والأرقام من 1 إلى 9 و. للخانة الفارغة
تُرجعboolean: صحيح إذا لم يتكرر أي رقم في أي صف أو عمود أو مربع 3 × 3، وخطأ خلاف ذلك

القيود

board.length == 9 و board[i].length == 9
board[i][j] هو رقم من 1 إلى 9 أو .
قد يكون من المستحيل إكمال اللوحة؛ المهم فقط هو التكرارات بين الخلايا المملوءة.

أمثلة

المدخلات: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
المخرجات: true
الشرح: الصف 4، عند العد بدءًا من 0، .74..89.3، يحتوي على الأرقام 7 و4 و8 و9 و3 مرة واحدة لكل منها، ولا تكرر أي مجموعة من المجموعات الـ26 الأخرى أي رقم أيضًا.

المدخلات: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
المخرجات: false
الشرح: يبدأ كلٌّ من الصف 0 والصف 7 بالرقم 3، لذا يحتوي العمود 0 على رقمي 3. لا يشتركان في صف أو مربع، لذا فإن فحص العمود وحده يكتشف ذلك.

المدخلات: board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
المخرجات: false
الشرح: العدد 5 في الصف 0، العمود 8 والعدد 5 في الصف 2، العمود 7 لا يشتركان في صف أو عمود، لكنهما يقعان في المربع العلوي الأيمن، لذا فالإجابة هي false.

سؤال إضافي

كيف ستتحقق من لوحة 16 × 16 تحتوي على مربعات 4 × 4 والرموز من 1 إلى 9 ومن A إلى G؟ ما الذي تصبح عليه صيغة المربع؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

ينتمي كل رقم إلى ثلاث مجموعات: صفه وعموده ومربع 3 × 3. من السهل فهرسة الصفوف والأعمدة؛ أما المربع فتكثر فيه الأخطاء. رقّم المربعات من 0 إلى 8 باستخدام (r / 3) * 3 + c / 3، وتتحقق جولة واحدة على الخلايا الـ81 من المجموعات الـ27 كلها.

تحقّق من كل صف وعمود ومربّع على حدة

الفكرة

تحدد القاعدة 27 مجموعة: 9 صفوف، و9 أعمدة، و9 مربعات. اجمع الخلايا التسع لكل مجموعة، وابحث عن رقم مكرر، مع تجاهل النقاط. يكون اللوح صالحًا بالضبط عندما لا تحتوي أي مجموعة على رقم مكرر.

تكشف علامة رصد لكل رقم عن أي تكرار ضمن الخلايا التسع. تُقرأ كل واحدة من الخلايا الـ81 مرةً واحدةً لكل مجموعة من مجموعاتها الثلاث: 243 قراءة، وهو مقدار ثابت من العمل. على لوح n × n، تبلغ كلفة الطريقة نفسها O(n²).

الخوارزمية

لكل i من 0 إلى 8، اجمع الصف i والعمود i والمربع i.
ركن المربع i يقع عند الصف 3 * (i / 3) والعمود 3 * (i % 3)؛ وتقع خليته k على بُعد k / 3 صفوف إلى الأسفل وk % 3 أعمدة إلى اليمين منه.
افحص كل مجموعة باستخدام أعلام تتبّع جديدة، مع تخطّي النقاط. إذا كان رقم قد وُسِم بالفعل، فأعِد false.
بعد المجموعات الـ27 كلها، أعِد true.

def has_repeat(cells):
    seen = set()
    for ch in cells:
        if ch == '.':
            continue
        if ch in seen:
            return True
        seen.add(ch)
    return False


def isValidSudoku(board):
    for r in range(9):
        if has_repeat(board[r][c] for c in range(9)):
            return False
    for c in range(9):
        if has_repeat(board[r][c] for r in range(9)):
            return False
    for top in (0, 3, 6):
        for left in (0, 3, 6):
            box = (board[top + i][left + j] for i in range(3) for j in range(3))
            if has_repeat(box):
                return False
    return True

مرور واحد باستخدام جدول للعناصر التي تمت رؤيتها لكل صف وعمود ومربع

الفكرة

زُر كل خلية مرة واحدة واطرح الأسئلة الثلاثة معًا. احتفظ بثلاثة جداول أعلام بحجم 9 × 9: يشير seenRow[r][d] إلى أن الرقم d+1 موجود مسبقًا في الصف r، وتعمل seenCol وseenBox بالطريقة نفسها.

تنتمي الخلية (r, c) إلى المربع (r / 3) * 3 + c / 3. يحدد الجزء الأول شريط المربعات الثلاثة، ويحدد c / 3 المربع داخل الشريط. تقع الخلية (4, 7) في المربع 1 * 3 + 2 = 5، أي المربع الأوسط على اليمين.

يعني العلم المضبوط مسبقًا أن الرقم يتكرر في تلك المجموعة. تُقرأ كل خلية مرة واحدة، وتحتوي الجداول على 243 علمًا: وقت وذاكرة ثابتان هنا، وO(n²) على لوحة n × n.

الخوارزمية

أنشئ seenRow وseenCol وseenBox، كلٌّ منها بحجم 9 × 9، واجعل جميع القيم false.
لكل خلية غير فارغة (r, c)، لتكن d هي رقمها ناقص 1، وb = (r / 3) * 3 + c / 3.
إذا كانت seenRow[r][d] أو seenCol[c][d] أو seenBox[b][d] مضبوطة، فأعِد false؛ وإلا فاضبطها جميعًا.
بعد آخر خلية، أعِد true.

def isValidSudoku(board):
    # seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
    seen_row = [[False] * 9 for _ in range(9)]
    seen_col = [[False] * 9 for _ in range(9)]
    seen_box = [[False] * 9 for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                continue
            d = int(ch) - 1
            b = (r // 3) * 3 + c // 3
            if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
                return False
            seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
    return True

أخطاء شائعة وحالات حدّية

حساب رقم المربع باستخدام r / 3 + c / 3. يعطي هذا القيم من 0 إلى 4 فقط، لذلك يشترك الموضعان (0, 3) و(3, 0) في الرقم نفسه رغم اختلاف مربعيهما، ويُبلَّغ عن وجود تكرار إذا وُجد فيهما رقمان 7.
القسمة باستخدام / في JavaScript أو Python 3 أو Lua، حيث إن 4 / 3 تساوي 1.33. قرّب الناتج إلى الأسفل.
اعتبار . قيمةً. تكون اللوحة الفارغة، التي يحتوي كل صف فيها على تسع نقاط، صالحة.
محاولة حل اللغز. لا يمكن إكمال الصف 0 الذي يحتوي على 12345678. مع وجود 9 أسفلَه في العمود 8، ومع ذلك لا يوجد أي تكرار: true.
تجاهل المربعات. شبكة كاملة يكون كل صف فيها هو الصف السابق بعد إزاحة عناصره خانةً واحدة إلى اليسار لا تحتوي على أي تكرار في الصفوف أو الأعمدة، بينما يحتوي كل مربع على تكرارات.

أسئلة شائعة3

ما التعقيد الزمني للتحقق من صحة السودوكو؟

تحتوي اللوحة دائمًا على 81 خلية، لذا يعمل كلا النهجين في زمن O(1) ويستخدمان ذاكرة O(1). بالنسبة إلى سودوكو عام بحجم n × n، يقرأ التحقق ذو المرور الواحد كل واحدة من الخلايا n² مرة واحدة، ويحتفظ بـ 3n² من علامات التحقق: زمن وذاكرة O(n²).

هل يجب أن تكون لوحة سودوكو صالحة قابلة للحل؟

لا. تعني «صالحة» هنا فقط أنه لا يتكرر أي رقم في صف أو عمود أو مربع 3 × 3 بين الخلايا المملوءة. قد تجتاز لوحة هذا الفحص ومع ذلك لا يكون لها حل. يتطلب تحديد إمكانية حلها إجراء بحث مثل التراجع، وهي مسألة مختلفة.

هل يمكن حلّ سودوكو صالحة باستخدام أقنعة البِتّات؟

نعم. خصّص عددًا صحيحًا واحدًا لكل صف وعمود ومربع، حيث تعني البتة d أن الرقم d+1 قد ظهر. بالنسبة إلى خلية ممتلئة، إذا كان ناتج AND بين 1 << d وأيٍّ من الأقنعة الثلاثة غير صفري، فهذا يعني أن الرقم مكرر؛ وإلا فطبّق OR عليه في الأقنعة الثلاثة. هذا يعني استخدام 27 عددًا صحيحًا بدلًا من 243 عَلَمًا.

def isValidSudoku(board):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]

الإخراج المتوقع

true