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

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

בעיית שמונה המלכות היא דוגמה של בעיה קלאסית המשתמשת בלוח ובחוקי התנועה של המלכה. הפותר נדרש להעמיד שמונה מלכות על לוח שחמט כך שבשום זוג שתי המלכות לא יאיימו זו על זו. במילים אחרות, אסור לשתי מלכות להיות באותה שורה, עמודה או אלכסון. מתמטיקאים רבים בחנו את הבעיה, ביניהם המתמטיקאי הגרמני החשוב בן המאה ה-19, קרל פרידריך גאוס (Gauss). בשנת 1874 הוכיח המתמטיקאי והאסטרונום ג'יימס גלשר (Glaisher) שיש לבעיה זו רק 12 פתרונות בסיסיים.

אחד הפתרונות לבעיית שמונה המלכות, מתוך 12 הפתרונות הקיימים | איור: ד"ר יוסי אלרןאחד הפתרונות לבעיית שמונה המלכות, מתוך 12 הפתרונות הקיימים | איור: ד"ר יוסי אלרן

כמו במקרים רבים אחרים, בעיית שמונה המלכות הייתה רק "יריית פתיחה" למבול של בעיות דומות נוספות. בכמה אופנים אפשר להעמיד חמש מלכות על לוח חמש על חמש בלי שהן יאיימו זו על זו? ובהכללה, בכמה אופנים אפשר להעמיד כך n מלכות על לוח של nxn משבצות? הרחבה נוספת דורשת להציב כלים אחרים כך שלא יאיימו זה על זה. אפשר להעמיד, למשל, שמונה צריחים על לוח שחמט מבלי שאף אחד יאיים על אחר. אפשר לפתור בעיות דומות עם 14 רצים או 16 מלכים. בשנת 2004 פרסם מדען המחשב רוג׳ר הואי (Hui) הוכחה שהמספר הקטן ביותר של מלכות ופרשים יחדיו שאפשר להעמיד על לוח שחמט מבלי שאף כלי יאיים על כלי אחר הוא חמש מלכות וחמישה פרשים, והוא מצא 16 פתרונות לבעיה.

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

בעיית שמונה המלכות והרחבותיה השונות הן בעיות קלאסיות במדעי המחשב ומשתמשים בהן, בין השאר, לבחון אלגוריתמים חדשים שמפתחים המדענים. מדוע זכתה הבעיה הזאת דווקא לפרסום כה נרחב? ראשית, בשל הרקע התרבותי שעליה היא צמחה. המאה ה-19, טרום עידן המחשב, התאפיין בהתפוצצות של בעיות וחידות במשחקים נפוצים כמו קלפים ושחמט. משחקים אלו היו תפאורה מושלמת לספריו הקלאסיים של המתמטיקאי צ׳ארלס דודג'סון (Dodgson) הידוע יותר בשמו הספרותי לואיס קרול (Carroll): אליס בארץ הפלאות ואליס מבעד למראה, שהתפרסמו באותה תקופה. החידות שהתעוררו סביב המשחקים התאפיינו בכך שקל ופשוט לנסח אותן אך קשה לפתור אותן. בעיות אלו נדונו לא רק בחוגי האקדמיה, אלא גם בסלונים האירופאים והן צברו פופולריות רבה.

הפרס הגדול

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

לדוגמה, זמן הפתרון של לוח עם 100 משבצות לוקח בערך פי 33 זמן לפתור מאשר לוח הקטן ממנו בכחצי (לוח עם 49 משבצות) בעוד שזמן הפתרון של לוח הגדול ממנו פי 2 בקירוב (לוח עם 196 משבצות), הוא פי 657! עם כל כוח המחשוב שיש לנו כיום, עדיין לא מצאו את כל הפתרונות ללוח בגודל 28x28. הזמן שיידרש לפתור זאת במחשב חזק היום מוערך בכ-2000 שנה!

בעיה שהקושי לפתור אותה גדל באופן מעריכי כשמרחב הבעיה עצמה גדל רק באופן לינארי מכונה בעיית NP-Complete (הגדרה זו לא מדויקת והשתמשנו בה רק לצורך בהירות וקריאה רציפה). ייעול פתרון בעיות NP-Complete היא אחת הבעיות  החשובות ביותר במדעי המחשב. האם בכלל אפשר לפתור ביעילות בעיות NP-Complete ביחס לפתרון בעיות שהקושי לפתור אותן הוא לינארי? זו בעיה "פתוחה" ואחת משבע בעיות המילניום במתמטיקה. עד כה, איש לא מצא את התשובה לשאלה זו, ומי שיפתור אותה יזכה בפרס בשווי מיליון דולר מהמכון למתמטיקה ע״ש קליי (Clay Mathematical Institute).

הכלי המשונה ביותר במשחק. המשבצות שהפרש יכול לנוע אליהן מסומנות ב-x | איור: ד"ר יוסי אלרןהכלי המשונה ביותר במשחק. המשבצות שהפרש יכול לנוע אליהן מסומנות ב-x | איור: ד"ר יוסי אלרן

על הסוס

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

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

מתמטיקאים רבים ניסו את כוחם בפתרון הבעיה, וגילו שיש לה הרבה מאוד פתרונות, אולם עד היום איש לא הצליח למצוא כמה בדיוק. רק בשנת 1997 הצליח המתמטיקאי האוסטרלי ברנדן מקיי (McKay) לפתור בעיה מעט פשוטה יותר: הדורשת שהפרש ינחת במהלכו האחרון על המשבצת שבה התחיל את מסעו. מקיי מצא כי במקרה זה יש לבעיה לא פחות מ-1,658,420,855,433 (ללא ספירת פתרונות סימטריים). אגב, אותו מקיי התפרסם כאחד הסטטיסטיקאים שהפריכו מתמטית את טענותיו של מחבר הספר "הצופן התנ"כי" מייקל דרוזנין, בדבר רמזים לאירועים היסטוריים המוצפנים בדילוגי אותיות בתנ"ך.

מתמטיקאים הציעו שיטות רבות ומגוונות למציאת מסלולי הפרש. אחד הראשונים לעשות זאת היה המתמטיקאי והשחמטאי כריסטיאן היינריך פון-ורנסדורף (von Warnsdorf) במאה ה-19. לשיטתו, בכל מהלך פרש יש להעבירו למשבצת שמספר אפשרויות הדילוג הלאה ממנה הוא הקטן ביותר.

אחד הפתרונות לחידת מסלולי הפרש | מקור: ויקיפדיה, נחלת הכלל, Tobias Pfanner אחד הפתרונות לחידת מסלולי הפרש | מקור: ויקיפדיה, נחלת הכלל, Tobias Pfanner 

פיות וגמלים

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

כך, למשל, שחמט ג’אנגי (Janggi) הוא גירסה קוריאנית של המשחק עם חוקים מעט שונים. שחמט אליס – הוא גירסה שמשחקים על שני לוחות. שחמט פיות משחקים עם כלים מסוגים חדשים, חלקם כלי משחק עתיקים וחלקם המצאות מודרניות. דוגמה לכלי משחק כזה הוא הארכיבישוף, המכונה גם נסיכה וקרדינל. זהו שילוב בין רץ ופרש והשחקן יכול לבחור בכל מהלך האם לנוע עם הכלי כמו רץ או כמו פרש. הגמל הוא כלי שזז קצת כמו פרש, אלא שהוא קופץ משבצת אחת בכוון אחד (אופקי או אנכי) ושלוש משבצות לכיוון המאונך לו (קפיצות 1,3 במקום קפיצה 1,2 של פרש).

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

4 תגובות

  • shirbi

    "בעיות שהקושי שלפתור אותם גדל

    "בעיות שהקושי שלפתור אותם גדל באופן מעריכי כשהבעיה עצמה גדלה רק באופן לינארי מכונה בעיית NP-Complete"
    זו הגדרה שגויה לבעיה NP שלמה. ההגדרה הנכונה ארוכה מדי בשביל תגובה כאן :-)

  • יוסי

    נכון - אבל במסגרת כתבה פופולרית זה הכי טוב שאפשר...

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

  • shirbi

    תודה :-)

    תודה :-)
    האם מישהי מהבעיות שהזכרת בכתבה באמת ידועה כבעיה NP שלמה, או שרק לא ידוע עבורן שום פיתרון פחות מאקספלוננציאלי?

  • יוסי

    לא קשה למצוא פתרונות לבעיות הללו...

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