Valid Sudoku

Q: מהי סיבוכיות הזמן של Valid Sudoku?

בלוח יש תמיד 81 תאים, ולכן שתי הגישות פועלות בזמן O(1) ומשתמשות בזיכרון O(1) . עבור סודוקו כללי בגודל n × n , הבדיקה במעבר אחד קוראת כל אחד מ־ n² התאים פעם אחת ושומרת 3n² דגלים: זמן וזיכרון של O(n²) .

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: 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

מהי סיבוכיות הזמן של Valid Sudoku?

בלוח יש תמיד 81 תאים, ולכן שתי הגישות פועלות בזמן O(1) ומשתמשות בזיכרון O(1). עבור סודוקו כללי בגודל n × n, הבדיקה במעבר אחד קוראת כל אחד מ־n² התאים פעם אחת ושומרת 3n² דגלים: זמן וזיכרון של O(n²).

האם לוח סודוקו תקין חייב להיות פתיר?

לא. כאן "תקין" פירושו רק שאף ספרה אינה חוזרת בשורה, בעמודה או בתיבה בגודל 3 × 3 בין התאים שמולאו. לוח יכול לעבור את הבדיקה הזאת ועדיין לא להיות פתיר. כדי לקבוע אם יש פתרון, נדרשת שיטת חיפוש כמו חזרה לאחור, וזו בעיה אחרת.

האם אפשר לפתור סודוקו תקין באמצעות מסכות ביטים?

כן. תן לכל שורה, עמודה ותיבה מספר שלם אחד, שבו ביט d מציין שהספרה d+1 כבר הופיעה. עבור תא מלא, אם 1 << d מבצע AND ומתקבל ערך שאינו אפס עם אחת משלוש המסכות שלו, הספרה חוזרת; אחרת, בצע לה 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