8皇后问题

Posted on Edited on

题目：

如何能够在8×8的国际象棋棋盘上放置8个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

因为在国际象棋中，皇后可以横、直或者斜着走，格数不限，所以棋盘中任意2个皇后都不能在同一行、同一列以及同一斜线。

思路：

依次检测同一行、同一列以及同一斜线有没有皇后，如果没有就检测下一行。累计检测满八个皇后就记一种解法。

一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉：

  1. x=row(在纵向不能有两个皇后)

  2. y=col（横向）

  3. col + row = y+x;（斜向正方向）

  4. col - row = y-x;（斜向反方向）

我们用 queen[x]来表示 第x个皇后在第几列。

递归法

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
#-*- coding:utf-8 -*-
# python Solution
# 检查有没有在同一列或者同一斜线
# 同一行不用检测因为后面皇后的行数是递增的
def available(row,col):
	for x in range(row):
		if queen[x]==col or x - queen[x] == row - col or queen[x] + x == row + col:
			return False
	return True

def find(row):
# 如果不冲突就记下当前的row和queen[row]（列）
# 然后检查下一行
	global count,queen
	if row == 8:
		count += 1
	else:
		for col in range(8):
			if available(row,col):
				queen[row] = col
				# 递归
				find(row+1)
	

if __name__ == '__main__':
	global count,queen
	count = 0
	queen = [-1]*8
	find(0)
	print count
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
//Java Solution
public class Queen8 {
	
	int[] queen = new int[8];
	
	int count = 0;
	
	public Queen8() {
		find(0);
    	System.out.println(count);
	}
// 检查有没有在同一列或者同一斜线
// 同一行不用检测因为后面皇后的行数是递增的
	public boolean avaliable(int row,int col) {
		for (int x = 0;x<row;x++){
			if (queen[x]==col || x-queen[x]==row-col || x+queen[x]==row+col) {
				return false;
			}
		}
		
		return true;
	}
	
	public void find(int row) {
		if (row == 8) {
			count++;
		}
		else {
			for (int col = 0;col<8;col++) {
				if (avaliable(row, col)) {
					queen[row] = col;
					// 递归
					find(row+1);
				}
			}
		}
	}
	
    public static void main(String[] args) 
    {
    	Queen8 queen8 = new Queen8();
    }
    
}

非递归(回溯法)

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

算法描述如下：

  1. 开始时清空棋盘，将当前行设为第零行，当前列设为第零列。
  2. 判断当前位置是否合法，若不合法到第4步。
  3. 当前位置合法，则在当前位置放置一棋子。
    • 若当前行为最后一行，则记录一个解。
      • 若当前列是最后一列，当前行设为前一行，当前列设为当前行对应列的下一列。
      • 若当前列不是最后一列，当前列设为下一列.
    • 若当前行不是最后一行，则将当前行设为下一行，当前列设为第零列。
      回至第2步。
  4. 当前位置不合法。
  • 若当前列不是最后最后一列，则当前列设为下一列，回到第2步。
  • 若当前列是最后一列
    • 若当前行为第零行，结束
    • 若当前不是第零行，当前行设为前一行，当前列设为当前行对应列的下一列。
      回至第2步。
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
#-*- coding:utf-8 -*-
def available(row,col):
	for x in range(row):
		if queen[x]==col or x - queen[x] == row - col or queen[x] + x == row + col:
			return False
	return True

def find():
	count = 0
	row = 0
	global queen
	queen[row] = 0
	while row>=0: #当前行为 -1 时结束
		if row < 8 and queen[row] < 8: #当前行、当前列均为到达最后
			if available(row,queen[row]): #当前位置合法，则探索下一行
				row += 1
				queen[row] = 0
			else:
				queen[row] += 1
		else: #当前位置不合法，探测当前行的下一个位置
			if row>=8: #当前行、当前列均到了最后，记录一个解
				count+=1
			row -= 1 # 返回上一行，继续探索
			queen[row] += 1
	return count

if __name__ == '__main__':
	global queen
	queen = [-1]*9
	print find()
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
public class Queen8 {
	
	int[] queen = new int[9];
	
	public Queen8() {
		
    	System.out.println(find());
	}
	
	public boolean avaliable(int row,int col) {
		for (int x = 0;x<row;x++){
			if (queen[x]==col || x-queen[x]==row-col || x+queen[x]==row+col) {
				return false;
			}
		}
		
		return true;
	}
	
	public int find() {
		int count = 0;
		int row = 0;
		queen[row] = 0;
		while (row >= 0) {
			if (row<8 && queen[row]<8) {
				if (avaliable(row, queen[row])) {
					row++;
					queen[row] = 0;
				}
				else {
					queen[row]++;
				}
			}
			else {
				if (row>=8) {
					count++;
				}
				row--;
				System.out.println(row);
				if (row>=0) {
					queen[row]++;
				}
				
				
			}
			
		}
		return count;
	}
    public static void main(String[] args) 
    {
    	Queen8 q = new Queen8();
    }
    
}

参考:
http://www.cnblogs.com/jillzhang/archive/2007/10/21/922830.html
https://baike.baidu.com/item/%E5%9B%9E%E6%BA%AF%E6%B3%95
https://github.com/zhsj/nqueen/blob/master/N%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98.md