1 package algorithm;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 public class Queen {
7 private int count = 0;
8
9 public static void main(String[] args) {
10 long start = System.currentTimeMillis();
11 List<Integer> list = new ArrayList<Integer>();
12 Queen queen = new Queen();
13 queen.findMyQueen(list);
14
15 long end = System.currentTimeMillis();
16 System.out.println("搜索時(shí)間"+(end - start)+"ms");
17 System.out.println("總共解法"+queen.count);
18 }
19
20 /**
21 * 建立一個(gè)隊(duì)列 list 用于存放八個(gè)皇后
22 */
23 public void findMyQueen(List<Integer> list) {
24
25 if (list.size() == 8) {
26 count++;
27 System.out.println("第" + count + "組");
28 for (int queen : list) {
29
30 for (int k = 0; k < 8; k++) {
31 if ((queen >> k) == 1) {
32 System.out.print(" Q ");
33 } else {
34 System.out.print(" . ");
35 }
36 }
37 System.out.println();
38
39 }
40
41 return;
42 }
43 for (int i = 0; i < 8; i++) {
44 /**
45 * 清理list
46 */
47
48 int myQueen = 1 << i;
49 if (list.size() == 0) {// 如果的長(zhǎng)度是0的話 初始狀態(tài)
50 list.add(myQueen);
51 int size = list.size();
52 findMyQueen(list);
53 clear(list, size);
54 } else {
55 int isFind = 1;
56 for (int j = 0; j < list.size(); j++) {
57 int queen = list.get(j);
58 if ((queen & myQueen) != 0) {
59 isFind = 0;
60 break;
61 }
62 if (queen != (1 << 7)) {
63 int queenLeft = queen << (list.size() - j);
64 if (queenLeft <= (1 << 7))
65 if ((queenLeft & myQueen) != 0) {
66
67 isFind = 0;
68 break;
69 }
70 }
71 if (queen != 1) {
72 int queenRight = queen >> (list.size() - j);
73 if ((queenRight & myQueen) != 0) {
74 isFind = 0;
75 break;
76 }
77 }
78 }
79 if (isFind == 1) {
80 list.add(myQueen);
81 int size = list.size();
82 findMyQueen(list);
83 clear(list, size);
84 }
85
86 }
87
88 }
89
90 }
91
92 void clear(List<Integer> list, int index) {
93 for (int i = index - 1; i < list.size(); i++)
94 list.remove(i);
95
96 }
97 }
98
list用來(lái)存放皇后隊(duì)列
如果回溯的過(guò)程中沒(méi)有找到合適的皇后 則會(huì)進(jìn)行清空的操作（刪去一個(gè)皇后）
解決八皇后問(wèn)題的核心算法 首先當(dāng)然是回溯
我自己使用的是8位取&的操作 用來(lái)判斷下一個(gè)皇后的位置正確與否
皇后左移/右移 之后與現(xiàn)在正在處理的皇后進(jìn)行&操作 移位的規(guī)則是隊(duì)列中的皇后與現(xiàn)在要處理的皇后的行的間距