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 Nauck

là 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

Clip 8 nữ hoàng quay lui Python ?

Bạn vừa tham khảo Post Với Một số hướng dẫn một cách rõ ràng hơn về Review 8 nữ hoàng quay lui Python tiên tiến nhất

Chia Sẻ Link Cập nhật 8 nữ hoàng quay lui Python miễn phí

Hero đang tìm một số trong những ShareLink Download 8 nữ hoàng quay lui Python miễn phí.

Giải đáp thắc mắc về 8 nữ hoàng quay lui Python

Nếu sau khi đọc nội dung bài viết 8 nữ hoàng quay lui Python vẫn chưa hiểu thì hoàn toàn có thể lại Comments ở cuối bài để Mình lý giải và hướng dẫn lại nha #nữ #hoàng #quay #lui #Python