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

חידת 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;
                    }
                }
            }
        }
    }
}

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

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

קידוד מהנה!