המתמטיקה של הסודוקו

עודכן ב־2026-10-05

ריבוע לטיני עם ריבועים פנימיים

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

מקורות: Wikipedia: Latin square

כמה לוחות יש

ברטרם פלגנהאואר (Bertram Felgenhauer) ופרייזר ג'רוויס (Frazer Jarvis) ספרו את הלוחות המלאים בגודל 9×9 ב־2005: יש 6,670,903,752,021,072,936,960 לוחות, כ־6.67 × 10²¹. רבים מהם הם אותו לוח בתחפושת. אם סופרים שני לוחות כאחד כאשר אפשר להפוך אחד לשני באמצעות החלפת תוויות הספרות, סיבוב או שיקוף, או סידור מחדש של שורות ועמודות בדרכים ששומרות על תקינות הלוח, נשארים 5,472,730,538 לוחות שונים במהותם, מספר שחישבו אד ראסל (Ed Russell) ופרייזר ג'רוויס.

מקורות: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

המינימום של 17 רמזים

אין סודוקו רגיל בגודל 9×9 עם 16 נתונים או פחות שיש לו פתרון אחד בדיוק. גארי מקגווייר (Gary McGuire), בסטיאן טוגמן (Bastian Tugemann) וז'יל סיוואריו (Gilles Civario) הראו זאת באמצעות חיפוש ממוחשב ממצה והכריזו על התוצאה בינואר 2012. שבעה־עשר הם המינימום, ולא ערובה: ללוחות רבים עם 17 נתונים עדיין יש יותר מפתרון אחד.

מקורות: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

סודוקו כצביעת גרפים

מציירים קודקוד אחד לכל אחד מ־81 התאים ומחברים שני קודקודים בכל פעם שהתאים שלהם נמצאים באותה שורה, עמודה או ריבוע. לגרף הסודוקו הזה יש 810 קשתות, ולכל קודקוד יש בדיוק 20 שכנים. פתרון החידה פירושו הרחבת הצביעה שנקבעת על ידי הנתונים, כך שקודקודים מחוברים לעולם לא יהיו באותו צבע. נדרשים לפחות תשעה צבעים, משום שכל שורה, עמודה וריבוע הם קבוצה של תשעה קודקודים שכולם מחוברים זה לזה, וכל לוח מלא מראה שתשעה צבעים מספיקים.

מקורות: Wikipedia: Sudoku graph

קשה במקרה הכללי, מהיר ב־9×9

עבור לוחות סודוקו שגודלם יכול לגדול ללא הגבלה (n²×n² עם ריבועים בגודל n×n), ההכרעה אם אפשר להשלים לוח מלא בחלקו היא בעיה NP-שלמה, תוצאה שטקאיוקי יאטו (Takayuki Yato) וטקאהירו סטה (Takahiro Seta) פרסמו ב־2003. תוכנות מחשב יעילות פותרות בדרך כלל חידות רגילות בגודל 9×9 בשבריר שנייה, אם כי הזמן תלוי בתוכנה, במחשב ובחידה.

מקורות: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

ראו גם

מקורות

כל המאמרים →