در این مطلب، به روش حل مساله n وزیر با الگوریتم پس گرد (Backtracking) پرداخته می‌شود. همچنین، کدهای پیاده‌سازی روش مذکور در زبان‌های گوناگون، ارائه شده‌اند. در بازی شطرنج، وزیر می‌تواند به میزان نامحدودی به طور افقی، عمودی و قطری حرکت کند. در مساله n وزیر، هدف آن است که n وزیر در یک صفحه شطرنج n×n به گونه‌ای قرار بگیرند که هیچ یک زیر ضرب دیگری نباشد. اولین مساله n وزیر در سال ۱۸۴۸ و با عنوان مساله ۸ وزیر مطرح شد. در سال ۱۸۵۰، «فرانز نائوک» (Franz Nauck) اولین راهکار برای مساله ۸ وزیر را ارائه کرد. او، مساله 8 وزیر را به مساله n وزیر تعمیم داد که در واقع همان قرارگیری n وزیر در یک صفحه شطرنج n×n است، به صورتی که یکدیگر را تهدید نکنند. ریاضیدانان متعددی روی مساله ۸ وزیر و حالت تعمیم یافته آن یا همان n وزیر کار و سعی کردند آن را حل کنند که از این جمله می‌توان به «کارل فریدریش گاوس» (Carl Friedrich Gauss) اشاره کرد. «اس گانتر» (S. Gunther) در سال ۱۸۷۴ یک روش قطعی برای حل این مساله ارائه کرد و «جیمز گلشیر» (James Whitbread Lee Glaisher) راهکار ارائه شده توسط گانتر را بهبود بخشید.

سرانجام و در سال ۱۹۷۲، «ادسخر ویبه دِیکسترا» (Edsger W. Dijkstra) الگوریتم «اول عمق پس‌گرد» (Depth-First Backtracking) را برای حل این مساله معرفی کرد. حل مساله ۸ وزیر به لحاظ محاسباتی بسیار پرهزینه است، زیرا تنها در یک صفحه 8×۸ برای هشت وزیر، ۴,۴۲۶,۱۶۵,۳۶۸ حالت ممکن قرارگیری در صفحه شطرنج وجود دارد که از میان آن‌ها، تنها ۹۲ مورد راه حل مساله است. بنابراین، با افزایش مقدار n، پیچیدگی محاسباتی افزایش پیدا می‌کند. البته، روش‌هایی برای کاهش پیچیدگی محاسباتی جهت حل این مساله ارائه شده است؛ اما به طور کلی، مساله n وزیر از جمله مسائل «ان‌پی» (Non Deterministic Polynomial | NP) در حوزه «هوش مصنوعی» (Artificial Intelligence) محسوب می‌شود.

شایان توجه است که در مساله n وزیر، برای n=2 و n=۳ پاسخی وجود ندارد. همچنین، الزاما تعداد راهکارهای موجود برای مساله با افزایش N افزایش پیدا نمی‌کنند. برای مثال، مساله ۶ وزیر، تعداد پاسخ‌های کمتری نسبت به حالت ۵ وزیر دارد. در ادامه، روش حل مساله n وزیر برای N=4 نمایش داده شده است؛ سپس، یک الگوریتم ساده برای حل آن معرفی و در نهایت، مساله ۴ وزیر با استفاده از «الگوریتم پَس‌گرد» (Backtracking Algorithm) حل شده است. پیاده‌سازی الگوریتم پس‌گرد برای حل مساله N وزیر با زبان‌های برنامه‌نویسی C++/C، پایتون و جاوا انجام شده است.

خروجی مورد انتظار، یک ماتریس دودویی است که در آن ۱ برای محل‌هایی که وزیر در آن قرار گرفته و ۰ برای محل‌های فاقد وزیر است. برای مثال، ماتریس خروجی زیر، برای مساله ۴ وزیر است که تصویر آن در بالا وجود دارد.

 { 0, 1, 0, 0}
{ 0, 0, 0, 1}
{ 1, 0, 0, 0}
{ 0, 0, 1, 0}

الگوریتم ساده برای حل مساله N وزیر

الگوریتم ساده برای حل مساله n وزیر، همه پیکربندی‌های ممکن برای وزیرها روی صفحه را تولید می‌کند و پیکربندی را چاپ می‌کند که محدودیت‌های داده شده را ارضا می‌کند.

while there are untried configurations
{
   generate the next configuration
   if queens don't attack in this configuration then
   {
      print this configuration;
   }
}

الگوریتم پَس‌گرد

در الگوریتم «پَس‌گرد» (Backtracking)، ایده آن است که وزیرها یکی یکی در ستون‌های متفاوت قرار بگیرند و کار از چپ‌ترین ستون آغاز می‌شود. هنگامی که یک وزیر در ستون قرار می‌گیرد، بررسی می‌شود که آیا وزیر جدید قرار داده شده با سایر وزیرهای قرار گرفته در صفحه تصادم دارد یا خیر. در ستون کنونی، اگر سطری پیدا شود که هیچ ضربی بین وزیر جدید و سایر وزیرها وجود نداشته باشد، وزیر در آنجا قرار داده می‌شود. در غیر این صورت، پس‌گرد اتفاق می‌افتد و false بازگردانده می‌شود. الگوریتم پَس‌گرد برای حل مساله n وزیر، به صورت زیر است:

  1. از چپ‌ترین ستون شروع کن.
  2. اگر همه وزیرها قرار گرفته‌اند،
    • True را بازگردان
  3. همه سطرها در ستون کنونی را بررسی کن. اقدامات زیر را برای هر سطر آزموده شده انجام بده.
    • اگر وزیر بتواند به صورت امن در این سطر قرار بگیرد، آن را [row, column] به عنوان بخشی از راهکار علامت‌گذاری کن و به طور بازگشتی بررسی کن که آیا قرار دادن وزیر در اینجا منجر به راهکار می‌شود.
    • اگر قرار دادن وزیر در [row, column] منجر به راهکار می‌شود، true را بازگردان.
    • اگر قرار دادن وزیر منجر به یک راهکار شود، نشانه‌گذاری آن را بردار [row, column] (پس‌گرد) و به مرحله a برو و سطر دیگری را بررسی کن.
  4. اگر همه سطرها مورد بررسی قرار گرفتند و هیچ یک پاسخ نبودند، false را به trigger backtracking (عامل عقب‌نشینی) بازگردان.

پیاده‌سازی مساله N وزیر در ++C/C

/* C/C++ program to solve N Queen Problem using 
   backtracking */
#define N 4 
#include<stdio.h> 
#include<stdbool.h> 
  
/* A utility function to print solution */
void printSolution(int board[N][N]) 
{ 
    for (int i = 0; i < N; i++) 
    { 
        for (int j = 0; j < N; j++) 
            printf(" %d ", board[i][j]); 
        printf("\n"); 
    } 
} 
  
/* A utility function to check if a queen can 
   be placed on board[row][col]. Note that this 
   function is called when "col" queens are 
   already placed in columns from 0 to col -1. 
   So we need to check only left side for 
   attacking queens */
bool isSafe(int board[N][N], int row, int col) 
{ 
    int i, j; 
  
    /* Check this row on left side */
    for (i = 0; i < col; i++) 
        if (board[row][i]) 
            return false; 
  
    /* Check upper diagonal on left side */
    for (i=row, j=col; i>=0 && j>=0; i--, j--) 
        if (board[i][j]) 
            return false; 
  
    /* Check lower diagonal on left side */
    for (i=row, j=col; j>=0 && i<N; i++, j--) 
        if (board[i][j]) 
            return false; 
  
    return true; 
} 
  
/* A recursive utility function to solve N 
   Queen problem */
bool solveNQUtil(int board[N][N], int col) 
{ 
    /* base case: If all queens are placed 
      then return true */
    if (col >= N) 
        return true; 
  
    /* Consider this column and try placing 
       this queen in all rows one by one */
    for (int i = 0; i < N; i++) 
    { 
        /* Check if the queen can be placed on 
          board[i][col] */
        if ( isSafe(board, i, col) ) 
        { 
            /* Place this queen in board[i][col] */
            board[i][col] = 1; 
  
            /* recur to place rest of the queens */
            if ( solveNQUtil(board, col + 1) ) 
                return true; 
  
            /* If placing queen in board[i][col] 
               doesn't lead to a solution, then 
               remove queen from board[i][col] */
            board[i][col] = 0; // BACKTRACK 
        } 
    } 
  
     /* If the queen cannot be placed in any row in 
        this colum col  then return false */
    return false; 
} 
  
/* This function solves the N Queen problem using 
   Backtracking. It mainly uses solveNQUtil() to  
   solve the problem. It returns false if queens 
   cannot be placed, otherwise, return true and 
   prints placement of queens in the form of 1s. 
   Please note that there may be more than one 
   solutions, this function prints one  of the 
   feasible solutions.*/
bool solveNQ() 
{ 
    int board[N][N] = { {0, 0, 0, 0}, 
        {0, 0, 0, 0}, 
        {0, 0, 0, 0}, 
        {0, 0, 0, 0} 
    }; 
  
    if ( solveNQUtil(board, 0) == false ) 
    { 
      printf("Solution does not exist"); 
      return false; 
    } 
  
    printSolution(board); 
    return true; 
} 
  
// driver program to test above function 
int main() 
{ 
    solveNQ(); 
    return 0; 
}

پیاده سازی مساله N وزیر در پایتون

# Python program to solve N Queen  
# Problem using backtracking 
  
global N 
N = 4
  
def printSolution(board): 
    for i in range(N): 
        for j in range(N): 
            print board[i][j], 
        print
  
  
# A utility function to check if a queen can 
# be placed on board[row][col]. Note that this 
# function is called when "col" queens are 
# already placed in columns from 0 to col -1. 
# So we need to check only left side for 
# attacking queens 
def isSafe(board, row, col): 
  
    # Check this row on left side 
    for i in range(col): 
        if board[row][i] == 1: 
            return False
  
    # Check upper diagonal on left side 
    for i,j in zip(range(row,-1,-1), range(col,-1,-1)): 
        if board[i][j] == 1: 
            return False
  
    # Check lower diagonal on left side 
    for i,j in zip(range(row,N,1), range(col,-1,-1)): 
        if board[i][j] == 1: 
            return False
  
    return True
  
def solveNQUtil(board, col): 
    # base case: If all queens are placed 
    # then return true 
    if col >= N: 
        return True
  
    # Consider this column and try placing 
    # this queen in all rows one by one 
    for i in range(N): 
  
        if isSafe(board, i, col): 
            # Place this queen in board[i][col] 
            board[i][col] = 1
  
            # recur to place rest of the queens 
            if solveNQUtil(board, col+1) == True: 
                return True
  
            # If placing queen in board[i][col 
            # doesn't lead to a solution, then 
            # queen from board[i][col] 
            board[i][col] = 0
  
    # if the queen can not be placed in any row in 
    # this colum col  then return false 
    return False
  
# This function solves the N Queen problem using 
# Backtracking. It mainly uses solveNQUtil() to 
# solve the problem. It returns false if queens 
# cannot be placed, otherwise return true and 
# placement of queens in the form of 1s. 
# note that there may be more than one 
# solutions, this function prints one  of the 
# feasible solutions. 
def solveNQ(): 
    board = [ [0, 0, 0, 0], 
              [0, 0, 0, 0], 
              [0, 0, 0, 0], 
              [0, 0, 0, 0] 
             ] 
  
    if solveNQUtil(board, 0) == False: 
        print "Solution does not exist"
        return False
  
    printSolution(board) 
    return True
  
# driver program to test above function 
solveNQ() 
  
# This code is contributed by Divyanshu Mehta

پیاده سازی مساله N وزیر در جاوا

/* Java program to solve N Queen Problem using 
   backtracking */
public class NQueenProblem 
{ 
    final int N = 4; 
  
    /* A utility function to print solution */
    void printSolution(int board[][]) 
    { 
        for (int i = 0; i < N; i++) 
        { 
            for (int j = 0; j < N; j++) 
                System.out.print(" " + board[i][j] 
                                 + " "); 
            System.out.println(); 
        } 
    } 
  
    /* A utility function to check if a queen can 
       be placed on board[row][col]. Note that this 
       function is called when "col" queens are already 
       placeed in columns from 0 to col -1. So we need 
       to check only left side for attacking queens */
    boolean isSafe(int board[][], int row, int col) 
    { 
        int i, j; 
  
        /* Check this row on left side */
        for (i = 0; i < col; i++) 
            if (board[row][i] == 1) 
                return false; 
  
        /* Check upper diagonal on left side */
        for (i=row, j=col; i>=0 && j>=0; i--, j--) 
            if (board[i][j] == 1) 
                return false; 
  
        /* Check lower diagonal on left side */
        for (i=row, j=col; j>=0 && i<N; i++, j--) 
            if (board[i][j] == 1) 
                return false; 
  
        return true; 
    } 
  
    /* A recursive utility function to solve N 
       Queen problem */
    boolean solveNQUtil(int board[][], int col) 
    { 
        /* base case: If all queens are placed 
           then return true */
        if (col >= N) 
            return true; 
  
        /* Consider this column and try placing 
           this queen in all rows one by one */
        for (int i = 0; i < N; i++) 
        { 
            /* Check if the queen can be placed on 
               board[i][col] */
            if (isSafe(board, i, col)) 
            { 
                /* Place this queen in board[i][col] */
                board[i][col] = 1; 
  
                /* recur to place rest of the queens */
                if (solveNQUtil(board, col + 1) == true) 
                    return true; 
  
                /* If placing queen in board[i][col] 
                   doesn't lead to a solution then 
                   remove queen from board[i][col] */
                board[i][col] = 0; // BACKTRACK 
            } 
        } 
  
        /* If the queen can not be placed in any row in 
           this colum col, then return false */
        return false; 
    } 
  
    /* This function solves the N Queen problem using 
       Backtracking.  It mainly uses solveNQUtil () to 
       solve the problem. It returns false if queens 
       cannot be placed, otherwise, return true and 
       prints placement of queens in the form of 1s. 
       Please note that there may be more than one 
       solutions, this function prints one of the 
       feasible solutions.*/
    boolean solveNQ() 
    { 
        int board[][] = {{0, 0, 0, 0}, 
            {0, 0, 0, 0}, 
            {0, 0, 0, 0}, 
            {0, 0, 0, 0} 
        }; 
  
        if (solveNQUtil(board, 0) == false) 
        { 
            System.out.print("Solution does not exist"); 
            return false; 
        } 
  
        printSolution(board); 
        return true; 
    } 
  
    // driver program to test above function 
    public static void main(String args[]) 
    { 
        NQueenProblem Queen = new NQueenProblem(); 
        Queen.solveNQ(); 
    } 
} 
// This code is contributed by Abhishek Shankhadhar

خروجی؛ مقدار ۱ نشان‌گر محل قرارگیری وزیر است.

 0 0 1 0 
1 0 0 0 
0 0 0 1 
0 1 0 0

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای 13 نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

یک نظر ثبت شده در “حل مساله n وزیر با الگوریتم پس گرد (Backtracking) — به زبان ساده

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *