n?皇后问题 研究的是如何将 n?个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的?n?皇后问题 的解决方案。
每一种解法包含一个不同的?n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
上代码：
定义全局变量：
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链接：力扣