ייצוג אלגברי (Algebraic Representation): הלוח כמכפלה קרטזית וארבע משוואות אי-האיום
הרחבת הדיון מחידת 8 המלכות המסורתית ללוח שחמט כללי בגודל $N \times N$, וניסוח החידה באופן אלגברי טהור באמצעות קבוצת האינדקסים $A$, המכפלה הקרטזית $B = A \times A$ ותת-הקבוצה $C \subseteq B$.
מודל מנטלי ועיקרון מנחה: תרגום חוקי התנועה של מלכה בשחמט לארבעה אי-שוויונות אלגבריים!
יש מספר רב של אופנים לייצוג חידת המלכות. בייצוג האלגברי אנחנו פורשים על לוח השחמט רשת קואורדינטות דו-ממדית $(i, j)$ — בדיוק כמו מערכת צירים קרטזית שבה כל משבצת מקבלת "כתובת" ייחודית של עמודה ושורה.
פתרון חוקי הוא תת-קבוצה $C \subseteq B$ בגודל $N$ שבה לכל זוג מלכות שונות $Q_k(i_k, j_k)$ ו-$Q_l(i_l, j_l)$ מתקיימים במקביל ארבעת תנאי אי-האיום: $i_k \ne i_l$, $j_k \ne j_l$, $i_k + j_k \ne i_l + j_l$, ו-$i_k - j_k \ne i_l - j_l$.
לאורך אלכסון אחד סכום הקואורדינטות $(i + j)$ נשאר קבוע, ולאורך האלכסון הנגדי הפרש הקואורדינטות $(i - j)$ נשאר קבוע — ולכן שני ביטויים אלגבריים פשוטים לוכדים את כל האיומים האלכסוניים!
1. מחידת 8 המלכות אל חידת $N$ המלכות ואופני הייצוג שלה
מדוע אנו חוקרים מספר רב של אופנים לייצוג אותה חידה על לוח בגודל $N \times N$?
שלום לך! אנחנו מרחיבים כעת את המבט שלנו מחידת 8 המלכות המסורתית אל המקרה הכללי והמרתק של חידת $N$ המלכות על לוח שחמט בגודל $N \times N$. המשימה שלנו בחידה ברורה: להציב $N$ מלכות על לוח של $N \times N$ משבצות, כך שאף מלכה לא תאיים על חברתה — לא באותה עמודה, לא באותה שורה, ולא באותו אלכסון (ראשי או נגדי).
אבל לפני שאנחנו רצים לכתוב קוד שמחפש פתרונות, אני רוצה שנעצור ונבין עיקרון הנדסי ומתמטי עמוק: יש מספר רב של אופנים לייצוג חידת המלכות! הדרך שבה אנחנו בוחרים לייצג ולמדל את מרחב המצבים של הבעיה קובעת אילו כלים יעמדו לרשותנו — החל ממשוואות אלגבריות, דרך חשבון מודולרי חד-ממדי, ועד לבעיות קלאסיות בתורת הגרפים וניתוח מחלקות השקילות של הפתרונות.
2. הניסוח הפורמלי של הייצוג האלגברי (סעיף 14.1)
הגדרת הקבוצות $A$, $B = A \times A$, ותת-הקבוצה $C \subseteq B$ בת $N$ איברים
בוא ננסח יחד את הייצוג הראשון והאינטואיטיבי ביותר — הייצוג האלגברי (Algebraic Representation), כפי שמודגם באיור 14.1. בייצוג זה אנו מתייחסים ללוח השחמט כאל מערכת צירים קרטזית בדידה:
📐 1. קבוצת האינדקסים $A$ ומרחב הלוח $B$
נגדיר תחילה את קבוצת האינדקסים האפשריים של השורות והעמודות (מ-$0$ ועד $N-1$):
מרחב כלל משבצות הלוח מוגדר כמכפלה הקרטזית של קבוצת האינדקסים $A$ בעצמה (סך הכל $N^2$ זוגות סדורים):
👑 2. תת-קבוצת הפתרון $C \subseteq B$ וארבעת התנאים
תת-קבוצה $C \subseteq B$ מתוך קבוצת $B$ המונה $N$ איברים (משבצות שבהן מוצבות מלכות) מהווה פתרון חוקי לחידת המלכות אם ורק אם מתקיימים כל ארבעת תנאי אי-האיום הבאים (או לחלופין, נכשלים כל תנאי ההתנגשות) לכל שני איברים שונים $Q_k(i_k, j_k), Q_l(i_l, j_l) \in C$ (כאשר $k \ne l$ ו-$k, l \in A$):
- 1. מלכות אינן באותה עמודה: $i_k \ne i_l$
- 2. מלכות אינן באותה שורה: $j_k \ne j_l$
- 3. מלכות אינן באותו אלכסון (ראשי): $i_k + j_k \ne i_l + j_l$
- 4. מלכות אינן באותו אלכסון נגדי (משני): $i_k - j_k \ne i_l - j_l$
בוא נבין לעומק את היופי המתמטי של תנאים 3 ו-4: כשאנחנו נעים צעד אחד באלכסון על גבי הרשת הקרטזית, או שאנחנו מגדילים את $i$ ב-$1$ ומקטינים את $j$ ב-$1$ — ואז סכום הקואורדינטות $i + j$ נשאר קבוע לחלוטין; או שאנחנו מגדילים גם את $i$ ב-$1$ וגם את $j$ ב-$1$ — ואז הפרש הקואורדינטות $i - j$ נשאר קבוע לחלוטין! לכן שתי המשוואות האלגבריות הפשוטות האלה מזהות מיד כל התנגשות אלכסונית בכל מרחק על הלוח.
ייצוג אלגברי של חידת 4 המלכות ($N=4$) באמצעות זוגות סדורים $(i, j)$ מ-$(0,0)$ עד $(3,3)$
מיני-סימולציה 14.1: סייר ארבעת התנאים האלגבריים סביב המלכה $Q_k(1, 2)$ בלוח $4 \times 4$
מעבדת תנאים אלגבריים חיה: הצב מלכות על לוח $N \times N$ ובדוק את 4 אי-השוויונות בזמן אמת!
📊 בדיקה אלגברית חיה לכל זוג מלכות $(Q_k, Q_l) \in C$:
הגשר הנרטיבי: ראינו שזוג קואורדינטות $(i, j)$ מייצג כל משבצת – אבל האם נוכל לייצג כל משבצת באמצעות מספר בודד אחד בלבד?
בייצוג האלגברי שמרנו לכל משבצת שתי קואורדינטות $(i, j)$. אבל מה אם נמספר את כל משבצות הלוח ברצף חד-ממדי מ-$0$ ועד $N^2-1$? בלשונית הבאה (סעיף 14.2) נגלה כיצד חשבון מודולרי (Modular Arithmetic) מאפשר לנו לחלץ מתוך מספר חד-ממדי בודד $x$ גם את העמודה, גם את השורה וגם את שני האלכסונים באמצעות פעולות השארית ($\bmod$) והחלוקה השלמה!
ייצוג בחשבון מודולרי (Modular Arithmetic Representation)
מיספור משבצות הלוח במספרים חד-ממדיים רציפים מ-$0$ ועד $N^2-1$, ותרגום תנאי העמודה, השורה והאלכסונים למשוואות שארית ($\bmod N$) וחלוקה שלמה ($\lfloor x/N \rfloor$).
מודל מנטלי ועיקרון מנחה: מספר שלם יחיד $x$ מקפל בתוכו גם שורה וגם עמודה!
בניין של 4 קומות שבו בכל קומה יש 4 דירות ממוספר מדירה 0 עד דירה 15. אם תיתן לי רק את מספר הדירה $x$, אוכל מיד לדעת באיזו קומה ובאיזה מיקום בקומה היא נמצאת בעזרת חלוקה ב-$4$ ושארית מ-$4$!
בקבוצת המשבצות $A = \{0, 1, \dots, N^2-1\}$, עבור כל משבצת $x$: הביטוי $x \bmod N$ מבודד קואורדינטה אחת (השארית), והביטוי $\lfloor x/N \rfloor$ מבודד את הקואורדינטה השנייה (המנה השלמה).
תת-קבוצה $B \subseteq A$ בת $N$ איברים היא פתרון לחידה אם לכל $x, y \in B$ ($x \ne y$) מתקיימים ארבעת אי-השוויונות המודולריים של העמודה, השורה, האלכסון והאלכסון הנגדי.
1. מלוח דו-ממדי לקבוצה חד-ממדית של מספרים שלמים (סעיף 14.2)
כיצד אנו ממספרים את משבצות הלוח מ-$0$ ועד $N^2-1$?
בסעיף הקודם ייצגנו כל משבצת בלוח באמצעות זוג סדור $(i, j)$. עכשיו אני רוצה להראות לך דרך אלגנטית שחוסכת את הצורך בזוגות סדורים לחלוטין: ייצוג בחשבון מודולרי (Modular Arithmetic Representation).
במקום להשתמש בשתי קואורדינטות לכל משבצת, נמספר את כל משבצות הלוח במספרים חד-ממדיים רציפים מ-$0$ ועד $N^2 - 1$:
באיור 14.2 מודגם המיספור הזה עבור לוח של 4 מלכות ($N=4$), שבו המשבצות ממוספרות מ-$0$ עד $15$: עמודה ראשונה מכילה את $0, 1, 2, 3$; עמודה שנייה מכילה את $4, 5, 6, 7$; עמודה שלישית מכילה את $8, 9, 10, 11$; ועמודה רביעית מכילה את $12, 13, 14, 15$ (וכמובן, באותו אופן בדיוק ניתן להתבונן על סריקה ליניארית שבה שורה ראשונה היא $0..3$, שורה שנייה $4..7$ וכן הלאה — שתי הצורות שקולות לחלוטין מבחינת שני האופרטורים שלנו: שארית החלוקה ב-$N$ והערך השלם של החלוקה ב-$N$).
2. ארבעת תנאי הפתרון בחשבון מודולרי
חילוץ השורה, העמודה והאלכסונים מתוך המספרים החד-ממדיים $x$ ו-$y$
תת-קבוצה $B \subseteq A$ מתוך קבוצת $A$ המונה $N$ איברים היא פתרון לחידת המלכות (כפי שמראה איור 14.2) אם לכל שני איברים $x, y \in B$ כך ש-$x \ne y$ מתקיימים ארבעת התנאים הבאים:
1. המלכות אינן באותה עמודה:
פעולת המודולו ($x \bmod N$) מחלצת את השארית מ-$N$. שתי משבצות בעלות אותה שארית מ-$N$ חולקות את אותו מיקום מחזורי!
2. המלכות אינן באותה שורה:
פעולת הערך השלם של החלוקה ב-$N$ ($\lfloor x/N \rfloor$) מבודדת את מספר הקבוצה הרציפה (בעלת $N$ איברים) שבה נמצאת המשבצת.
3. המלכות אינן באותו אלכסון:
זהו התרגום המדויק של $i_k + j_k \ne i_l + j_l$: סכום השארית והמנה השלמה של $x$ חייב להיות שונה מזה של $y$.
4. המלכות אינן באותו אלכסון נגדי:
הפרש השארית והמנה השלמה מבטא את האלכסון הנגדי (בכפוף לכך שאם משתמשים בערך מוחלט, הוא מאחד אלכסונים סימטריים משני צידי האלכסון המרכזי).
ייצוג מודולרי של לוח $4 \times 4$ ממוספר מ-$0$ עד $15$ וחילוץ הקואורדינטות
מיני-סימולציה 14.2: מפענח משבצת מודולרי מהיר ($x \in \{0..15\}$ בלוח $N=4$)
מחשבון מודולרי למשבצות $x$ ו-$y$: בדיקת 4 תנאי המודולו והחלוקה השלמה
בחר שתי משבצות $x$ ו-$y$ מתוך $A = \{0, 1, \dots, 15\}$ (עבור $N=4$) וראה כיצד 4 הנוסחאות המודולריות מחשבות את השאריות והמנות השלמות ומזהות אם קיימת התנגשות:
📐 פירוט החישוב המתמטי של 4 תנאי הפתרון במודולו:
הגשר הנרטיבי: מנוסחאות אלגבריות ומודולריות אל עולם תורת הגרפים!
בשני הסעיפים הראשונים ייצגנו את החידה באמצעות משוואות ואי-שוויונות על קואורדינטות או על מספרים במודולו. אבל מה יקרה אם נהפוך כל משבצת בלוח לצומת (Vertex) בגרף, ונמתח קשת (Edge) בין כל שתי משבצות שמאיימות זו על זו? בלשונית הבאה (סעיף 14.3) נגלה כיצד חידת $N$ המלכות מתמפה ישירות לבעיה מפורסמת בתורת הגרפים: בעיית הקבוצה היציבה המקסימלית (Maximum Stable Set)!
ייצוג כבעיית Maximum Stable Set (קבוצה יציבה / בלתי-תלויה מקסימלית)
מיפוי חידת המלכות לבעיה קלאסית בתורת הגרפים: כל משבצת בלוח היא צומת ב-$V$, כל איום הדדי הוא קשת ב-$E$, ופתרון לחידה הוא קבוצה יציבה $V' \subseteq V$ בגודל $|V'| = N$.
מודל מנטלי ועיקרון מנחה: כשקשת מייצגת "איום", פתרון הוא קבוצת צמתים ללא אף קשת ביניהם!
דמיין חדר שבו מתוח חוט אדום בין כל שני אנשים שרבים זה עם זה. כדי להקים ועדה של $N$ אנשים שחיים בשלום, עליך לבחור $N$ אנשים שאין ביניהם אף חוט אדום — זו בדיוק קבוצה יציבה (Stable Set)!
בגרף $G = (V, E)$, קבוצת צמתים $V' \subseteq V$ היא יציבה (stable) אם אין קשת ב-$E$ המחברת שני צמתים ב-$V'$. בחידת המלכות: $V$ הן המשבצות ($N^2$ צמתים), ו-$E$ מחברת צמתים באותה שורה, עמודה או אלכסון.
כל קבוצה יציבה $V' \subseteq V$ בגודל המקסימלי האפשרי $|V'| = N$ מהווה פתרון חוקי לחידת $N$ המלכות (כפי שמודגם באיור 14.3 עבור 4 מלכות).
1. מהגדרה בתורת הגרפים אל מידול לוח השחמט (סעיף 14.3)
כיצד אנו מתרגמים את הלוח והאיומים לגרף $G = (V, E)$?
אחרי שראינו שני ייצוגים חישוביים (אלגברי ומודולרי), בוא נעשה קפיצה מחשבתית אל עולם תורת הגרפים. אחת הדרכים העוצמתיות ביותר במדעי המחשב לפתור בעיה היא למפות אותה לבעיה מוכרת בתורת הגרפים. בסעיף 14.3 אנחנו ממפים את חידת המלכות לבעיית ה-Maximum Stable Set (קבוצה יציבה מקסימלית, המוכרת גם כקבוצה בלתי-תלויה מקסימלית – Independent Set).
📖 ההגדרה התאורטית: קבוצה יציבה (Stable Set)
בהינתן גרף $G = (V, E)$, תת-קבוצת צמתים $V' \subseteq V$ נקראת קבוצה יציבה (stable) אם אין ב-$E$ אף קשת המחברת שני צמתים השייכים ל-$V'$. כלומר, כל שני צמתים מתוך $V'$ הם מנותקים לחלוטין זה מזה בגרף $G$.
♟️ מידול חידת המלכות (איור 14.3)
- קבוצת הצמתים $V$: נייצג ב-$V$ כל משבצת בלוח כצומת (סך הכל $|V| = N^2$ צמתים).
- קבוצת הקשתות $E$: נמתח קשת ב-$E$ בין כל שני צמתים שנמצאים על אותה שורה, אותה עמודה או אותו אלכסון (כלומר צמתים המאיימים זה על זה).
- משמעות הפתרון: כל קבוצה יציבה $V' \subseteq V$ בגודל $|V'| = N$ היא פתרון חוקי לחידת המלכות!
בוא נחשוב מדוע הגודל המקסימלי של קבוצה יציבה בגרף הזה אינו יכול לעלות על $N$: מכיוון שבלוח יש בדיוק $N$ שורות, וכל שתי משבצות באותה שורה מחוברות ביניהן בקשת איום ב-$E$, קבוצה יציבה יכולה להכיל לכל היותר צומת אחד מכל שורה — ולכן גודלה המקסימלי הוא $N$!
ייצוג חידת 4 המלכות כבעיית Maximum Stable Set בגרף האיומים $G=(V,E)$
מיני-סימולציה 14.3: חוקר קשתות האיום של צומת בגרף $G=(V,E)$ (לוח $4 \times 4$)
מעבדת גרפים – מצא קבוצה יציבה מקסימלית ($|V'|=4$) ללא אף קשת איום!
בחר 4 צמתים בגרף הלוח $4 \times 4$. כל קשת אדומה ב-$E$ המחברת שני צמתים שבחרת תוצג מיד על גבי הגרף. המטרה שלך: לבחור $|V'|=4$ צמתים עם 0 קשתות אדומות ביניהם!
הגשר הנרטיבי: מה יקרה אם נהפוך את משמעות הקשתות בגרף? מ-Maximum Stable Set ל-Maximum Clique!
בסעיף 14.3 מתחתי קשת בין כל שתי משבצות שמאיימות זו על זו, ולכן חיפשנו קבוצה של $N$ צמתים שאין ביניהם אף קשת (Stable Set). אבל מה יקרה אם נגדיר את הקשתות בדיוק להפך — ונמתח קשת בין כל שתי משבצות שאינן מאיימות זו על זו? בלשונית הבאה (סעיף 14.4) נראה כיצד ההיפוך הזה ממפה את חידת המלכות לבעיה המשלימה בתורת הגרפים: בעיית הקליק המקסימלי (Maximum Clique)!
ייצוג כבעיית מקסימום קליק (Maximum Clique)
המידול המשלים בתורת הגרפים: קשת ב-$E$ מחברת כל שני צמתים שאינם מאיימים זה על זה, ופתרון חוקי לחידה הוא קליק $V' \subseteq V$ (תת-גרף מלא) בגודל $|V'| = N$.
מודל מנטלי ועיקרון מנחה: כשקשת מייצגת "ביטחון הדדי", פתרון הוא קליק שבו כולם מחוברים לכולם!
אם נחבר חוט ירוק בין כל שני אנשים שיכולים לשבת יחד בשלום, אז ועדה של $N$ אנשים שכולם מסתדרים עם כולם היא תת-קבוצה שבה בין כל שני חברים מתוח חוט ירוק — וזהו בדיוק קליק (Clique)!
בגרף $G = (V, E)$, קליק (clique) היא קבוצת צמתים $V' \subseteq V$ אם יש קשת ב-$E$ בין כל שני צמתים ב-$V'$ המחברת אותם. בחידת המלכות: קשת ב-$E$ מחברת צמתים שאינם באותה שורה, עמודה או אלכסון.
קבוצה יציבה בגרף האיומים $G$ היא בדיוק קליק בגרף המשלים $\overline{G}$! כל קליק $V' \subseteq V$ בגודל $|V'| = N$ הוא פתרון לחידת המלכות (כפי שמראה איור 14.4).
1. מהו קליק (Clique) וכיצד הוא ממדל את חידת המלכות? (סעיף 14.4)
הגדרת הגרף המשלים שבו קשת מבטאת אי-איום (תאימות הדדית)
בסעיף 14.3 ראינו שניתן למדל את חידת המלכות באמצעות גרף שבו הקשתות מייצגות איומים. כעת, בסעיף 14.4, אנו מתבוננים במידול המשלים והמרתק לא פחות: ייצוג כבעיית מקסימום קליק (Maximum Clique).
📖 ההגדרה התאורטית: קליק (Clique)
בגרף $G = (V, E)$, קליק (clique) היא קבוצת צמתים $V' \subseteq V$ אם יש קשת ב-$E$ בין כל שני צמתים ב-$V'$ המחברת אותם. במילים אחרות, תת-הגרף המושרה על ידי $V'$ הוא גרף מלא (שלם) שבו כל צומת מחובר ישירות לכל צומת אחר בקבוצה.
🕸️ מידול חידת המלכות כקליק (איור 14.4)
- קבוצת הצמתים $V$: נייצג ב-$V$ כל משבצת בלוח כצומת ($N^2$ צמתים).
- קבוצת הקשתות $E$: תהא ב-$E$ קשת בין כל שני צמתים שאינם נמצאים על אותה שורה, עמודה, או אלכסון (כלומר אינם מאיימים זה על זה!).
- משמעות הפתרון: כל קליק $V' \subseteq V$ בגודל $|V'| = N$ הוא פתרון חוקי לחידת המלכות, כפי שמראה איור 14.4!
שים לב לקשר הדואלי היפהפה בין סעיף 14.3 לסעיף 14.4: הגרף של סעיף 14.4 הוא בדיוק הגרף המשלים (Complement Graph) של הגרף מסעיף 14.3! בעוד שבגרף האיומים (14.3) חיפשנו 4 צמתים שאין ביניהם אף קשת ($0$ קשתות), בגרף התאימות (14.4) אותם 4 צמתים בדיוק מחוברים זה לזה בכל הקשתות האפשריות — כלומר יוצרים קליק מלא מסדר 4 ($K_4$ הכולל $\binom{4}{2} = 6$ קשתות)!
ייצוג חידת 4 המלכות כבעיית Maximum Clique בגרף אי-האיום (השלמת קליק $K_4$)
מיני-סימולציה 14.4: מתג הדואליות – צפה באותו צומת בגרף ה-Stable Set לעומת גרף ה-Clique
מעבדת חיפוש קליק מקסימלי ($K_4$): בנה קליק של 4 צמתים המחוברים ב-6 קשתות בטוחות!
לחץ על צמתים בגרף הלוח $4 \times 4$. המערכת מותחת קשת ירוקה בין כל שני צמתים נבחרים שאינם מאיימים זה על זה. כדי שהקבוצה $V'$ תהיה קליק בגודל $4$, כל 6 הזוגות האפשריים חייבים להיות מחוברים בקשת ירוקה!
הגשר הנרטיבי: מצאנו פתרונות ללוח – אבל מתי שני פתרונות שונים הם בעצם אותו פתרון בדיוק מזווית ראייה אחרת?
אם תתבונן בשני הפתרונות של לוח $4 \times 4$, תבחין במשהו מפתיע: אם פשוט נסובב או נשקף את הלוח של הפתרון הראשון, נקבל בדיוק את הפתרון השני! בלשונית הבאה (סעיף 14.5) נחקור את הפתרונות השקולים איזומורפית (Isomorphic Solutions) ונכיר את כל 8 העתקות הסימטריה של לוח השחמט!
פתרונות שקולים איזומורפית (Isomorphic Solutions): 8 סימטריות הלוח
כיצד הסימטריה של לוח השחמט הריבועי יוצרת פתרונות שקולים שניתן לקבל זה מזה באמצעות 4 סיבובים דו-ממדיים נגד כיוון השעון ו-4 סיבובים תלת-ממדיים של $180^\circ$ סביב צירי הלוח.
מודל מנטלי ועיקרון מנחה: סיבוב או היפוך של הלוח אינו משנה את יחסי אי-האיום בין המלכות!
אם תניח מלכות בפתרון חוקי על לוח שקוף על השולחן, ותלך להסתכל עליו מצד אחר של השולחן (סיבוב) או תרים ותהפוך אותו (סיבוב תלת-ממדי של $180^\circ$), המלכות עדיין לא יאיימו זו על זו!
ללוח השחמט הריבועי יש בדיוק 8 העתקות סימטריה: 4 סיבובים במישור ($90^\circ, 180^\circ, 270^\circ, 360^\circ$ נגד כיוון השעון) ו-4 סיבובים תלת-ממדיים של $180^\circ$ סביב הצירים האופקי, האנכי, האלכסוני ($i \ne j$) והנגדי האלכסוני ($i = j$).
פתרונות שלא ניתן לקבל אחד מהשני באמצעות אף אחת מ-8 הסימטריות הללו נקראים "פתרונות זרים ממש" (פתרונות יסודיים המייצגים מחלקות שקילות שונות).
1. מהם פתרונות שקולים איזומורפית? (סעיף 14.5)
8 העתקות הסימטריה של לוח השחמט הריבועי (סיבובים במישור וסיבובים תלת-ממדיים במרחב)
כשאנחנו פותרים את חידת המלכות, אנו מגלים תופעה גיאומטרית מרתקת: בשל הסימטריה המובנית של לוח השחמט הריבועי, פתרונות רבים הם שקולים איזומורפית זה לזה (Isomorphic Solutions) — כלומר ניתן לקבל פתרון אחד מתוך השני באמצעות סדרה של סיבובים.
בוא נכיר במדויק את כל 8 הסיבובים והשיקופים היוצרים פתרונות שקולים איזומורפית על הלוח:
↺ קבוצה א': 4 סיבובים במישור (נגד כיוון השעון)
- 1. סיבוב הלוח ב-$90^\circ$ נגד כיוון השעון 90° CCW
- 2. סיבוב הלוח ב-$180^\circ$ נגד כיוון השעון 180° CCW
- 3. סיבוב הלוח ב-$270^\circ$ נגד כיוון השעון 270° CCW
- 4. סיבוב הלוח ב-$360^\circ$ נגד כיוון השעון (זהות עצמית) 360° Identity
🪞 קבוצה ב': 4 סיבובים תלת-ממדיים של $180^\circ$ (שיקופים)
- 5. סיבוב תלת-ממדי של $180^\circ$ סביב הציר האופקי Horizontal Axis
- 6. סיבוב תלת-ממדי של $180^\circ$ סביב הציר האנכי Vertical Axis
- 7. סיבוב תלת-ממדי של $180^\circ$ סביב הציר האלכסוני ($i \ne j$) Anti-Diag (i≠j)
- 8. סיבוב תלת-ממדי של $180^\circ$ סביב הציר הנגדי האלכסוני ($i = j$) Main Diag (i=j)
מדוע הבנת הסימטריות הללו חשובה כל כך? משום שהיא מאפשרת לנו להבחין בין סך כל הפתרונות האפשריים לבין "פתרונות זרים ממש" (פתרונות יסודיים שאינם ניתנים לגזירה זה מזה באמצעות סיבובים ושיקופים), וכן לחסוך זמן חיפוש אדיר באלגוריתמים על ידי הימנעות מסריקת מצבים איזומורפיים!
ארבעה סיבובים במישור וארבעה צירי סיבוב תלת-ממדיים של $180^\circ$
מיני-סימולציה 14.5: בוחן הטרנספורמציות על פתרון 4 המלכות
מעבדת 8 הסימטריות בתלת-ממד: סובב והפוך את הלוח בזמן אמת!
לחץ על כל אחת מ-8 העתקות הסימטריה וצפה באנימציה החיה של הלוח ובעדכון קואורדינטות המלכות:
הגשר הנרטיבי: עכשיו כשאנחנו מבינים מהו פתרון ומהי שקילות איזומורפית – כמה פתרונות יש לחידת $N$ המלכות עבור כל $N$?
ראינו שעבור $N=4$ ישנם $2$ פתרונות כוללים, אך שניהם שייכים לאותה מחלקת שקילות איזומורפית (ולכן יש רק פתרון זר ממש אחד!). מה קורה כשגודל הלוח $N$ גדל ל-$8$, ל-$15$, ל-$20$ או ל-$34$? וכמה פתרונות זרים ממש ישנם עבור $N=1, 2, 3, 4, 5, 6, 7, 8$? בוא נעבור ללשונית 14.6 ונגלה!
מספר הפתרונות לחידה (טבלה 14.1) ותרגיל 14.1: פתרונות זרים ממש
ניתוח מספר הפתרונות לחידת $N$ המלכות כתלות בגודל הלוח $N$ (מ-$N=1$ ועד $N=34$), והבחנה כמותית בין סך כל הפתרונות לבין מספר הפתרונות הזרים ממש (תרגיל 14.1).
מודל מנטלי ועיקרון מנחה: פיצוץ קומבינטורי עצום שמתכווץ דרמטית דרך מחלקות השקילות!
בחידת 8 המלכות ישנם 92 פתרונות כוללים על הלוח — אבל אם נסיר את כל הפתרונות שמתקבלים זה מזה בסיבוב או בשיקוף, נגלה שישנם רק 12 פתרונות זרים ממש (תבניות יסוד שונות)!
מספר הפתרונות אינו גדל בצורה מונוטונית פשוטה בתחילת הדרך: עבור $N=2, 3$ אין פתרונות כלל ($0$), ועבור $N=6$ ישנם רק $4$ פתרונות — פחות מאשר עבור $N=5$ ($10$ פתרונות)!
בטבלה 14.1 אנו רואים כיצד מספר הפתרונות מזנק מ-$1$ (עבור $N=1$) ל-$92$ (עבור $N=8$), למיליונים ב-$N=15$, ועד ל-$80,311,184,345$ עבור $N=34$!
1. מספר הפתרונות לחידה כתלות בגודל הלוח $N$ (טבלה 14.1)
התבוננות בכל ערכי טבלה 14.1 מ-$N=1$ ועד $N=34$
אחרי שהגדרנו את מרחב הפתרונות של חידת $N$ המלכות בארבע דרכים שונות (אלגברית, מודולרית, קבוצה יציבה וקליק מקסימלי) והבנו את הסימטריות של הלוח, הגיע הזמן לשאול: כמה פתרונות חוקיים יש לחידה עבור כל גודל לוח $N$?
מספר הפתרונות האפשריים כתלות בגודל הלוח $N$ מוצג בטבלה 14.1, וישנם רבים כאלו ככל ש-$N$ גדל:
📋 טבלה 14.1: מספר הפתרונות לחידת $N$ המלכות כתלות בגודל הלוח $N$
19 ערכי $N$ מדויקים| N (גודל הלוח) | סך כל הפתרונות |
|---|---|
| 1 | 1 |
| 2 | 0 |
| 3 | 0 |
| 4 | 2 |
| 5 | 10 |
| 6 | 4 |
| 7 | 40 |
| N (גודל הלוח) | סך כל הפתרונות |
|---|---|
| 8 | 92 |
| 9 | 352 |
| 10 | 724 |
| 11 | 2,680 |
| 12 | 14,200 |
| 13 | 73,732 |
| N (גודל הלוח) | סך כל הפתרונות |
|---|---|
| 14 | 365,596 |
| 15 | 2,279,184 |
| 20 | 4,192,125 |
| 25 | 1,265,433 |
| 30 | 1,749,317,724 |
| 34 | 80,311,184,345 |
2. תרגיל 14.1: כמה פתרונות זרים ממש יש עבור $N = 1, 2, 3, 4, 5, 6, 7, 8$?
הבחנה בין סך הפתרונות לבין מספר מחלקות השקילות תחת 8 סימטריות הלוח
כעת בוא נחבר את טבלה 14.1 אל הסימטריות שלמדנו בסעיף 14.5 ונפתור יחד את תרגיל 14.1: "כמה פתרונות זרים ממש יש עבור $N = 1, 2, 3, 4, 5, 6, 7, 8$?"
זכור: פתרונות זרים ממש (Fundamental Solutions) הם פתרונות שלא ניתן לקבל אחד מהשני באמצעות אף אחד מ-8 הסיבובים והשיקופים של סעיף 14.5. כל פתרון זר ממש מייצג מחלקת שקילות איזומורפית שלמה (שגודלה הוא $1$, $2$, $4$ או $8$ פתרונות, בהתאם לסימטריה הפנימית של אותו פתרון):
- $N = 1$: סך הכל $1$ פתרון $\leftarrow$ $1$ פתרון זר ממש.
- $N = 2, 3$: סך הכל $0$ פתרונות $\leftarrow$ $0$ פתרונות זרים ממש.
- $N = 4$: מתוך $2$ הפתרונות הכוללים, שניהם מתקבלים זה מזה בסיבוב של $90^\circ$ או בשיקוף $\leftarrow$ קיימת מחלקת שקילות אחת בלבד: $1$ פתרון זר ממש!
- $N = 5$: מתוך $10$ פתרונות כוללים $\leftarrow$ $2$ פתרונות זרים ממש (אחד סימטרי שיוצר $2$ פתרונות, ואחד שיוצר $8$ פתרונות: $2+8=10$).
- $N = 6$: מתוך $4$ פתרונות כוללים $\leftarrow$ $1$ פתרון זר ממש (בעל סימטריה סיבובית של $180^\circ$ שיוצר $4$ וריאציות).
- $N = 7$: מתוך $40$ פתרונות כוללים $\leftarrow$ $6$ פתרונות זרים ממש.
- $N = 8$: מתוך $92$ הפתרונות הכוללים של חידת 8 המלכות $\leftarrow$ קיימים $12$ פתרונות זרים ממש בלבד!
השוואת סך כל הפתרונות מול הפתרונות הזרים ממש עבור $N = 1 \dots 8$
מיני-סימולציה 14.6: סייר טבלה 14.1 – בחר גודל לוח $N$ וצפה בנתוני הפתרונות
מעבדת תרגיל 14.1: חקירת הפתרונות הזרים ממש ומחלקות השקילות עבור $N=1..8$
✍️ קוביית תרגיל 14.1 – בדוק את עצמך!
הזן את מספר הפתרונות הזרים ממש עבור ה-$N$ שנבחר (או רשום את הנימוק שלך בחישוב מחלקות השקילות) ובדוק את תשובתך:
הגשר הנרטיבי: השלמנו את כל סעיפי פרק 14 (14.1 עד 14.6) – בוא נסכם ונבחן את עצמנו בכרטיסיות התלת-ממד!
עברנו דרך כל אופני הייצוג של חידת $N$ המלכות: הייצוג האלגברי, החשבון המודולרי, הקבוצה היציבה המקסימלית, הקליק המקסימלי, 8 הסימטריות של פתרונות איזומורפיים, וטבלת מספר הפתרונות ותרגיל 14.1. בלשונית הבאה והאחרונה לפרק זה נבצע אינטגרציה של כל המושגים ונבחן את השליטה שלנו באמצעות 12 כרטיסיות זיכרון תלת-ממדיות (3D Flashcards), לקראת המעבר למימוש מונחה העצמים ב-Smalltalk בפרק 15!
מילון מושגים אינטראקטיבי וסיכום אינטגרטיבי של פרק 14
חיבור כל אופני הייצוג של חידת $N$ המלכות (אלגברי, מודולרי, קבוצה יציבה, קליק מקסימלי, איזומורפיזם ומספר הפתרונות) לתמונה שלמה, ו-12 כרטיסיות תלת-ממד לתרגול עצמי.
מודל מנטלי ועיקרון מנחה: בעיה אחת – ארבע שפות ייצוג מתמטיות ו-8 סימטריות מרחביות!
הייצוג האלגברי משתמש בזוגות סדורים $(i,j) \in A \times A$, בעוד שהייצוג המודולרי דוחס כל משבצת למספר חד-ממדי $x \in \{0..N^2-1\}$ ומחלץ את המיקום בעזרת $x \bmod N$ ו-$\lfloor x/N \rfloor$.
בגרף האיומים (קשת = איום) פתרון הוא קבוצה יציבה (Stable Set) בגודל $N$. בגרף המשלים (קשת = אי-איום) פתרון הוא קליק (Clique) בגודל $N$.
8 סימטריות הלוח (4 סיבובים במישור ו-4 סיבובים תלת-ממדיים של $180^\circ$) מקבצות את הפתרונות למחלקות שקילות איזומורפיות של "פתרונות זרים ממש" (כגון 12 מתוך 92 עבור $N=8$).
כל אופני הייצוג של חידת $N$ המלכות ומחלקות השקילות במבט אחד
מיני-סימולציה 14.7: בוחן אבחנה מהיר – השוואת 4 אופני הייצוג של החידה
כרטיסיות זיכרון תלת-ממדיות (3D Flashcards) לכל 12 מושגי פרק 14
לחץ על כל כרטיסייה כדי להפוך אותה ולבחון את עצמך על כל אחד מ-12 מושגי היסוד של פרק 14:
נחשפו: 0 / 12סיימנו במלואו את פרק 14! מה מחכה לנו בפרק 15?
בפרק 14 ראינו כיצד ניתן להגדיר ולמדל את חידת $N$ המלכות באופן אלגברי, בחשבון מודולרי ובתורת הגרפים (Stable Set ו-Clique), וכיצד סימטריות הלוח מגדירות פתרונות שקולים איזומורפית ופתרונות זרים ממש.
Board, את מחלקת המלכה Queen, את מנגנון השרשור ושיתוף הפעולה בין המלכות השכנות, את בדיקת האיומים canAttack:x:, ואת מימוש המלכה המנוונת QueenTerminator!