iOS使用OC写算法之递归实现八皇后

简介

八皇后问题是指在一个 8 x 8 的棋盘上放置 8 个皇后，并且每个皇后之间不能在同一行、同一列或同一对角线，问有多少种不同的摆法。

本文介绍使用 Objective-C 语言实现经典的八皇后问题。

实现思路

八皇后问题可以使用递归方式解决。具体思路如下：

1. 首先在第一行第一列放置一个皇后。
2. 在第二行放置一个皇后，除了第一列之外，可以在任何一列放置，因为在同一列的情况已经被第一行的皇后排除了。
3. 尝试在第三行放置皇后，同时需要排除同一列和同一对角线的情况。
4. 依次重复上述步骤，直到在第八行找到一个可行的方案或者所有的方案都不可行。

代码实现

具体实现可以使用递归方式，在递归的过程中不断地排除不合法的情况。

- (void)solveNQueens {
    NSMutableArray *temp = [NSMutableArray array];
    [self backtrack:temp row:0];
}

- (void)backtrack:(NSMutableArray *)temp row:(NSInteger)row {
    // 如果已经找到了一个可行的方案，则将其加入答案数组中
    if (row == n) {
        [self.result addObject:[temp copy]];
        return;
    }
    // 遍历当前行的所有列，判断是否合法
    for (NSInteger i = 0; i < n; i++) {
        // 判断当前位置是否合法
        if ([self isValidPos:temp row:row col:i]) {
            // 将当前位置加入临时方案数组中
            NSMutableString *rowStr = [NSMutableString string];
            for (NSInteger j = 0; j < n; j++) {
                [rowStr appendString:j == i ? @"Q" : @"."];
            }
            [temp addObject:[rowStr copy]];
            // 继续向下一层递归
            [self backtrack:temp row:row+1];
            // 恢复现场，回溯到上一层
            [temp removeLastObject];
        }
    }
}

- (BOOL)isValidPos:(NSMutableArray *)temp row:(NSInteger)row col:(NSInteger)col {
    // 判断同一列
    for (NSInteger i = 0; i < row; i++) {
        NSString *rowStr = (NSString *)temp[i];
        if ([[rowStr substringWithRange:NSMakeRange(col, 1)] isEqualToString:@"Q"]) {
            return NO;
        }
    }
    // 判断左上方对角线
    for (NSInteger i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
        NSString *rowStr = (NSString *)temp[i];
        if ([[rowStr substringWithRange:NSMakeRange(j, 1)] isEqualToString:@"Q"]) {
            return NO;
        }
    }
    // 判断右上方对角线
    for (NSInteger i = row-1, j = col+1; i >= 0 && j < n; i--, j++) {
        NSString *rowStr = (NSString *)temp[i];
        if ([[rowStr substringWithRange:NSMakeRange(j, 1)] isEqualToString:@"Q"]) {
            return NO;
        }
    }
    return YES;
}

其中，solveNQueens 方法是主方法，backtrack 方法是递归过程中的核心方法，isValidPos 方法用来判断当前空格是否合法。

示例展示

以下是一种可行的八皇后摆法：

["Q.......", "..Q.....", ".......Q", ".....Q..", "...Q....", ".Q......", "....Q...", "......Q."]

以下是该算法在 N = 4 的情况下的一个可行解：

[".Q..", "...Q", "Q...", "..Q."]

总结

通过以上代码实现和示例展示，我们可以看出，该算法使用递归思路比较简洁明了。当然，由于递归这种算法的特性，确保代码的正确性和时间复杂度也需要一定的技巧和经验。