בסרטון - ואלס השחמט
איש אינו יודע בדיוק את מקורו של משחק השחמט, אולם האגדה מספרת כי הוא הומצא בהודו. לוח השחמט מורכב מ-64 משבצות הצבועות בשחור ולבן לסירוגין. המשחק מיועד לשני שחקנים, אחד משחק בכלים שחורים ואחד בלבנים. משחק השחמט, לוחו וכליו, משמשים עד היום תפאורה מושלמת לבעיות בתחומי המתמטיקה ומדעי המחשב.
בעיית שמונה המלכות היא דוגמה של בעיה קלאסית המשתמשת בלוח ובחוקי התנועה של המלכה. הפותר נדרש להעמיד שמונה מלכות על לוח שחמט, כך שבשום זוג שתי המלכות לא יאיימו זו על זו. במילים אחרות, אסור לשתי מלכות להיות באותה שורה, עמודה או אלכסון. מתמטיקאים רבים בחנו את הבעיה, ביניהם המתמטיקאי הגרמני החשוב בן המאה ה-19, קרל פרידריך גאוס (Gauss). בשנת 1874 הוכיח המתמטיקאי והאסטרונום ג'יימס גלשר (Glaisher) שיש לבעיה זו רק 12 פתרונות בסיסיים.
עוד בנושא
האם תצליחו לפתור את החידה שהטריפה את העולם?
החידה הפשוטה לילדים שמשגעת את המבוגרים
כמו במקרים רבים אחרים, בעיית שמונה המלכות הייתה רק "יריית פתיחה" למבול של בעיות דומות נוספות. בכמה אופנים אפשר להעמיד חמש מלכות על לוח חמש על חמש בלי שהן יאיימו זו על זו? ובהכללה, בכמה אופנים אפשר להעמיד כך n מלכות על לוח של nxn משבצות? הרחבה נוספת דורשת להציב כלים אחרים כך שלא יאיימו זה על זה. אפשר להעמיד, למשל, שמונה צריחים על לוח שחמט מבלי שאף אחד יאיים על אחר. אפשר לפתור בעיות דומות עם 14 רצים או 16 מלכים. בשנת 2004 פרסם מדען המחשב רוג'ר הואי הוכחה שהמספר הקטן ביותר של מלכות ופרשים יחדיו שאפשר להעמיד על לוח שחמט מבלי שאף כלי יאיים על כלי אחר הוא חמש מלכות וחמישה פרשים, והוא מצא 16 פתרונות לבעיה.
בעיות אחרות הציגו אתגר הפוך: להעמיד את המספר הקטן ביותר של כלים כך שיאיימו על כל המשבצות בלוח.
בעיית שמונה המלכות והרחבותיה השונות הן בעיות קלאסיות במדעי המחשב ומשתמשים בהן, בין השאר, לבחון אלגוריתמים חדשים שמפתחים המדענים. מדוע זכתה הבעיה הזאת דווקא לפרסום כה נרחב? ראשית, בשל הרקע התרבותי שעליה היא צמחה. המאה ה-19, טרום עידן המחשב, התאפיין בהתפוצצות של בעיות וחידות במשחקים נפוצים כמו קלפים ושחמט. משחקים אלו היו תפאורה מושלמת לספריו הקלאסיים של המתמטיקאי צ'ארלס דודג'סון, הידוע יותר בשמו הספרותי לואיס קרול - מחבר אליס בארץ הפלאות ואליס מבעד למראה, שהתפרסמו באותה תקופה. החידות שהתעוררו סביב המשחקים התאפיינו בכך שקל ופשוט לנסח אותן אך קשה לפתור אותן. בעיות אלו נדונו לא רק בחוגי האקדמיה, אלא גם בסלונים האירופאים והן צברו פופולריות רבה.
הפרס הגדול
ההתעניינות האקדמית בבעיית שמונה המלכות גברה מאז בעיקר בשל העובדה שאם מגדילים את הלוח באופן מתון (לינארי מכפלה בקבוע) הקושי למצוא את כל הפתרונות האפשריים במחשב גדל באופן מעריכי (אקספוננציאלי - לפי העלאה בחזקה).
לדוגמה, זמן הפתרון של לוח עם 100 משבצות לוקח בערך פי 33 זמן לפתור מאשר לוח הקטן ממנו בכחצי (לוח עם 49 משבצות) בעוד שזמן הפתרון של לוח הגדול ממנו פי 2 בקירוב (לוח עם 196 משבצות), הוא פי 657! עם כל כוח המחשוב שיש לנו כיום, עדיין לא מצאו את כל הפתרונות ללוח בגודל 28x28. הזמן שיידרש לפתור זאת במחשב חזק היום מוערך בכ-2000 שנה!
בעיות שהקושי שלפתור אותם גדל באופן מעריכי כשהבעיה עצמה גדלה רק באופן לינארי מכונה בעיית NP-Complete. ייעול פתרון בעיות NP-Complete היא אחת הבעיות החשובות ביותר במדעי המחשב. האם בכלל אפשר לפתור ביעילות בעיות NP-Complete ביחס לפתרון בעיות שהקושי לפתור אותן הוא לינארי? זו בעיה "פתוחה" ואחת משבע בעיות המילניום במתמטיקה. עד כה, איש לא מצא את התשובה לשאלה זו, ומי שיפתור אותה יזכה בפרס בשווי מיליון דולר מהמכון למתמטיקה ע"ש קליי.
על הסוס
קשר אחר בין מתמטיקה ושחמט עוסק בכלי המשונה ביותר במשחק הפרש. הפרש יכול לדלג מעל כלים אחרים ובמהלך אחד להגיע לאחת משמונה משבצות הנמצאות במרחק משבצת אחת באחד הכוונים (אופקי או אנכי) ושתי משבצות בכוון המאונך לו.
בעיית מהלכי הפרש שואלת האם יכול הפרש לדלג לכל משבצות הלוח כאשר הוא נוחת על כל משבצת רק פעם אחת? זו בעיה עתיקה ביותר, המוזכרת לראשונה בספרו של השחמטאי הערבי אבו זכריה יחיא אבן איברהים אל-חכים משנת 840. בספר מביא אל-חכים שני פתרונות אפשריים לבעיה.
מתמטיקאים רבים ניסו את כוחם בפתרון הבעיה, וגילו שיש לה הרבה מאוד פתרונות, אולם עד היום איש לא הצליח למצוא כמה בדיוק. רק בשנת 1997 הצליח המתמטיקאי האוסטרלי ברנדן מקיי לפתור בעיה מעט פשוטה יותר: הדורשת שהפרש ינחת במהלכו האחרון על המשבצת שבה התחיל את מסעו. מקיי מצא כי במקרה זה יש לבעיה לא פחות מ-1,658,420,855,433 (ללא ספירת פתרונות סימטריים). אגב, אותו מקיי התפרסם כאחד הסטטיסטיקאים שהפריכו מתמטית את טענותיו של מחבר הספר "הצופן התנ"כי" מייקל דרוזנין, בדבר רמזים לאירועים היסטוריים המוצפנים בדילוגי אותיות בתנ"ך.
מתמטיקאים הציעו שיטות רבות ומגוונות למציאת מסלולי הפרש. אחד הראשונים לעשות זאת היה המתמטיקאי והשחמטאי כריסטיאן היינריך פון-ורנסדורף במאה ה-19. לשיטתו, בכל מהלך פרש יש להעבירו למשבצת שמספר אפשרויות הדילוג הלאה ממנה הוא הקטן ביותר.
