תוכנה לפתרון חידת המלכות

תוכנה לפתרון חידת המלכות

הודעהעל ידי אורי אבן-חן » 19/11/2011 09:30

היי אנשים,

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

http://chessqueens.sourceforge.net/

פרטים נוספים על התוכנה אפשר לראות באתר הבא:
http://sourceforge.net/projects/chessqueens/

התוכנה כתובה ב-Java ומשתמשת ב-GWT של גוגל, כך שהאתר עובד ב-Javascript. הקומפיילר של GWT מתרגם מ-Java ל-Javascript. אפשר להוריד את קוד המקור מהאתר.

אני מחפש תמונה חופשית של צריח בגודל המתאים (או בגודל דומה), עם רקע לבן, שאפשר להשתמש בה בלי להסתבך עם זכויות יוצרים. למי שיש תמונה כזאת, תנו קישור או תשלחו לי לכתובת [email protected] .

בברכה,
אורי אבן-חן.
[email protected]
אורי אבן-חן
משתמש מתחיל
 
הודעות: 7
הצטרף: 19/11/2011 07:23

Re: תוכנה לפתרון חידת המלכות

הודעהעל ידי אורי אבן-חן » 19/11/2011 09:43

טוב, בינתיים מצאתי תמונה של צריח ואני אחליף את התמונה של הצריח באתר.

אורי אבן-חן.
אורי אבן-חן
משתמש מתחיל
 
הודעות: 7
הצטרף: 19/11/2011 07:23

Re: תוכנה לפתרון חידת המלכות

הודעהעל ידי Oded Ross » 19/11/2011 17:29

תוכנה ממש נחמדה, מומלץ להעיף מבט.
תסתכלו לדוגמה על הפתרון לחידת המלכות בלוח של 20*20 בדרישה של לפחות 4 משבצות ביניהן :)
The rest of the game is no fairy tale, but will be appreciated by those who call chess a war game. Unlike the high level combative artistry of top players, this game captures the true nature of war: sloppy, senseless tragedy, chaos and stupidity.
Oded Ross
מנהל
 
הודעות: 8787
הצטרף: 30/11/2004 23:07
מיקום: קרית-אונו

Re: תוכנה לפתרון חידת המלכות

הודעהעל ידי אורי אבן-חן » 19/11/2011 21:08

יש פתרונות מעניינים. לדוגמה בלוח של 16*16 עם מרחק מינימלי של 4 משבצות בין המלכות, יש רק 2 פתרונות (כמובן סימטריים). בלוח של 10*10 עם מרחק מינימלי של 3 משבצות בין המלכות (או ביטול מהלך פרש, זה אותו הדבר), יש 4 פתרונות. בלוח שחמט רגיל של 8*8 עם מלכות ללא דרישות נוספות, יש כמובן 92 פתרונות, ועם צריחים יש 40320 פתרונות, שזה כמובן 8! (8 עצרת).

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

בלוח של 2*2 או 3*3 עם מלכות אין פתרונות, ובלוח של 4*4 יש 2 פתרונות. בלוח של 5*5 יש 10 פתרונות, ובלוח של 6*6 יש רק 4 פתרונות.
אורי אבן-חן
משתמש מתחיל
 
הודעות: 7
הצטרף: 19/11/2011 07:23

Re: תוכנה לפתרון חידת המלכות

הודעהעל ידי שמוליק » 19/11/2011 23:34

בהחלט נחמד מאוד .
שאלה - ככל הלוח גדל , מן הסתם אנו מצפים ליותר פתרונות . למרות זאת בלוח של 6*6 יש פחות פתרונות בבעיית המלכות מאשר בלוח 5*5 . יש הסבר לכך ?
שמוליק
משתמש חסר חיים
 
הודעות: 2846
הצטרף: 01/12/2004 21:32
מיקום: תל אביב

Re: תוכנה לפתרון חידת המלכות

הודעהעל ידי אורי אבן-חן » 24/11/2011 23:24

בלוחות גדולים באמת ככל שהלוח גדל יש יותר פתרונות, אבל בלוחות קטנים (עד 6*6) זה לא תמיד נכון. צריך לזכור שבלוח גדול יותר יש גם יותר מלכות, ולכן יש יותר הגבלות על המיקום של כל מלכה. בצריחים אמנם יש תמיד יותר פתרונות בלוח גדול יותר, לפי הנוסחה n!, אבל במלכות לא תמיד יש יותר פתרונות בלוח גדול בהשוואה ללוח קטן יותר. לדוגמה בלוח של 2*2 ו-3*3 אין בכלל פתרונות, למרות שבלוח של 1*1 יש פתרון אחד.

למי שמתעניין, בויקיפדיה האנגלית יש מאמר מעניין על חידת המלכות:
http://en.wikipedia.org/wiki/Eight_queens_puzzle
אורי אבן-חן
משתמש מתחיל
 
הודעות: 7
הצטרף: 19/11/2011 07:23

Re: תוכנה לפתרון חידת המלכות

הודעהעל ידי אורי אבן-חן » 24/11/2011 23:48

אני חושב שבמקרה של לוח בגודל 6*6, התשובה היא שבלוח בגודל 5*5 שני האלכסונים תמיד מאויימים על-ידי מלכות בכל הפתרונות, ולכן לא ניתן להרחיב את הלוח ל-6*6 ולהציב מלכה בפינה. לכן בכל הפתרונות בלוח בגודל 6*6 אין מלכות בפינה. בלוח בגודל 4*4 לעומת זאת, האלכסונים לא מאויימים, ולכן בלוח בגודל 5*5 ניתן להציב מלכה בפינה, ואלה 80% מהפתרונות (8 מתוך 10 פתרונות).

עם צריחים לעומת זאת, אין בעיה, וניתן להציב צריח בכל מקום ולפתור את הבעיה ברדוקציה. לכן מספר הפתרונות בצריחים הוא תמיד n כפול מספר הפתרונות בלוח בגודל n-1.
אורי אבן-חן
משתמש מתחיל
 
הודעות: 7
הצטרף: 19/11/2011 07:23

Re: תוכנה לפתרון חידת המלכות

הודעהעל ידי שמוליק » 25/11/2011 12:40

תודה אורי .
אכן מעניינת מאוד העובדה שבלוחות של 4*4 ו-6*6 אין מלכות באלכסונים הראשיים .
שמוליק
משתמש חסר חיים
 
הודעות: 2846
הצטרף: 01/12/2004 21:32
מיקום: תל אביב


חזור אל תוכנות שחמט

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד