حل مساله 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 وزیر، به صورت زیر است:
- از چپترین ستون شروع کن.
- اگر همه وزیرها قرار گرفتهاند،
- True را بازگردان
- همه سطرها در ستون کنونی را بررسی کن. اقدامات زیر را برای هر سطر آزموده شده انجام بده.
- اگر وزیر بتواند به صورت امن در این سطر قرار بگیرد، آن را [row, column] به عنوان بخشی از راهکار علامتگذاری کن و به طور بازگشتی بررسی کن که آیا قرار دادن وزیر در اینجا منجر به راهکار میشود.
- اگر قرار دادن وزیر در [row, column] منجر به راهکار میشود، true را بازگردان.
- اگر قرار دادن وزیر منجر به یک راهکار شود، نشانهگذاری آن را بردار [row, column] (پسگرد) و به مرحله a برو و سطر دیگری را بررسی کن.
- اگر همه سطرها مورد بررسی قرار گرفتند و هیچ یک پاسخ نبودند، 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
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان دادهها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- معرفی منابع آموزش ویدئویی هوش مصنوعی به زبان فارسی و انگلیسی
- زبان برنامهنویسی پایتون (Python) — از صفر تا صد
- آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
^^
سلام من اینو نمی فهمم از کجا به کجا میره آیا در تابع چندین مقدار ذخیره میشه آیا اگر آموزش c++ فرادرس تهیه کنم می تونم اینم بفهمم
با تشکر از مطلب بسیار زیبا.میشه مثالی از کاربرد این الگوریتم در حوزه هایی دیگه ارائه بدین