LeetCode51 -- iOS使用OC写算法之递归实现N皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
输入：n = 4输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
_cols、_pie、_na为攻击范围
_pie中数据的关系：行+列等于一个常数
_na中数据的关系：行 - 列等于一个常数
上代码：
定义全局变量：
NSMutableArray *_result;
NSMutableArray *_cols;
NSMutableArray *_pie;
NSMutableArray *_na;
具体实现：
-(NSArray *)solveNQueens {
int n = 4;
if (n < 1) {
return @[];
}
_result = [NSMutableArray new];
/** 列 */
_cols = [NSMutableArray new];
/** 丿 */
_pie = [NSMutableArray new];
/** 捺 */
_na = [NSMutableArray new];
[self solveNQueensWidhDFS:n row:0 cur_state:[NSMutableArray new]];
return [self _generate_result:n];
}
-(void)solveNQueensWidhDFS:(int)n row:(int)row cur_state:(NSMutableArray *)cur_state {
if (row >= n) {
[_result addObject:cur_state];
return;
}
for (int col = 0; col < n; col ++) {
if ([_cols containsObject:@(col)] || [_pie containsObject:@(row + col)] || [_na containsObject:@(row - col)]
) {
continue;
}
[_cols addObject:@(col)];
[_pie addObject:@(row + col)];
[_na addObject:@(row - col)];
NSMutableArray *c = [NSMutableArray new];
[c addObjectsFromArray:cur_state];
[c addObject:@(col)];
[self solveNQueensWidhDFS:n row:row + 1 cur_state:c];
[_cols removeObject:@(col)];
[_pie removeObject:@(row + col)];
[_na removeObject:@(row - col)];
}
}
-(NSArray *)_generate_result:(int)n {
NSMutableArray *board = [NSMutableArray new];
for (NSArray *res in _result) {
for (NSNumber *i in res) {
NSString *point1 = [self string:i.intValue];
NSString *point2 = [self string:n - i.intValue - 1];
NSString *q = [NSString stringWithFormat:@"%@%@%@",point1,@"Q",point2];
[board addObject:q];
}
}
return board;
}
-(NSString *)string:(int)num {
NSString *string = @"";
for (int i = 0; i < num; i ++) {
string = [string stringByAppendingString:@"."];
}
return string;
}
leetcode链接：https://leetcode-cn.com/problems/n-queens/
