00
עדכונים

מנוי במייל

קבלת עדכונים על רשומות חדשות ישירות לתיבת האמייל
יש להזין אימייל תקין על מנת להרשם לעדכונים
ברגעים אלו נשלח אליך אימייל לאישור/ביטול ההרשמה
*שים/י לב, מרגע עשית מנוי, כותב/ת הבלוג יוכל לראות את כתובת האמייל שלך ברשימת העוקבים.
X

{ [ ( בניית עזר ) ] } - מתמטיקה, תכנות, סיכומים לבחינות הבגרות ואקסל

<<<<
 מפת האתר -  כאן

   מתמטיקה 
   ונושאים 
   נוספים 
 
משפטים, נוסחאות ומתמטיקאים על ציר הזמן  תורת המספרים  תכנות C++/C  קומבינטוריקה  מתמטיקה/EXCEL  אסטרונומיה

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

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

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

רשומות קשורות:
מתמטיקה על לוח השחמט - חידות שחמט קומבינטוריות
ריבוע הקסם של אוילר כפתרון לחידת מסעי הפרש

 


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

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

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


הפתרון המצורף מטה, בשפת C, מובא באדיבותו של מר בנימין גולובטי.

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

לחידה זו ישנם 12 פתרונות ייחודיים, ו-92 פתרונות בסה"כ הנוצרים
משיקופים אפקיים, שיקופים אנכיים או סיבוב של לוח השחמט
ב- 1800,900 או 2700.

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

קישורים:

הכללת חידת 8 המלכות ללוח שחמט כמטריצה ריבועית מסדר N

תיאור גרפי של 12 הפתרונות הייחודיים



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



התכנית המצורפת מדפיסה את כל 92 הפתרונות.

דוגמה לפתרון ייחודי מתוך 12 הפתרונות הקיימים: 46831752 .
פירוש: המלכה הראשונה מוצבת בעמודה הראשונה בשורה הרביעית.
         המלכה השנייה מוצבת בעמודה השנייה בשורה השישית.

         וכן הלאה:
         המלכה השלישית מוצבת בעמודה השלישית בשורה השמינית.
         המלכה הרביעית מוצבת בעמודה הרביעית בשורה השלישית.
         המלכה החמישית מוצבת בעמודה החמישית בשרה הראשונה.
         המלכה השישית מוצבת בעמודה השישית בשורה השביעית.
         המלכה השביעית מוצבת בעמודה השביעית בשורה החמישית.
         המלכה השמינית מוצבת בעמודה השמינית בשורה השנייה.


שיקוף אנכי, שיקוף אפקי וסיבובים של הפתרון על לוח השחמט:
הפתרון לאחר סיבוב לוח השחמט 900 ימינה: 41582736.
הפתרון לאחר סיבוב לוח השחמט 1800 ימינה: 74286135.
הפתרון לאחר סיבוב לוח השחמט 2700 ימינה: 36271485.

הפתרון לאחר שיקוף אפקי של לוח השחמט (מימין לשמאל): 25713864.

הפתרון לאחר שיקוף אנכי של לוח השחמט (מלמעלה למטה): 64158273.

 

רשימת כל 92 הפתרונות מצורפת מתחת לצילומי המסך של התכנית.
תאי המטריצה ממסופרים החל מ-0, כנהוג בשימוש במערכים בשפות תכנות,
עד 7. הפינה השמאלית התחתונה של לוח השחמט מיוצגת באמצעות
הזוג הסדור (0,0).

 

 

פלט התכנית:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ההערות בגוף התכנית כקובץ טקסט:

המלכה הנוכחית מיוצגת ע"י a ואילו המלכה שכבר הצבנו על הלוח מיוצגת ע"י ind
הבדיקה מתבצעת על הלוח ששורותיו ממוספרות מ-0 עד 7

כל עוד לא חרגנו מגבולות לוח השחמט

בדיקה האם 8 המלכות סודרו במקומן. אם לא, עוברים להדפסת התוצאות.

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

                                               

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

 

אם עברנו בהצלחה את שני התנאים הקודמים, יורדים שורה ובודקים
את שאר המלכות אשר הוצבו על הלוח ע"י חזרה ללולאה הראשית.

 

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

קידום המלכה החדשה וניסיון למצוא לה מקום חדש עדיין באותה שורה.

 

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

 

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

 

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

 

עדכון הסריקה מהסוף להתחלה.

 

לוקחים את המלכה הבאה ומנסים למקם אותה.

                       

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

                       

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

אין לקדם פוסט זה

הוספת תגובה

נשארו 150 תוים
נשארו 1500 תוים

תגובה אחת

© כל הזכויות לתוכן המופיע בדף זה שייכות ל ExcelMath91 אלא אם צויין אחרת