Valid Sudoku
מקבלים לוח סודוקו בגודל 9 × 9 בתור board, רשימה של 9 מחרוזות, שכל אחת מהן מכילה 9 תווים, מחרוזת אחת לכל שורה. כל תו הוא ספרה מ-1 עד 9 או . עבור תא ריק. החזירו true אם אף ספרה לא מופיעה פעמיים באותה שורה, באותה עמודה או באותו ריבוע בגודל 3 × 3, ו-false אחרת. בודקים רק את התאים המלאים: לא חייב להיות אפשר לפתור את הלוח.
פונקציה
- boardstring-array
- 9 מחרוזות בנות 9 תווים, אחת בכל שורה, הספרות 1 עד 9 ו־. עבור תא ריק
- מחזירהboolean
- אמת אם אין שורה, עמודה או תיבה בגודל 3 × 3 שחוזרת על ספרה, אחרת שקר
אילוצים
board.length == 9וגםboard[i].length == 9board[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. אילו מספרים בקוד שלכם תלויים בגודל הלוח, ומה תהיה נוסחת התיבה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
ציינו את הקבוצות שעליהן הכללים מדברים. כמה קבוצות יש, ואיזה סוג הכי קשה לאנדקס?
התא בשורה
rובעמודהcנמצא בדיוק בתיבה אחת. בחלוקה שלמה,r / 3מציין באיזו קבוצת שורות מתוך שלוש הוא נמצא, ו-c / 3מציין באיזו קבוצת עמודות מתוך שלוש. שלבו את שניהם למספר אחד בין 0 ל-8.בקר בכל תא פעם אחת. שמור דגל ביקור לכל זוג של (שורה, ספרה), (עמודה, ספרה) ו-(תיבה, ספרה). תא מלא שהדגל שלו כבר מסומן באחת משלוש הקבוצות שלו הוא חזרה.
פתרון
כל ספרה שייכת לשלוש קבוצות בו־זמנית: לשורה שלה, לעמודה שלה ולתיבה שלה בגודל 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. - עבור כל קבוצה, עבור על התאים שלה עם דגלי seen חדשים, ודלג על נקודות.
- אם ספרה כבר סומנה, החזר
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); דלגו עליו אם הוא מכיל נקודה. - נסמן את הספרה פחות 1 ב־
d, ואת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. - התייחסות אל
.כאל ערך. בלוח ריק יש תשע נקודות בכל שורה, והוא תקין. - ניסיון לפתור את החידה. כאשר
12345678.היא שורה 0 ויש 9 בהמשך למטה בעמודה 8, לעולם אי אפשר למלא את התא האחרון בשורה 0, ובכל זאת אין קבוצה שבה ספרה חוזרת, ולכן התשובה היאtrue. - בדיקת שורות ועמודות אך לא תיבות. בלוח מלא שבו כל שורה מוזזת מקום אחד שמאלה ביחס לשורה הקודמת, אין חזרות באף שורה או עמודה, בעוד שבכל תיבה יש חזרות.
שאלות נפוצות4
מהי סיבוכיות הזמן של Valid Sudoku?
בלוח יש תמיד 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