במחקר שהתפרסם בכתב העת של האגודה האמריקאית למתמטיקה השתמשו חוקרים בכלים מתורת הגרפים כדי לנתח תשבצי סודוקו באופן שיטתי וגילו שסודוקו מוביל לבעיות בלתי פתורות בתורת הגרפים
האם ניסית אי-פעם לפתור סודוקו, ולפתע תחושת ייאוש השתלטה עליך: "ואולי אין לו פתרון?". ואפילו אם מצאת פתרון, כיצד אתה יכול לדעת שזהו הפתרון היחיד? מה אם לפני חצי-שעה ארוכה היית כותב 5 במקום 3, אולי היית מגיע לפתרון שונה בתכלית?
שאלות אלו ואחרות מעסיקות את אגנס מ. הרצברג (Agnes M. Herzberg) ורם מורטי (M. Ram Murty), במאמרם "Sudoku Squares and Chromatic Polynomials", שפורסם בגיליון יוני-יולי 2007 של כתב העת Notices של האגודה האמריקאית למתמטיקה (American Mathematical Society, או AMS). הכותבים השתמשו בכלים מענף מתמטי הנקרא תורת-הגרפים (graph theory) כדי לנתח תשבצי סודוקו באופן שיטתי. החוקרים גם גילו שניתוח סודוקו מוביל לבעיות בלתי-פתורות בתורת הגרפים.
סודוקו כגרף צבוע
במסגרת התורה, "גרף" הוא כינוי לקבוצה של נקודות (או צמתים) המקושרות באמצעות קטעים (המכונים קשתות). גרפים גם מכונים לעיתים 'רשתות'. ניתן לחשוב על 81 המשבצות בתשבץ סודוקו כעל 81 צמתים בגרף. מעבר לזה, כל אחד מהמספרים 1-9 ייוצג באמצעות צבע שונה: 1 יהיה אדום, 2 כחול, 3 ירוק וכן הלאה; כך שכל צומת מקבל צבע, כמו שבכל משבצת יש מספר. הנה, יצרנו ייצוג גרפי לסודוקו, הבה נקרא לו "גרף סודוקו".
אם בתשבץ סודוקו שתי משבצות נמצאות באותה השורה, באותו הטור, או באותו ריבוע בגודל 3 על 3, אז נמתח קשת בין שני הצמתים שמייצגים אותם. מכיוון שעל-פי חוקי הסודוקו אין שני מספרים זהים באותה השורה, העמודה או המשבצת בגודל 3 על 3, אין שני צמתים בעלי אותו צבע המחוברים ביניהם.
(דוגמה תעזור להבהיר את הכוונה. נניח שלמספר 1 הצמדנו את הצבע אדום. אם שני צמתים אדומים יהיו מחוברים ביניהם, פירוש הדבר שיש שתי משבצות (הן הצמתים) עם המספר 1 (הוא הצבע אדום) באותה השורה או באותה העמודה או בתוך אותה משבצת בגודל 3 על 3 (כי כך הגדרנו חיבור באמצעות קשת), ודבר זה אסור על-פי חוקי הסודוקו).
בתורת הגרפים, צביעה של גרף, כך שלא יהיו קשתות בין צמתים בעלי אותו צבע, נקראת "צביעה נאותה" (proper coloring). פותרי הסודוקו בכל העולם, אפוא, מנסים להרחיב גרף צבוע-חלקית (בתשבץ המקורי יש משבצות ריקות, כלומר צמתים לא-צבועים) לגרף צבוע-נאות.
מה אפשר להוכיח על תשבצי סודוקו
עם האנלוגיה הזו בין גרפים לתשבצי סודוקו, הרצברג ומורטי יכלו להשתמש בכלים מתמטיים מתורת הגרפים בשביל להוכיח משפטים על סודוקו. לדוגמה, הם הוכיחו שמספר הדרכים להרחיב גרף צבוע-חלקית נתונות על-ידי פולינום. אם ערכו של הפולינום הוא 0 עבור תשבץ סודוקו מסוים, אז לתשבץ אין פתרון, אם הערך של הפולינום הוא 1, אז ישנו פתרון יחיד, וכך הלאה.
עוד מבחן שהזוג הוכיח, אותו הקורא יכול לבצע בעצמו: לתשבץ סודוקו נתון יהיה פתרון יחיד רק אם לפחות שמונה מספרים מתוך התשעה (1-9) יופיעו בתשבץ. אם רק שבעה מספרים מבין התשעה יופיעו, אז לתשבץ יהיו לפחות שני פתרונות אפשריים. וכאן הגענו לבעיה פתוחה במתמטיקה: "זה יהיה מרתק לגלות באילו תנאים ניתן להרחיב גרף צבוע-חלקית לצביעה ייחודית [נאותה]," כתבו הרצברג ומורטי.
כמה משבצות נתונות צריך
תשבצים מסוימים קשים יותר מאחרים, והקשים ביותר מכילים מספר גדול של משבצות ריקות. "מהו המספר המינימלי של משבצות נתונות, המבטיח שלתשבץ יש סידור שיוביל לפתרון ייחודי?" הרצברג ומורטי נתנו דוגמה לתשבץ עם פתרון ייחודי, שבו 17 משבצות נתונות. לכן, המספר המינימלי יהיה קטן או שווה ל-17. אבל מהו המספר המינימלי? זאת אין עוד איש יודע. אתה עשוי אולי לחשוב שלתשבץ עם מספר גדול יותר של משבצות נתונות יש סיכוי גדול יותר לפתרון יחיד. אין זה כך; הרצברג ומורטי נתנו דוגמה לתשבץ עם שני פתרונות אפשריים, ובו 29 משבצות נתונות.
השאלה הוכרעה בשנים שלאחר מכן: ב-2012 פרסמו גארי מקגווייר (Gary McGuire), בסטיאן טוגמן (Bastian Tugemann) וז'יל סיוויריו (Gilles Civario) הוכחה, שנסמכת על חיפוש ממצה במחשב, לכך שאין תשבץ סודוקו בעל 16 משבצות נתונות ופתרון יחיד, ולפיכך 17 הוא אכן המספר המינימלי. המאמר ראה אור ב-2014 בכתב העת Experimental Mathematics (לעיון במאמר).
ואם תהית מתי יגמר מחסן הסודוקו של העיתון המקומי שלך, החוקרים טוענים שיש כ-5.5 מיליארד תשבצי סודוקו שונים - מספיק בשביל להעסיק את חובבי הסודוקו ברחבי העולם, במשך זמן רב.
תורת הגרפים היא תחום צעיר יחסית ובו הרבה בעיות פתוחות. בדומה לתורת המספרים האלמנטרית, גם בה בעיות פתוחות קלות להבנה אך קשות לפתרון. כנראה שתגליות מתמטיות ימשיכו להלהיב את האנושות עוד שנים רבות.
הכתבה עודכנה באוקטובר 2026 כדי לשקף מחקר מ-2014 שהכריע כי המספר המינימלי של משבצות נתונות הוא 17.
שאלות ותשובות
איך אפשר לתאר תשבץ סודוקו בעזרת תורת הגרפים?
כל אחת מ-81 המשבצות מיוצגת כצומת בגרף וכל מספר מ-1 עד 9 מיוצג בצבע שונה. בין שני צמתים נמתחת קשת אם המשבצות שלהם באותה שורה, באותו טור או באותו ריבוע של 3 על 3, ופתרון תקין הוא צביעה נאותה, שבה אין צמתים מחוברים בעלי אותו צבע.
מה הוכיחו הרצברג ומורטי על מספר הפתרונות של תשבץ?
הם הוכיחו שמספר הדרכים להשלים תשבץ חלקי נתון על-ידי פולינום: אם ערכו 0 אין פתרון, ואם ערכו 1 יש פתרון יחיד. הם הוכיחו גם שתשבץ עם פתרון יחיד חייב להכיל לפחות שמונה מתוך המספרים 1-9.
האם יותר משבצות נתונות מבטיחות פתרון יחיד?
לא. החוקרים הציגו תשבץ עם 29 משבצות נתונות שיש לו שני פתרונות אפשריים, וגם תשבץ עם 17 משבצות נתונות בלבד שיש לו פתרון יחיד.
מהו המספר המינימלי של משבצות נתונות בתשבץ סודוקו עם פתרון יחיד?
בזמן פרסום המאמר ב-2007 הידוע היה רק שהמספר הוא לכל היותר 17. מחקר שפורסם ב-2014 הראה, בחיפוש ממצה במחשב, שאין תשבץ עם 16 משבצות נתונות ופתרון יחיד, ולכן המספר המינימלי הוא 17.
המאמר "Sudoku Squares and Chromatic Polynomials" ניתן לצפייה בגרסה מקוונת באתר ההודעות של ה-AMS.