Mẹo 8 nữ hoàng quay lui Python
Thủ Thuật Hướng dẫn 8 nữ hoàng quay lui Python 2022
Bùi Bình Minh đang tìm kiếm từ khóa 8 nữ hoàng quay lui Python được Cập Nhật vào lúc : 2022-12-19 16:26:06 . Với phương châm chia sẻ Mẹo về trong nội dung bài viết một cách Chi Tiết 2022. Nếu sau khi đọc tài liệu vẫn ko hiểu thì hoàn toàn có thể lại Comments ở cuối bài để Admin lý giải và hướng dẫn lại nha.Câu đố N-quân hậu là bài toán đặt N quân hậu trên bàn cờ N × N sao cho không còn hai quân hậu nào đe dọa lẫn nhau. Do đó, giải pháp yêu cầu không còn hai con hậu nào chia sẻ cùng một hàng, cột hoặc đường chéo
Nội dung chính Show- Cách giải 8Backtracking hoạt động và sinh hoạt giải trí ra làm sao trên 8Dùng thuật toán nào để giải 8
Ví dụ: đối với bàn cờ tiêu chuẩn 8 × 8, phía dưới là một thông số kỹ thuật như vậy
Q. – – – – – – –
– – – – Q. – – –
– – – – – – Q.
– – – – – Q. – –
– – Q. – – – – –
– – – – – – Q. –
– Q. – – – – – –
– – – Q. – – – –
Lưu ý rằng giải pháp tồn tại cho tất cả những số tự nhiên n, ngoại trừ n = 2 và n = 3
Thực hành vấn đề này
Chúng ta hoàn toàn có thể xử lý và xử lý vấn đề này với sự trợ giúp của tính năng quay lui. Ý tưởng là bắt nguồn từ số 1 tiên và đặt Nữ hoàng vào mỗi ô vuông của số 1 tiên và mày mò đệ quy những hàng còn sót lại để kiểm tra xem chúng có dẫn đến giải pháp hay là không. Nếu thông số kỹ thuật hiện tại không dẫn đến giải pháp, hãy quay lại. Trước khi mày mò bất kỳ hình vuông vắn nào, hãy bỏ qua hình vuông vắn nếu hai nữ hoàng đe dọa lẫn nhau.
Thuật toán hoàn toàn có thể được triển khai như sau trong C, Java và Python
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include
#include
// Bàn cờ `N × N`
#define N 8
// Hàm kiểm tra 2 quân hậu có đe dọa nhau hay là không
int isSafe(char mat[][N], int r, int c)
// trả về 0 nếu hai quân hậu ở cùng một cột
cho (int i = 0; i r; i++)
nếu (mat[i][c] == 'Q.')
return 0;
// trả về 0 nếu hai quân hậu có cùng `` đường chéo
cho (int i = r, j = c; i >= 0 && j >= 0; i--, j--)
nếu (mat[i][j] == 'Q.')
return 0;
// trả về 0 nếu hai quân hậu có cùng đường chéo `/`
cho (int i = r, j = c; i >= 0 && j N; i--, j++)
nếu (mat[i][j] == 'Q.')
return 0;
return 1;
void printSolution(char mat[][N])
cho (int i = 0; i N; i++)
cho (int j = 0; j N; j++)
printf("%c ", mat[i][j]);
printf("n");
printf("n");
void nQueen(char mat[][N], int r)
// nếu `N` quân hậu được đặt thành công, hãy in lời giải
nếu (r == N)
printSolution(mat);
trả lại;
// đặt quân hậu ở mỗi ô trong hàng hiện tại `r`
// và lặp lại cho từng hoạt động và sinh hoạt giải trí hợp lệ
cho (int i = 0; i N; i++)
// nếu không còn 2 quân hậu đe dọa nhau
nếu (An toàn(mat, r, i))
// đặt quân hậu vào ô hiện tại
mat[r][i] = 'Q.';
// lặp lại cho hàng tiếp theo
nQuân hậu(mat, r + 1);
// quay lại và vô hiệu quân hậu khỏi ô hiện tại
mat[r][i] = '-';
int chính()
// `mat[][]` theo dõi vị trí của quân hậu trong thông số kỹ thuật hiện tại
char mat[N][N];
// khởi tạo `mat[][]` bằng `-`
bộ nhớ(mat, '-', sizeof mat);
nQuân hậu(mat, 0);
return 0;
Tải xuống Chạy mã
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
nhập java. sử dụng. Mảng;
lớp Chính
// Hàm kiểm tra xem 2 quân hậu có đe dọa nhau hay là không
riêng tư tĩnh boolean isSafe(char[][] mat, int r, int c)
// trả về false nếu hai quân hậu ở cùng một cột
cho (int i = 0; i r; i++)
nếu (mat[i][c] == 'Q.')
trả về false;
// trả về false nếu hai quân hậu có cùng `` đường chéo
cho (int i = r, j = c; i >= 0 && j >= 0; i--, j--)
nếu (mat[i][j] == 'Q.')
trả về false;
// trả về false nếu hai quân hậu có cùng `/` đường chéo
cho (int i = r, j = c; i >= 0 && j mat.độ dài; i--, j++)
nếu (mat[i][j] == 'Q.')
trả về false;
trả về true;
riêng tư tĩnh vô hiệu printSolution(char[][] mat)
cho (char[] chars: thảm)
Hệ thống. ra. println(Mảng. toString(ký tự). replaceAll(",", ""));
Hệ thống. ra. println();
riêng tư tĩnh vô hiệu nQueen(char[][] mat, int r)
// nếu `N` quân hậu được đặt thành công, hãy in đáp án
nếu (r == mat.độ dài)
printSolution(mat);
return;
// đặt quân hậu ở mỗi ô trong hàng hiện tại `r`
// và lặp lại cho từng hoạt động và sinh hoạt giải trí hợp lệ
cho (int i = 0; i mat.độ dài; i++)
// nếu không còn 2 quân hậu đe dọa nhau
if (isSafe(mat, r, i))
// đặt quân hậu vào ô hiện tại
thảm[r][i] = 'Q.';
// lặp lại cho hàng tiếp theo
nQuân hậu(thảm, r + 1);
// quay lại và vô hiệu quân hậu khỏi ô hiện tại
thảm[r][i] = '–';
công khai minh bạch tĩnh vô hiệu chính(String[] args)
// `N × N` bàn cờ
int N = 8;
// `mat[][]` theo dõi vị trí của quân hậu trong
// thông số kỹ thuật hiện tại
char[][] mat = new char[N][N];
// khởi tạo `mat[][]` bằng `-`
cho (int i = 0; i N; i++)
Mảng. điền(đệm[i], '–');
nQuân hậu(thảm, 0);
Tải xuống Chạy mã
con trăn
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# Chức năng kiểm tra xem hai nữ hoàng có đe dọa nhau hay là không
def isSafe(mat, r, c):
# trả về false nếu hai quân hậu ở cùng một cột
cho i trong phạm vi(r):
nếu mat[i][c] == 'Q.':
return Sai
# trả về giá trị sai nếu hai quân hậu có cùng `` đường chéo
(i, j) = (r, c)
while i >= 0 and j >= 0:
nếu mat[i][j] == 'Q.':
return Sai
i = i - 1
j = j - 1
# trả về giá trị sai nếu hai quân hậu có cùng đường chéo `/`
(i, j) = (r, c)
while i >= 0 and j len(mat):
nếu mat[i][j] == 'Q.':
return Sai
i = i - 1
j = j + 1
return True
def printSolution(mat):
cho r trong mat:
in(str(r).thay thế(',', '').thay thế(''', ''))
in()
def nQueen(mat, r):
# nếu `N` quân hậu được đặt thành công, hãy in lời giải
if r == len(mat):
printSolution(mat)
trả lại
# đặt quân hậu vào mỗi ô trong hàng hiện tại `r`
# và lặp lại cho từng hoạt động và sinh hoạt giải trí hợp lệ
cho i trong phạm vi(len(mat)):
# nếu không còn hai quân hậu đe dọa nhau
nếu An toàn(mat, r, i):
# đặt quân hậu vào ô hiện tại
mat[r][i] = 'Q.'
# lặp lại cho hàng tiếp theo
nQuân hậu(mat, r + 1)
# quay lại và vô hiệu quân hậu khỏi ô hiện tại
mat[r][i] = '–'
if __name__ == '__main__'.
# `N × N` bàn cờ
N = 8
# `mat[][]` theo dõi vị trí của quân hậu trong
# thông số kỹ thuật hiện tại
mat = [['–' for x in range(N)] for y in range(N)]
nQuân hậu(mat, 0)
Tải xuống Chạy mã
Đầu ra.
Q. – – – – – – –
– – – – Q. – – –
– – – – – – – Q.
– – – – – Q. – –
– – Q. – – – – –
– – – – – – Q. –
– Q. – – – – – –
– – – Q. – – – –
Q. – – – – – – –
– – – – – Q. – –
– – – – – – – Q.
– – Q. – – – – –
– – – – – – Q. –
– – – Q. – – – –
– Q. – – – – – –
– – – – Q. – – –
And 90 other distinct solutions to the eight queens problem.
Độ phức tạp về thời gian của giải pháp quay lui ở trên là theo cấp số nhân
Tối ưu hóa. Độ phức tạp về thời gian của thuật toán quay lui ở trên hoàn toàn có thể được cải tổ bằng phương pháp sử dụng Nhánh và Giới hạn. Trong một giải pháp quay lui, chúng tôi quay lại khi đi vào ngõ cụt, nhưng theo nhánh và số lượng giới hạn, sau khi xây dựng giải pháp một phần, chúng tôi nhận ra rằng không còn ích gì khi đi sâu hơn thế nữa khi chúng tôi sắp đi vào ngõ cụt. Giải pháp ràng buộc và nhánh N-Queen được thảo luận tại đây.
Tham khảo.
1. https. // vi. wikipedia. org/wiki/Eight_queens_puzzle
2. https. // nhà phát triển. Google. com/optimization/cp/queen
Cách giải 8
Sắp xếp 8 quân hậu trong 64 phần. Điều này hoàn toàn có thể được thực hiện trong 64C8 = (64x63x62x61x60x59x58x57)/8. = 4.426.165.368 cách . ** Sắp xếp 1 nữ hoàng mỗi hàng. **Nếu tất cả chúng ta số lượng giới hạn một quân hậu trên mỗi hàng, thì mỗi quân hậu có 8 vị trí hoàn toàn có thể, vì vậy tổng số cách sắp xếp là 8⁸ = 16.777.216 cách.Backtracking hoạt động và sinh hoạt giải trí ra làm sao trên 8
Quay lui thuật toán . Quân hậu chỉ hoàn toàn có thể bị tấn công nếu nằm cùng hàng, cùng cột hoặc cùng đường chéo với bất kỳ quân hậu nào khác .Dùng thuật toán nào để giải 8
Giải trình. Năm 1972, thuật toán quay lui đầu tiên theo chiều sâu được đề xuất bởi Edsger Dijkshtra để minh họa cho câu đố Eight Queen. Max Friedrich William Bezzel đã xuất bản câu đố và lời giải đầu tiên cho Câu đố 8 quân hậu được đưa ra bởi Franz Naucklà N
Ian, Christopher và Peter đã chỉ ra rằng câu đố n-Queens thực sự khó chứ không đơn giản . Nó thuộc về những lớp phức tạp NP-Complete và #P-Complete. Tải thêm tài liệu liên quan đến nội dung bài viết 8 nữ hoàng quay lui Python programming python
Post a Comment