שיחה:חידת מסע הפרש

"קיימים מספר מיליארדים של פתרונות שונים לבעיה, שמתוכם כ-122,000,000 הם מסלולים סגורים." - איך חישבו דבר כזה? --miniature 20:18, 17 בינואר 2007 (IST)

סביר להניח שיש שיטות אלגנטיות יותר אבל אפשר פשוט לבדוק את כל המסלולים בעזרת תוכנית מחשב פשוטה (backtracking). לא מדובר במספרים גדולים עבור מחשב (של עשרים השנים האחרונות).יבחוש 23:15, 17 בינואר 2007 (IST)

לא חושב. בבחרותי כתבתי תוכנית כזו, והרצתי אותה על VAX-750 ב-1984 (מישהו זוכר?) היא רצה 10 שעות מהפינה השמאלית העליונה, ובקושי מצאה פתרון אחד. למרות שעברו 23 שנים, קשה לי להאמין שתוכנית מחשב סרקה את כל מיליארדי האפשרויות. חגי אדלר 01:14, 18 בינואר 2007 (IST)

אם כך איך בכל זאת אנו סבורים שהנתונים הכתובים בערך אכן נכונים? --miniature 14:47, 18 בינואר 2007 (IST)

טעיתי, למרות שמעבר על מספר סביר של מליארדי אפשרויות היא באמת לא משימה קשה, מדובר פה על כמה מליארדי פתרונות - מרחב החיפוש גדול בהרבה. אתמול בלילה נסיתי להריץ קוד בדיקה ובאמת נרדמתי לפני שקבלתי תוצאה. טוב, אפשר לנסות להפעיל קצת את הראש או לחפש ברשת. עונג שבת של משהו?יבחוש 15:17, 18 בינואר 2007 (IST)

תודות לעוזי! "באופן כללי ספירת מסלולים המילטוניים היא בעיה קשה; במקרה הזה, נראה ש- Brendon McKay פתר אותה. עבור לוחות גדולים יותר, ידוע שמספר המסלולים עולה על $\ (1.3535)^{n^{2}}$: Kyek, Olaf; Parberry, Ian; Wegener, Ingo, Bounds on the number of knight's tours, Discrete Appl. Math. 74 (1997), no. 2, 171--181. עוזי ו. 18:50, 18 בינואר 2007 (IST)"

בקשר לנוסחה, אתה יכול להסביר בבקשה איך היא עובדת ומאיפה אתה מסיק שהיא נכונה? --miniature 22:20, 18 בינואר 2007 (IST)

הכנס להסבר בערך, של זה שכתב אותה. אני לא הצלחתי להכנס. עוזי, אפשר לקשר לקובץ בפורמט אחר? חגי אדלר 22:27, 18 בינואר 2007 (IST)

לפי http://mathworld.wolfram.com/KnightsTour.html ואתרים אחרים, המספר ~13 טריליון המופיע בערך הנוכחי הוא מספר המסלולים *הסגורים*. כך גם במאמר של McKay, שהוא זה שחישב לראשונה מספר זה: http://cs.anu.edu.au/techreports/1997/TR-CS-97-03.pdf המספר ~123 מיליון הנזכר בערך הוא מספר המסלולים העוברים קודם על מחצית אחת של הלוח (תת-לוח 4 על 8) ואחר כך על המחצית השנייה ( Maurice Kraitchik, Mathematical Recreations, p. 264)

ייחוס מסלול הפרש היוצר ריבוע קסם לאוילר הוא טעות נפוצה. אוילר לא יצר מעולם ריבוע קסם כזה. הראשון שיצר אותו היה אדם בשם William Beverley, שפירסם את תוצאתו בשנת 1848. ר', למשל, מי שמלין על טעות זו כאן: http://www.ktn.freeuk.com/cd.htm

הערת מזכיר התחרות

אני מזכיר להוסיף בדף שיחה קישורים לערכים שהוכחלו במהלך הכתיבה ושיתוף פעולה עם ויקיפדים אחרים, אם היה כזה. גילגמש • שיחה 22:17, 23 בנובמבר 2013 (IST)

גרף פרש, האנציקלופדיה המקוונת לסדרות של מספרים שלמים שדדשכ • שיחה • ו' בטבת ה'תשע"ד • 00:53, 9 בדצמבר 2013 (IST)

אליפות העולם בשחמט 2010 --Yoavd - שיחה 16:49, 18 בדצמבר 2013 (IST)

הזמנה לביקורת עמיתים

הערך בשלבי סיום. כרגע מה שבעיקר נשאר לי זה כתיבה של פסקת ההיסטוריה, דבר שיקח לי קצת זמן לעשות. בינתיים הייתי מאוד שמח לשמוע את דעתכם על שאר הערך. במיוחד חשוב לי לשמוע מהקורא ההדיוט על קריאותו של הערך: האם הוא ברור? האם הבנת (לפחות בערך) מה פירוש הבעיה בתורת הגרפים, איך פועלים האלגוריתמים השונים, איך עובד ריבוע הקסם? מי שרוצה לבצע הגהות יכול לעשות אותן ישירות בערך ואין צורך להגיד בדף השיחה. שדדשכ • שיחה • כ"ב בכסלו ה'תשע"ד • 01:44, 25 בנובמבר 2013 (IST)

חייבים קישורים חיצוניים. גיא - שיחה 13:30, 23 בדצמבר 2013 (IST)

"ריבוע הקסם של אוילר"

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

1. אין פתרון ריבוע קסם לבעיית הפרש - ב-2003 הדבר הוּכח.

2. הריבוע המוצג אינו ריבוע קסם -

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

3. הריבוע המוצג הוא ריבוע אותו יצר ויליאם בברלי ולא אוילר. לא נמצאה ראייה שאוילר יצר את הריבוע הנ"ל, ומנגד ישנן מקורות רציניים המראים שבברלי יצר אותו (הערת השוליים אינה מספקת בהקשר זה).

נעם דובב - שיחה 01:30, 7 בדצמבר 2013 (IST)

תודה על ההערה, תיקנתי. לגבי המחבר, מהן ה"ראיות הרציניות"? כל עוד הדבר לא מוכח בבירור, נראה לי שאין לויקיפדיה לנקוט עמדה בסוגיה זו. אנא הפנה. שדדשכ • שיחה • ד' בטבת ה'תשע"ד • 19:23, 7 בדצמבר 2013 (IST)

כאן יש מקור לעבודה של בברלי. עוזי ו. - שיחה 01:06, 9 בדצמבר 2013 (IST)

הערות שונות

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

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

ג. לא הצלחתי להבין את המילה המסומנת - את תוצאה זאת היינו מקבלים מהדבקת השורות הקיוניות - אולי קיצוניות?

ד. תיקנתי מספר תקלדות - אתה מוזמן לבדוק.

פרט להערות מעלה נראה לי שהערך כתוב בצורה מענינת, ובהחלט מקיף את הנושא מכל הכוונים. ברכות! --Yoavd - שיחה 09:45, 18 בדצמבר 2013 (IST)

א. תיקנתי.

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

ג. אכן.

תודה רבה על ההערות והתיקונים! שדדשכ • שיחה • ט"ז בטבת ה'תשע"ד • 00:07, 19 בדצמבר 2013 (IST)

שאלה על קיום מסלול המילטוני סגור בלוח ריבועי אי-זוגי מנוקב

האם ידוע משהו כללי על קיומו של מסלול המילטוני (של מהלכי פרש) בלוח ריבועי, בעל מספר אי זוגי של שורות/טורים, שהורחקה ממנו אחת המשבצות? מה שידוע לי: מסלול כזה קיים בלוחות בעלי מספר שורות 3, 5, 7, 9, 11 ועוד כמה. בלוח 3X3 יש להוציא את המשבצת האמצעית. בלוח 5X5 צריך להוציא מהלוח את אחת ממשבצות הפינה. בלוחות בעלי מספר שורות 7, 9, 11 ועוד כמה, אפשר לבנות מעגל המילטוני אם עוקרים מהלוח את משבצת האמצע או כל משבצת אחרת בעלת אותו צבע. האם ידוע משהו במקרה הכללי?--TalmonS - שיחה 21:35, 26 בספטמבר 2021 (IDT)טלמון

הייתי מתחיל את מסע הדילוגים בספרות מכאן: [1]. עוזי ו. - שיחה 22:39, 26 בספטמבר 2021 (IDT)

מסע דילוגים בספרות זה כמובן מצוין. TalmonS - שיחה 17:01, 27 בספטמבר 2021 (IDT)

הראו לי קישור למאמר העונה לשאלה זו: קישור. לדעתי, אפשר להוסיף לערך את המשפט המסכם ממאמר זה, וכן את הקישור למאמר. TalmonS - שיחה 19:16, 27 בספטמבר 2021 (IDT)