כיצד פותרין? סודוקו, תורת הגרפים ובעיות פתוחות במתמטיקה

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

תשבץ סודוקו פתור. המספרים בשחור הם הנתונים.

האם ניסית אי-פעם לפתור סודוקו, ולפתע תחושת ייאוש השתלטה עליך: “ואולי אין לו פתרון?”. ואפילו אם מצאת פתרון, כיצד אתה יכול לדעת שזהו הפתרון היחיד? מה אם לפני חצי-שעה ארוכה היית כותב 5 במקום 3, אולי היית מגיע לפתרון שונה בתכלית?

שאלות אלו ואחרות מעסיקות את אגנס מ. הרצברג (Herzberg) ורם מורטי (Murty), במאמרם “Sudoku Squares and Chromatic Polynomials”, שפורסם בגליון האחרון של האגודה האמריקאית למתמטיקה (ה-AMS). הכותבים השתמשו בכלים מענף מתמטי הנקרא תורת-הגרפים כדי לנתח תשבצי סודוק באופן שיטתי. החוקרים גם גילו שניתוח סודוקו מוביל לבעיות בלתי-פתורות בתורת הגרפים.

במסגרת התורה, “גרף” הוא כינוי לקבוצה של נקודות (או צמתים) המקושרות באמצעות קטעים (המכונים קשתות). גרפים גם מכונים לעיתים 'רשתות'. ניתן לחשוב על 81 המשבצות בתשבץ סודקו, כעל 81 צמתים בגרף. מעבר לזה, כל אחד מהמספרים 1-9 ייוצג באמצעות צבע שונה: 1 יהיה אדום, 2 כחול, 3 ירוק וכן הלאה; כך שכל צומת מקבל צבע, כמו שבכל משבצת יש מספר. הנה, יצרנו ייצוג גרפי לסודוקו, הבה נקרא לו “גרף סודוקו”. אם בתשבץ סודוקו, שתי משבצות נמצאות באותה השורה, באותו הטור, או באותו ריבוע בגודל 3 על 3, אז נמתח קשת בין שני הצמתים שמייצגים אותם. מכיוון שעל-פי חוקי הסודוקו, אין שני מספרים זהים באותה השורה, העמודה או המשבצת בגודל 3 על 3, אין שני צמתים בעלי אותו צבע המחוברים ביניהם. (דוגמא תעזור להבהיר את הכוונה. נניח שלמספר 1 הצמדנו את הצבע אדום. אם שני צמתים אדומים יהיו מחוברים ביניהם, פירוש הדבר שיש שתי משבצות (הן הצמתים) עם המספר 1 (הוא הצבע אדום) באותה השורה או באותה העמודה או בתוך אותה משבצת בגודל 3 על 3 (כי כך הגדרנו חיבור באמצעות קשת), ודבר זה אסור על-פי חוקי הסודוקו).

בתורת הגרפים, צביעה של גרף, כך שלא יהיו קשתות בין צמתים בעלי אותו צבע, נקראת “צביעה נאותה”. פותרי הסודוקו בכל העולם, אפוא, מנסים להרחיב גרף צבוע-חלקית (בתשבץ המקורי יש משבצות ריקות, כלומר צמתים לא-צבועים) לגרף צבוע-נאות.

עם האנלוגיה הזו בין גרפים לתשבצי סודוקו, הרצברג ומורטי יכלו להשתמש בכלים מתמטיים מתורת הגרפים בשביל להוכיח משפטים על סודוקו. לדוגמא, הם הוכיחו שמספר הדרכים להרחיב גרף צבוע-חלקית נתונות על-ידי פולינום. אם ערכו של הפולינום הוא 0 עבור תשבץ סודוקו מסוים, אז לתשבץ אין פתרון, אם הערך של הפולינום הוא 1, אז ישנו פתרון יחיד, וכך הלאה. עוד מבחן שהזוג הוכיח, אותו הקורא יכול לבצע בעצמו: לתשבץ סודוקו נתון יהיה פתרון יחיד רק אם לפחות שמונה מספרים מתוך התשעה (1-9) יופיעו בתשבץ. אם רק שבעה מספרים מבין התשעה יופיעו, אז לתשבץ יהיו לפחות שני פתרונות אפשריים. וכאן הגענו לבעיה פתוחה במתמטיקה: “זה יהיה מרתק לגלות באילו תנאים ניתן להרחיב גרף צבוע-חלקית לצביעה ייחודית [נאותה],” כתבו הרצברג ומורטי.

תשבצים מסוימים קשים יותר מאחרים, והקשים ביותר מכילים מספר גדול של משבצות ריקות. “מהו המספר המינמלי של משבצות נתונות, המבטיח שלתשבץ יש סידור שיוביל לפתרון ייחודי?” הרצברג ומורטי נתנו דוגמא לתשבץ עם פתרון ייחודי, שבו 17 משבצות נתונות. לכן, המספר המינימלי יהיה קטן או שווה ל-17. אבל מהו המספר המינימלי? זאת אין עוד איש יודע. אתה עשוי אולי לחשוב שלתשבץ עם מספר גדול יותר של משבצות נתונות יש סיכוי גדול יותר לפתרון יחיד. אין זה כך; הרצברג ומורטי נתנו דוגמא לתשבץ עם שני פתרונות אפשריים, ובו 29 משבצות נתונות.

ואם תהית מתי יגמר מחסן הסודוקו של העיתון המקומי שלך, החוקרים טוענים שיש כ-5.5 ביליון תשבצי סודוקו שונים – מספיק בשביל להעסיק את חובבי הסודוקו ברחבי העולם, במשך זמן רב.

תורת הגרפים היא תחום צעיר יחסית ובו הרבה בעיות פתוחות. בדומה לתורת המספרים האלמנטרית, גם לו בעיות פתוחות קלות להבנה אך קשות לפתרון. כנראה שתגליות מתמטיות ימשיכו להלהיב את האנושות עוד שנים רבות.

המאמר Sudoku Squares and Chromatic Polynomials” ניתן לצפיה בגרסא מקוונת באתר ההודעות של ה-AMS.