8 המלכות: נסו לפתור את חידת מיליון הדולר

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

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

מדובר למעשה בבעיה מתמטית שפורסמה לראשונה ב-1850 וכבר נמצא לה פתרון. בסך הכול יש 4,426,165,368 הצבות אפשריות למלכות על הלוח, אך רק 92 פתרונות אפשריים.

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

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

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

השאלה בה היא למעשה: האם כל בעיה שניתן לאשר בקלות שהתשובה לפתרון שלה נכונה - האם גם קל לפתור אותה? למשל, אם קל (לפחות באמצעות מחשבון) לדעת כי מכפלת המספרים הראשוניים 839 ו-967 שווה 811,313 האם קל באותה מידה לדעת כי המחלקים של 811,313 הם 839 ו-967?

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