Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

CSharp – חידת 8 המלכות

riddle of the 8 queens solution
riddle of the 8 queens solution

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

חידת 8 המלכות היא מקרה מסוים של בעיית n המלכות, בעיה דומה אשר בה יש להציב n מלכות על לוח בגודל n x n‏.
לחידה זו יש 12 פתרונות בסיסיים, כאשר באמצעות שיקוף וסיבוב הלוח, ניתן לקבל את שאר הפתרונות.
זוהי דוגמה נפוצה לבעיה הניתנת לפתרון באמצעות בדיקת כל המצבים האפשריים, ומציאת אלה מתוכם העונים על תנאי החידה.
לשם מיקום המלכות עלינו לבחור 8 משבצות מתוך הלוח (מספר המצבים האפשריים הוא יותר מארבעה מיליארד(!)).
מספר עצום זה של מצבים הוא לא פרקטי לבדיקה בידי אדם, אך מספר סביר בהחלט לבדיקה באמצעות מחשב.

לצורך כתיבת מאמר זה, השתמשנו ב-WPF על מנת להציג את הפרזנטציה.

יצירת ה-MainViewModel

ניצור את ה-MainViewModel בקובץ חדש.
נוסיף לו את השדות אשר ייצגו את לוח השחמט שלנו, בבנאי נאתחל את השדות ונבנה את הלוח.
ניצור מחלקה בשם – Cell – כל אריח בלוח יכיל – Cell .
נכניס את כל התאים למבנה נתונים, ובמקביל ניצור מערך דו מימדי לשם מימוש הלוגיקה בתוכנית:

using System.Collections.Generic;

public class MainViewModel
{
    const int MAX = 8;

    public int[,] Board;
    public List<List<Cell>> CellBoard = new();

    //ctor - builds the chessboard
    public MainViewModel()
    {
        CellBoard = new List<List<Cell>>(MAX);

        for (int i = 0; i < MAX; i++)
        {
            CellBoard.Add(new List<Cell>(MAX));

            for (int j = 0; j < MAX; j++)
            {
                CellBoard[i].Add(new Cell());
            }
        }

        Board = new int[MAX, MAX];
    }
 }

בניית האלגוריתמים לבדיקת מיקומי 8 המלכות

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

bool IsSafe(int row, int col)
{
//from the left until the current col
    for (int i = 0; i < col; i++)
    {
        if (Board[row, i] == 1)
        {
            return false;
        }
    }

    //upper diagonal
   for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (Board[i, j] == 1)
        {
            return false;
        }
    }

    //lower diagonal
    for (int i = row, j = col; i < MAX && j >= 0; i++, j--)
    {
        if (Board[i, j] == 1)
        {
            return false;
        }
    }
    return true;
 }

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

public bool Solve(int col)
{
    //if all queens are placed return true
    if (col >= MAX)
    {
        return true;
    }

    for (int row = 0; row < MAX; row++)
    {
        if (IsSafe(row, col))
        {
            Board[row, col] = 1;
            CellBoard[row][col].Value = 1;

            if (Solve(col + 1))
            {
                return true;
            }

            Board[row, col] = 0;
            CellBoard[row][col].Value = 0;
        }
    }
    return false;
}

יצירת הממשק הגרפי

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

namespace _8Queens
{
    public partial class MainWindow : Window
    {
        public  MainViewModel Board = new();
        public Image[,]? AllImages;

        public MainWindow()
        {
            InitializeComponent();

            AllImages = new Image[8, 8]
            { { pic1_1, pic1_2, pic1_3, pic1_4, pic1_5, pic1_6, pic1_7, pic1_8 },
              { pic2_1, pic2_2, pic2_3, pic2_4, pic2_5, pic2_6, pic2_7, pic2_8 },
              { pic3_1, pic3_2, pic3_3, pic3_4, pic3_5, pic3_6, pic3_7, pic3_8 },
              { pic4_1, pic4_2, pic4_3, pic4_4, pic4_5, pic4_6, pic4_7, pic4_8 },
              { pic5_1, pic5_2, pic5_3, pic5_4, pic5_5, pic5_6, pic5_7, pic5_8 },
              { pic6_1, pic6_2, pic6_3, pic6_4, pic6_5, pic6_6, pic6_7, pic6_8 },
              { pic7_1, pic7_2, pic7_3, pic7_4, pic7_5, pic7_6, pic7_7, pic7_8 },
              { pic8_1, pic8_2, pic8_3, pic8_4, pic8_5, pic8_6, pic8_7, pic8_8 } };
        }
        private void Button_Click_1(object sender, RoutedEventArgs e)
        {
            Board.Solve(0);

            foreach (List<Cell> cells in Board.CellBoard)
            {
                foreach (Cell c in cells)
                {
                    if (c.Value == 1 && AllImages != null)
                    {
                        AllImages[Board.CellBoard.IndexOf(cells), cells.IndexOf(c)].Visibility = Visibility.Visible;
                    }
                }
            }
        }
    }
}

אם פעלתם לפי המאמר תוכלו לקבל את התוצאה הבאה:.

riddle of the 8 queens solution
riddle of the 8 queens solution

התוכנית המלאה בגיטהאב :

קידוד מהנה!

אהבתכם את המדריך? פתר לכם תקלה? הזמינו את כותב המדריך לכוס קפה

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

ניתן לתרום 10, 15, 20 או כל סכום אחר שתרצו באמצעות כרטיס אשראי \ Paypal

רוצים לשתף את המדריך?

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *

הזמינו אותי לכוס קפה
buy me coffee

אהבתכם את המדריך? פתר לכם תקלה? הזמינו את כותב המדריך לכוס קפה

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