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

۳۴۱۰ بازدید
آخرین به‌روزرسانی: ۱۰ تیر ۱۴۰۲
زمان مطالعه: ۸ دقیقه
حل مساله n وزیر با الگوریتم پس گرد (Backtracking) — به زبان ساده

در این مطلب، به روش حل مساله 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 وزیر، همه پیکربندی‌های ممکن برای وزیرها روی صفحه را تولید می‌کند و پیکربندی را چاپ می‌کند که محدودیت‌های داده شده را ارضا می‌کند.

1while there are untried configurations
2{
3   generate the next configuration
4   if queens don't attack in this configuration then
5   {
6      print this configuration;
7   }
8}

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

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

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

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

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

1/* C/C++ program to solve N Queen Problem using 
2   backtracking */
3#define N 4 
4#include<stdio.h> 
5#include<stdbool.h> 
6  
7/* A utility function to print solution */
8void printSolution(int board[N][N]) 
9{ 
10    for (int i = 0; i < N; i++) 
11    { 
12        for (int j = 0; j < N; j++) 
13            printf(" %d ", board[i][j]); 
14        printf("\n"); 
15    } 
16} 
17  
18/* A utility function to check if a queen can 
19   be placed on board[row][col]. Note that this 
20   function is called when "col" queens are 
21   already placed in columns from 0 to col -1. 
22   So we need to check only left side for 
23   attacking queens */
24bool isSafe(int board[N][N], int row, int col) 
25{ 
26    int i, j; 
27  
28    /* Check this row on left side */
29    for (i = 0; i < col; i++) 
30        if (board[row][i]) 
31            return false; 
32  
33    /* Check upper diagonal on left side */
34    for (i=row, j=col; i>=0 && j>=0; i--, j--) 
35        if (board[i][j]) 
36            return false; 
37  
38    /* Check lower diagonal on left side */
39    for (i=row, j=col; j>=0 && i<N; i++, j--) 
40        if (board[i][j]) 
41            return false; 
42  
43    return true; 
44} 
45  
46/* A recursive utility function to solve N 
47   Queen problem */
48bool solveNQUtil(int board[N][N], int col) 
49{ 
50    /* base case: If all queens are placed 
51      then return true */
52    if (col >= N) 
53        return true; 
54  
55    /* Consider this column and try placing 
56       this queen in all rows one by one */
57    for (int i = 0; i < N; i++) 
58    { 
59        /* Check if the queen can be placed on 
60          board[i][col] */
61        if ( isSafe(board, i, col) ) 
62        { 
63            /* Place this queen in board[i][col] */
64            board[i][col] = 1; 
65  
66            /* recur to place rest of the queens */
67            if ( solveNQUtil(board, col + 1) ) 
68                return true; 
69  
70            /* If placing queen in board[i][col] 
71               doesn't lead to a solution, then 
72               remove queen from board[i][col] */
73            board[i][col] = 0; // BACKTRACK 
74        } 
75    } 
76  
77     /* If the queen cannot be placed in any row in 
78        this colum col  then return false */
79    return false; 
80} 
81  
82/* This function solves the N Queen problem using 
83   Backtracking. It mainly uses solveNQUtil() to  
84   solve the problem. It returns false if queens 
85   cannot be placed, otherwise, return true and 
86   prints placement of queens in the form of 1s. 
87   Please note that there may be more than one 
88   solutions, this function prints one  of the 
89   feasible solutions.*/
90bool solveNQ() 
91{ 
92    int board[N][N] = { {0, 0, 0, 0}, 
93        {0, 0, 0, 0}, 
94        {0, 0, 0, 0}, 
95        {0, 0, 0, 0} 
96    }; 
97  
98    if ( solveNQUtil(board, 0) == false ) 
99    { 
100      printf("Solution does not exist"); 
101      return false; 
102    } 
103  
104    printSolution(board); 
105    return true; 
106} 
107  
108// driver program to test above function 
109int main() 
110{ 
111    solveNQ(); 
112    return 0; 
113}

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

1# Python program to solve N Queen  
2# Problem using backtracking 
3  
4global N 
5N = 4
6  
7def printSolution(board): 
8    for i in range(N): 
9        for j in range(N): 
10            print board[i][j], 
11        print
12  
13  
14# A utility function to check if a queen can 
15# be placed on board[row][col]. Note that this 
16# function is called when "col" queens are 
17# already placed in columns from 0 to col -1. 
18# So we need to check only left side for 
19# attacking queens 
20def isSafe(board, row, col): 
21  
22    # Check this row on left side 
23    for i in range(col): 
24        if board[row][i] == 1: 
25            return False
26  
27    # Check upper diagonal on left side 
28    for i,j in zip(range(row,-1,-1), range(col,-1,-1)): 
29        if board[i][j] == 1: 
30            return False
31  
32    # Check lower diagonal on left side 
33    for i,j in zip(range(row,N,1), range(col,-1,-1)): 
34        if board[i][j] == 1: 
35            return False
36  
37    return True
38  
39def solveNQUtil(board, col): 
40    # base case: If all queens are placed 
41    # then return true 
42    if col >= N: 
43        return True
44  
45    # Consider this column and try placing 
46    # this queen in all rows one by one 
47    for i in range(N): 
48  
49        if isSafe(board, i, col): 
50            # Place this queen in board[i][col] 
51            board[i][col] = 1
52  
53            # recur to place rest of the queens 
54            if solveNQUtil(board, col+1) == True: 
55                return True
56  
57            # If placing queen in board[i][col 
58            # doesn't lead to a solution, then 
59            # queen from board[i][col] 
60            board[i][col] = 0
61  
62    # if the queen can not be placed in any row in 
63    # this colum col  then return false 
64    return False
65  
66# This function solves the N Queen problem using 
67# Backtracking. It mainly uses solveNQUtil() to 
68# solve the problem. It returns false if queens 
69# cannot be placed, otherwise return true and 
70# placement of queens in the form of 1s. 
71# note that there may be more than one 
72# solutions, this function prints one  of the 
73# feasible solutions. 
74def solveNQ(): 
75    board = [ [0, 0, 0, 0], 
76              [0, 0, 0, 0], 
77              [0, 0, 0, 0], 
78              [0, 0, 0, 0] 
79             ] 
80  
81    if solveNQUtil(board, 0) == False: 
82        print "Solution does not exist"
83        return False
84  
85    printSolution(board) 
86    return True
87  
88# driver program to test above function 
89solveNQ() 
90  
91# This code is contributed by Divyanshu Mehta

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

1/* Java program to solve N Queen Problem using 
2   backtracking */
3public class NQueenProblem 
4{ 
5    final int N = 4; 
6  
7    /* A utility function to print solution */
8    void printSolution(int board[][]) 
9    { 
10        for (int i = 0; i < N; i++) 
11        { 
12            for (int j = 0; j < N; j++) 
13                System.out.print(" " + board[i][j] 
14                                 + " "); 
15            System.out.println(); 
16        } 
17    } 
18  
19    /* A utility function to check if a queen can 
20       be placed on board[row][col]. Note that this 
21       function is called when "col" queens are already 
22       placeed in columns from 0 to col -1. So we need 
23       to check only left side for attacking queens */
24    boolean isSafe(int board[][], int row, int col) 
25    { 
26        int i, j; 
27  
28        /* Check this row on left side */
29        for (i = 0; i < col; i++) 
30            if (board[row][i] == 1) 
31                return false; 
32  
33        /* Check upper diagonal on left side */
34        for (i=row, j=col; i>=0 && j>=0; i--, j--) 
35            if (board[i][j] == 1) 
36                return false; 
37  
38        /* Check lower diagonal on left side */
39        for (i=row, j=col; j>=0 && i<N; i++, j--) 
40            if (board[i][j] == 1) 
41                return false; 
42  
43        return true; 
44    } 
45  
46    /* A recursive utility function to solve N 
47       Queen problem */
48    boolean solveNQUtil(int board[][], int col) 
49    { 
50        /* base case: If all queens are placed 
51           then return true */
52        if (col >= N) 
53            return true; 
54  
55        /* Consider this column and try placing 
56           this queen in all rows one by one */
57        for (int i = 0; i < N; i++) 
58        { 
59            /* Check if the queen can be placed on 
60               board[i][col] */
61            if (isSafe(board, i, col)) 
62            { 
63                /* Place this queen in board[i][col] */
64                board[i][col] = 1; 
65  
66                /* recur to place rest of the queens */
67                if (solveNQUtil(board, col + 1) == true) 
68                    return true; 
69  
70                /* If placing queen in board[i][col] 
71                   doesn't lead to a solution then 
72                   remove queen from board[i][col] */
73                board[i][col] = 0; // BACKTRACK 
74            } 
75        } 
76  
77        /* If the queen can not be placed in any row in 
78           this colum col, then return false */
79        return false; 
80    } 
81  
82    /* This function solves the N Queen problem using 
83       Backtracking.  It mainly uses solveNQUtil () to 
84       solve the problem. It returns false if queens 
85       cannot be placed, otherwise, return true and 
86       prints placement of queens in the form of 1s. 
87       Please note that there may be more than one 
88       solutions, this function prints one of the 
89       feasible solutions.*/
90    boolean solveNQ() 
91    { 
92        int board[][] = {{0, 0, 0, 0}, 
93            {0, 0, 0, 0}, 
94            {0, 0, 0, 0}, 
95            {0, 0, 0, 0} 
96        }; 
97  
98        if (solveNQUtil(board, 0) == false) 
99        { 
100            System.out.print("Solution does not exist"); 
101            return false; 
102        } 
103  
104        printSolution(board); 
105        return true; 
106    } 
107  
108    // driver program to test above function 
109    public static void main(String args[]) 
110    { 
111        NQueenProblem Queen = new NQueenProblem(); 
112        Queen.solveNQ(); 
113    } 
114} 
115// This code is contributed by Abhishek Shankhadhar

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

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

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

^^

بر اساس رای ۱۳ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
۲ دیدگاه برای «حل مساله n وزیر با الگوریتم پس گرد (Backtracking) — به زبان ساده»

سلام من اینو نمی فهمم از کجا به کجا میره آیا در تابع چندین مقدار ذخیره میشه آیا اگر آموزش c++ فرادرس تهیه کنم می تونم اینم بفهمم

با تشکر از مطلب بسیار زیبا.میشه مثالی از کاربرد این الگوریتم در حوزه هایی دیگه ارائه بدین

نظر شما چیست؟

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