八皇后算法介绍
知道国际象棋的朋友们应该知道里面的皇后是最厉害的角色,她可以上下左右通吃,和中国象棋里面的车(ju 一声)一样,但是她比车更强大,她可以在斜线上也做到通吃,而我们的八皇后问题其实简单来说就是如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后
八皇后算法思路解析
既然任意一个皇后都无法吃掉其他的皇后,也就是说任两个皇后都不能处于同一条横行、纵行或斜线上,我们将棋盘当做一个二维数组,将皇后的位置标记为1 而其他位置默认都为0,这样我们就可以使用递归的方式将棋盘以打印的方式打印出来,问题也就解决了,下面我将以OC和C语言两种方式来实现,当然思路都是一样的,有些人可能不熟悉OC,所以这里也顺带提供一份C语言的
OC实现八皇后
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
/** 全局的二维数组(用于八皇后递归算法) */
@property(nonatomic,strong) NSMutableArray<NSMutableArray *> *eightQueens;
#pragma mark - 懒加载视图
#pragma mark -
- (NSMutableArray<NSMutableArray *> *)eightQueens {
if (!_eightQueens) {
_eightQueens = [NSMutableArray array];
for ( int i = 0; i < 8; i++) {
NSMutableArray *tempArray = [NSMutableArray array];
for ( int i = 0; i < 8; i++) {
[tempArray addObject:@(0)];
}
[_eightQueens addObject:tempArray];
}
}
return _eightQueens;
}
#pragma mark - OC八皇后递归算法
#pragma mark -
/**
八皇后的递归方法
@param row 开始行
*/
- ( void )eightQueen:( int )row{
if (row == 8) {
NSLog(@ "这是第%lu种解法" ,self.count +1);
for ( int i = 0; i < 8; i++) {
for ( int j = 0; j < 8; j ++) {
printf ( "%d " ,[self.eightQueens[i][j] intValue]);
}
printf ( "\n" );
}
_count++;
} else {
for ( int k = 0; k < 8; k++) {
//查看是否这一行的这些列中是否就是存放皇后的位置
if ([self isQueenPosition:row col:k]) {
//接着下一行找合适的皇后插入位置
[self eightQueen:row + 1];
}
//row行 k列情况试探完毕 将对应位置重置为0 防止干扰下次结果
self.eightQueens[row][k] = @(0);
}
}
}
/**
判断当前位置是否可以存放皇后
@param row 当前要求解的行
@param col 位置的列数
@return 是否可以存放皇后
*/
- ( BOOL )isQueenPosition:( int )row col:( int )col {
//判断列的方向 也就是竖直方向
for ( int i = 0; i < 8; i++) {
if ([self.eightQueens[i][col] integerValue] == 1) {
//表示不能放皇后在这个位置
return NO;
}
}
//判断左上方
for ( int i = row -1,j = col - 1; i >= 0 && j>=0; i--,j--) {
if ([self.eightQueens[i][j] integerValue] == 1) {
//表示不能放皇后在这个位置
return NO;
}
}
//判断右上方
for ( int i = row - 1,j = col + 1; i >= 0 && j < 8 ; i--,j++) {
if ([self.eightQueens[i][j] integerValue] == 1) {
//表示不能放皇后在这个位置
return NO;
}
}
//判断右下方(由于是从第0行开始排列 所以这里可以不用判断)
for ( int i = row,j = col; i < 8 && j < 8; i++,j++) {
if ([self.eightQueens[i][j] integerValue] == 1) {
//表示不能放皇后在这个位置
return NO;
}
}
//判断左下方(由于是从第0行开始排列 所以这里可以不用判断)
for ( int i = row,j = col; i < 8 && j >= 0 ; i++,j--) {
if ([self.eightQueens[i][j] integerValue] == 1) {
//表示不能放皇后在这个位置
return NO;
}
}
//表示这个位置可以放皇后了
self.eightQueens[row][col] = @(1);
return YES;
}
|
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
|
#pragma mark - C语言实现八皇后算法
#pragma mark -
const int QueensNumber = 8 ; //皇后数量
int queens[QueensNumber][QueensNumber] = {0}; //初始化数组
static int QueensCount = 0; //记录解法数量
void printSolution() {
printf ( "这是第%d种解法" ,QueensCount +1);
printf ( "\n" );
for ( int i = 0; i < QueensNumber; i++) {
for ( int j = 0; j < QueensNumber; j ++) {
printf ( "%d " ,queens[i][j]);
}
printf ( "\n" );
}
}
bool rightPosition( int row, int col) {
//判断列也就是竖直方向是否有皇后
for ( int i = 0; i < QueensNumber; i++) {
if (queens[i][col] == 1) {
return false ;
}
}
//判断左上角
for ( int i = row - 1,j = col -1; i >= 0 && j >= 0; i--,j--) {
if (queens[i][j] == 1) {
return false ;
}
}
//判断右上角
for ( int i = row - 1,j = col + 1; i >= 0 && j < QueensNumber; i--,j++) {
if (queens[i][j] == 1) {
return false ;
}
}
//走到这里证明皇后是可以插入的 此时将它标记为1
queens[row][col] = 1;
return true ;
}
void eightQueen( int row) {
if (QueensNumber == row) {
//当行数为8时 直接打印 count++
printSolution();
QueensCount++;
} else {
//判断当前行的所有列中是否有一个位置可以插入皇后
for ( int col = 0; col < QueensNumber; col++) {
if (rightPosition(row,col)) {
//如果上一行位置合适了 接着找下一行
eightQueen(row + 1);
}
//这里如果是不能插入皇后 就要将当前行所有的元素赋值为0 防止对下次造成干扰
queens[row][col] = 0;
}
}
}
|
总结
总得来说C语言的思路和OC是一样的,都是通过递归的方式来寻找皇后合适的插入位置,当然递归并不是唯一的实现方式,今天我们先谈递归的实现,以后有机会我会使用回溯法的方式来实现,有需要的继续关注就好
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:http://www.jianshu.com/p/09726eead9bc?utm_source=tuicool&utm_medium=referral