Valid Sudoku

Q: كيف تحدد المربع 3 × 3 الذي تنتمي إليه الخلية؟

باستخدام القسمة الصحيحة، يمثّل r / 3 مجموعة الصفوف (0 أو 1 أو 2)، ويمثّل c / 3 مجموعة الأعمدة. يرقّم (r / 3) * 3 + c / 3 المربعات من 0 إلى 8، من اليسار إلى اليمين ومن الأعلى إلى الأسفل. تقع الخلية (7, 1) في المربع 2 * 3 + 0 = 6 ، وهو المربع السفلي الأيسر.

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

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

متوسطالتجزئة

+10

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

الدالة

isValidSudoku(board: string-array) → boolean

boardstring-array: ٩ سلاسل نصية، يتكوّن كل منها من ٩ أحرف، سلسلة واحدة في كل صف، والأرقام من ١ إلى ٩ و. للخلية الفارغة
تُرجع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 الأخرى، لذا فالإجابة هي true.

المدخلات: 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 × 16، مع مربعات بحجم 4 × 4 والرموز من 1 إلى 9 ومن A إلى G. ما الأعداد في شفرتك التي تعتمد على حجم اللوحة، وإلى ماذا تصبح صيغة المربع؟

تلميحات

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

فُتح 0 من 3

الحل

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

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

الفكرة

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

الصف i هو board[i][0..8]، والعمود i هو board[0..8][i]. يبدأ المربع i من الصف 3 * (i / 3) والعمود 3 * (i % 3)، باستخدام القسمة الصحيحة، لذا يبدأ المربع 5 من الصف 3 والعمود 6. تقع خليته k على بُعد k / 3 صفوف إلى الأسفل وk % 3 أعمدة إلى اليمين من تلك الزاوية.

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

الخوارزمية

من أجل i من 0 إلى 8، اجمع الصف i والعمود i والمربع i، تسع خلايا لكل منها.
يبدأ المربع i عند top = 3 * (i / 3) وleft = 3 * (i % 3)؛ وتوجد خليته k في الصف top + k / 3 والعمود left + 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. يحدد الجزء الأول الشريط الذي يضم ثلاثة مربعات (الصفوف من 0 إلى 2 تعطي الشريط 0، والصفوف من 3 إلى 5 تعطي الشريط 1، والصفوف من 6 إلى 8 تعطي الشريط 2)، ويحدد c / 3 المربع داخل الشريط. تقع الخلية (4, 7) في المربع 1 * 3 + 2 = 5، وهو المربع الأوسط الأيمن.

لكل خلية مُعبّأة، إذا كانت أيٌّ من علاماتها الثلاث مضبوطة بالفعل، فهذا يعني أن الرقم يتكرر في تلك المجموعة، وعندها تُعيد false فورًا. وإلا، فاضبط العلامات الثلاث كلها. تُقرأ كل خلية مرة واحدة، وتحتوي الجداول على 243 علامة، لذا يظل الوقت والذاكرة ثابتين للوحة 9 × 9، ويكون التعقيد 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] تساوي true، فأعِد false.
وإلا، فاجعل القيم الثلاث كلها true. بعد الخلية الأخيرة، أعِد 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 فيهما. استخدم (r / 3) * 3 + c / 3.
القسمة باستخدام / في JavaScript أو Python 3 أو Lua، حيث تكون نتيجة 4 / 3 هي 1.33، وليست رقم مربع. استخدم Math.floor أو // أو math.floor.
التعامل مع . على أنه قيمة. يحتوي اللوح الفارغ على تسع نقاط في كل صف، وهو صالح.
محاولة حل اللغز. إذا كان الصف 0 هو 12345678. وكان هناك رقم 9 في موضع أدنى في العمود 8، فلا يمكن أبدًا ملء الخلية الأخيرة في الصف 0، ومع ذلك لا تكرر أي مجموعة رقمًا، لذا تكون الإجابة true.
التحقق من الصفوف والأعمدة دون التحقق من المربعات. شبكة مكتملة يكون كل صف فيها هو الصف السابق بعد إزاحته خانة واحدة إلى اليسار لا تحتوي على أي تكرار في أي صف أو عمود، بينما يحتوي كل مربع على تكرارات.

أسئلة شائعة4

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

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

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

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

كيف تحدد المربع 3 × 3 الذي تنتمي إليه الخلية؟

باستخدام القسمة الصحيحة، يمثّل r / 3 مجموعة الصفوف (0 أو 1 أو 2)، ويمثّل c / 3 مجموعة الأعمدة. يرقّم (r / 3) * 3 + c / 3 المربعات من 0 إلى 8، من اليسار إلى اليمين ومن الأعلى إلى الأسفل. تقع الخلية (7, 1) في المربع 2 * 3 + 0 = 6، وهو المربع السفلي الأيسر.

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

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

Python

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