קטגוריה: תכנות

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

השאלה לא היתה שאלה אלגוריתמית אלא מימושית, האלגוריתם הוסבר בבהירות רבה בשאלה, ורק נשאר לבחור שפה ולממש.
בניגוד למטלה הקודמת, בה בחרתי בפרולוג לפתרון של סודוקו, מה שלמרבה הצער שרף הרבה זמן והביא לתוצאות מפוקפקות, הפעם החלטתי ללכת על שפת הבית – הרי היא ג'אווה.
תוך בערך שעה העסק היה די כתוב, חוץ מזה שהוא לא עבד – לפעמים האלגוריתם נתקע בלולאה אינסופית, ולפעמים פתר את הבעיה בקלות.
בהתחלה הדפסתי את הלוח למסוף הטקסט, אבל מהר מאוד הבנתי שככה לא נגיע רחוק:
מאוד קשה לזהות תבניות שחוזרות על עצמן כשהן מודפסות כטקסט, וגם קשה לראת אם המלכות מאיימות אחת על השניה באלכסון.
החלטתי לעשות את מה שאני עושה טוב, וכתבתי ממשק שמציג סימולציה של האלגוריתם בג'אווה, ובעזרתו מצאתי את הבאגים.
חשבתי לעצמי, אם כבר הגעתי לכאן, נשקיע עוד קצת ונהפוך את זה ליותר שימושי:
הפכתי את הישום לאפלט, מה שמאפשר להריץ אותו גם בדפדפן, והוספתי כמה כפתורים ששולטים על הסימולציה.
התוצאה לפניכם:
נסו לשחק עם זה, בכל פעם שהוא נתקע הרקע הופך לאדום והוא מגריל מחדש.
שימו לב שאפשר לפתור עם זה גם לוחות גדולים מאוד.
עוד דברים שכדאי לשים אליהם לב זה שיש בעיה עם לוחות קטנים (כמה קטנים?), ושכל פעם הוא נותן פתרון אחר כי ההתחלה אקראית.
האפלט כאן, הקוד כלול בפנים (מי שרוצה את הקוד, שישמור את הJAR ויפרוש אותו עם WinZip או תוכנת זיפ אחרת, הקוד בפנים).