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("搜索时间"+(end - start)+"ms");
17 System.out.println("总共解法"+queen.count);
18 }
19
20 /**
21 * 建立一个队列 list 用于存放八个皇后
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) {// 如果的长度是0的话 初始状态
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用来存放皇后队列
如果回溯的过程中没有找到合适的皇后 则会进行清空的操作（删去一个皇后）
解决八皇后问题的核心算法 首先当然是回溯
我自己使用的是8位取&的操作 用来判断下一个皇后的位置正确与否
皇后左移/右移 之后与现在正在处理的皇后进行&操作 移位的规则是队列中的皇后与现在要处理的皇后的行的间距