מבוא לתכנות ולמדעי המחשב בשפת C/רקורסיה (שמונה המלכות)

בעיית שמונה המלכות

8 7 6 5 4 3 2 1 א ב ג ד ה ו ז ח

פתרון אפשרי לבעיית שמונה המלכות

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

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

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

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

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

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

האנימציה הבאה מדגימה את האלגוריתם שתיארנו:

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

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

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

int board[8] = {0,0,0,0, 0,0,0,0};

כעת, ננסה לתקוף את הבעיה המרכזית ונניח לעצמינו לקרוא לפונקציות שעדיין לא מימשנו (top down design):

void queens(int i) {
    if(i == 8) {
	printBoard(); 
	return; 
    }
    int j; 
    for(j=0; j<8; ++j) {
	if(valid(i,j)) {
	    board[i] = j; 
	    queens(i+1); 
	}
    }
 
}

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

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

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

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

int valid(int i, int j) {
    int diagPlus = i+j, diagMinus = i-j;  
 
    int i1; 
    for(i1=0; i1<i; ++i1) {
	int j1 = board[i1];
	if(j == j1 || i1+j1 == diagPlus || i1-j1 == diagMinus)
	    return 0;
    }
    return 1; 
}

כעת נותר רק להוסיף פונקציית הדפסה ו main. הקוד השלם נראה כך:

#include <stdio.h> 
 
int board[8] = {0,0,0,0, 0,0,0,0}; 

int count = 0; 
 
void printBoard() {
    int i,j;
    printf("Solution %d:\n\n",count); 
    for(j=0; j<8; ++j)
	printf("+---"); 
    printf("+\n"); 
 
    for(i=0; i<8; ++i) {
 
	for(j=0; j<board[i]; ++j)
	    printf("|   "); 
	printf("| * "); 
	j++; 
	for(; j<8; ++j)
	    printf("|   "); 
	printf("|\n"); 
 
	for(j=0; j<8; ++j)
	    printf("+---"); 
	printf("+\n"); 
    }
    printf("\n\n"); 
}
 
int valid(int i, int j) {
    int diagPlus = i+j, diagMinus = i-j;  
 
    int i1; 
    for(i1=0; i1<i; ++i1) {
	int j1 = board[i1];
	if(j == j1 || i1+j1 == diagPlus || i1-j1 == diagMinus)
	    return 0;
    }
    return 1; 
}
 
void queens(int i) {
    if(i == 8) {
	++count; 
	printBoard(); 
	return; 
    }
    int j; 
    for(j=0; j<8; ++j) {
	if(valid(i,j)) {
	    board[i] = j; 
	    queens(i+1); 
	}
    }
 
}
 
void solve8queens() {
    queens(0); 
}
 
int main() {
    solve8queens(); 
    return 0; 
}

פלט:

Solution 1:

+---+---+---+---+---+---+---+---+
| * |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | * |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | * |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | * |   |   |
+---+---+---+---+---+---+---+---+
|   |   | * |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | * |   |
+---+---+---+---+---+---+---+---+
|   | * |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   | * |   |   |   |   |
+---+---+---+---+---+---+---+---+


Solution 2:

+---+---+---+---+---+---+---+---+
| * |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | * |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | * |
+---+---+---+---+---+---+---+---+
|   |   | * |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | * |   |
+---+---+---+---+---+---+---+---+
|   |   |   | * |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   | * |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | * |   |   |   |
+---+---+---+---+---+---+---+---+





...


Solution 92:

+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | * |
+---+---+---+---+---+---+---+---+
|   |   |   | * |   |   |   |   |
+---+---+---+---+---+---+---+---+
| * |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   | * |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | * |   |   |
+---+---+---+---+---+---+---+---+
|   | * |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | * |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | * |   |   |   |
+---+---+---+---+---+---+---+---+