回溯法 n 皇后問題（Java實現）

n 皇后問題

問題分析

在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。

x[i] 表示皇后i 放在棋盤的第i 行的第x[i] 列

不能在同一行

不能在同一列 x[i] 互不相同

不能在同一斜線

斜率為1 和值相等

斜率為-1 差值相等

若兩個點 (i, j) (k, l), 則有

i - j = k - l => i - k = j - l

i + j = k + l => i - k = l -j

即 |i - k| = |j - l| 成立即可

Java 源代碼

/* * 若塵 */ package nqueen; /** * n 皇后問題 * @author ruochen * @version 1.0 */ public class NQueen { /** 皇后個數 */ static int n; /** 當前解 */ static int[] x; /** 當錢已找到的可行方案數 */ static long sum; public static void main(String[] args) { nQueen(5); System.out.println("可行方案個數為： " + sum); } /** * 初始化及返回可行解個數 * @return 可行解個數 */ public static long nQueen(int nn) { n = nn; sum = 0; x = new int[n + 1]; for (int i = 0; i <= n; i++) { // 初始化 x[i] = 0; } backTrack(1); return sum; } /** * 可行性約束 * @param k * @return 是否可行 */ public static boolean place(int k) { for (int j = 1; j < k; j++) { // 對應公式 |i - k| = |j - l| && 列號不能相同 if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || x[j] == x[k]) return false; } return true; } /** * 回溯搜索 * @param i */ public static void backTrack(int t) { if (t > n) { // 已經找到一種可行解 long temp = sum + 1; System.out.print("第" + temp + "種可行解為： "); for (int k = 1; k <= n; k++) { System.out.print(x[k] + " "); } System.out.println(); sum++; } else { for (int i = 1; i <= n; i++) { x[t] = i; if (place(t)) backTrack(t + 1); } } } }

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

第1種可行解為： 1 3 5 2 4 第2種可行解為： 1 4 2 5 3 第3種可行解為： 2 4 1 3 5 第4種可行解為： 2 5 3 1 4 第5種可行解為： 3 1 4 2 5 第6種可行解為： 3 5 2 4 1 第7種可行解為： 4 1 3 5 2 第8種可行解為： 4 2 5 3 1 第9種可行解為： 5 2 4 1 3 第10種可行解為： 5 3 1 4 2 可行方案個數為： 10

1

2

3

4

5

6

7

8

9

10

11

Java

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。