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

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

הרשימה כבר בהכנה, גדלה כל הזמן, רק תביאו מספר מאתגר.

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

בעיה שניתן לפתור באמצעות הדמיון, ואחר כך לבנות עבורה מכונה מבצעת, נותנת אפשרויות נוספות.

חבר'ה, כולם פותרים את זה בעזרת שיטת הניסוי-טעייה הקלאסית (recursion עם back-tracking) אבל לכשמנתחים את סיבוכיות הריצה מגיעים למסקנה שאסימפטוטית (כלומר במקום לוח של 8x8 עובדים עם לוח NxN כש N שואף לאינסוף) נוצר עץ שעומקו הוא מעריכי כלומר NP - אינו פתרון polynomial (מכאן ה P) כמו למשל לחשב אורך של מחרוזת (לינארי כאורך הקלט). בזמנו עוד בתיכון במגמת טכ"מ, בשפות כמו פרולוג (הפתרון הוא סה"כ 2 שורות) מצאתי משוואה שמראה מה מס' הפתרונות האפשריים לכל N (בעיה קומבינטורית לא פשוטה אבל גם לא נוראית) אבל למצוא אותם, כבר ב N שווה ל 15, המחשב מתחיל להזיע...
חבל שאנשים בורים מגיבים בלי לקרוא קצת באינטרנט... בכל אופן, ההשערה היא שכמו אלף-אפס מול "הרצף", אין באמת משהו באמצע וע"כ זוהי בעייה השייכת ל NP (כמו לחפש יציאה ממבוך) ולא הייתי ממליץ ל"התאבד" על פתרון הבעיה הנ"ל.
אגב, בסרט הנחמד gifted מזכירים את בעיית נוויה-סטוקס שלמרות שימושיה הרבים, גם היא עדיין לא נפתרה (מבחינת הסגירות של מרחב הפתרונות האפשריים, לא הנכונות עצמה של המשוואה).

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

שנעזר באינטרנט על מנת שאתה תוכל לכתוב את בליל השטויות שלך בטמקא, עכשיו אמור לי, האלגוריתם בתלמוד כתוב בפסאדו קוד?

בהתחלה כותבים שמדובר על הצבות בלוח רגיל 8x8,
ואז מדברים על זה ש"לוח המחשב גדל..."
(בקיצור אני משער שהכוונה ללוח של nxn ל-n גדול).
לא בטוח בכלל שזו לא בעיה NP שלמה, אבל זה כבר
קצת מעבר לכתבה של עמוד בynet.

צריך לחלק את התוצאה ב-2, כיוון שאחרי שמצאת 46 פתרונות, כל ה-46 האחרות הן תמונות מראה שלהן - מהצד השני של הלוח.

למעשה יד רק 23 פתרונות ליבה... שעל כל אחד מהם אפשר לסובב את הלוח ב-90 מעלות ולמצוא עוד "פיתרון"... אבל כיוון שסיבוב של הלוח ב-90 מעלות אינו חוקי בשח, בגלל הכיוון של השחור והלבן - יש 46 פתרונות.

זה ויכוח שלי מלפני 15 שנה עם מרצה בוק שמלמד מה שאמרו לו ובכלל לא חושב.

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

אם תוריד את האפשרות של שיקוף וסיבוב אתה נשאר עם 12.

מכל פתרון ניתן לייצר (לכל היותר) עוד 7 פתרונות ע"י סיבוב הלוח ב-90 מעלות 3 פעמים (מה שיוצר בסה"כ 4 פתרונות) ואח"כ הופכים את הלוח (כך ש-4 הפתרונות הופכים לעוד 4 פתרונות נוספים). לכן כל פתרון מייצר (לכל היותר) 7 פתרונות נוספים.
מבחינה מתמטית, ניתן לומר שכל פתרון שייך לקבוצת פתרונות ("מחלקת שקילות") הנוצרת על ידו באמצעות סיבובים והיפוך הלוח ומכילה לכל היותר 8 פתרונות שונים שקולים.
מסתבר שהפתרון המוצג בתמונה לעיל הוא סימטרי ולכן הוא מייצר רק עוד 3 פתרונות שונים, בלומר הוא שייך למחלקת שקילות המכילה 4 פתרונות שונים בלבד.
בנוסף לכך יש עוד 11 מחלקות שקילות שונות שכל אחת מכילה 8 פתרונות (לא סימטריים) שונים. לכן בסה"כ יש 92 = 8 * 11 + 4 פתרונות שונים.

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

אם עזרתי למישהו לזכות במיליון דולר, שיהיה לו לבריאות :-).

שחקתי לא מזמן במשחק שהייתי צריך לפתור את זה והצלחתי בלינלהסתכל על הפתרון באינטרנט

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

יש לי פיתרון יותר קל ממה שהוא מראה

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

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

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

ולא לוח גדול יותר, וגם אין שום אזכור לפרס של מיליון דולר.

איפה הלינק עם הצעת הפרס?