八皇后问题

  八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题。

#import "JYCnQueens.h"

@interface JYCnQueens ()

@property (nonatomic, copy) NSMutableDictionary *queensColDic;

@property (nonatomic, assign) NSInteger maxQueens;

@property (nonatomic, assign) NSInteger resultCount;

@end

@implementation JYCnQueens

/// n皇后问题解法
/// @param queenCount 皇后问题个数 n
- (void)findQueen:(NSInteger)queenCount
{
    self.maxQueens = queenCount;
    self.resultCount = 0;
    [self find:0];
    NSLog(@"%ld皇后问题有%ld种解",self.maxQueens,self.resultCount);
}

- (void)find:(NSInteger)queenCount
{
    if (queenCount >= self.maxQueens) {
        // 找到了一个解
        self.resultCount++;
        [self showResult];
        return;
    }
    for (NSInteger row = 0; row < self.maxQueens; row++) {
        if ([self canPutHerCol:queenCount row:row]) {
            self.queensColDic[@(queenCount)] = @(row);
            [self find:queenCount + 1];
            [self.queensColDic removeObjectForKey:@(queenCount)];
        }
    }
}

- (void)showResult
{
    for (NSInteger i = 0; i < self.queensColDic.count; i++) {
        NSInteger putRow = [self.queensColDic[@(i)] integerValue];
        NSMutableArray *rowArray = [NSMutableArray array];
        for (NSInteger j = 0; j < self.queensColDic.count; j++) {
            if (j == putRow) {
                [rowArray addObject:@"1"];
            } else {
                [rowArray addObject:@"0"];
            }
        }
        NSString *rowStr = [rowArray  componentsJoinedByString:@"  "];
        NSLog(@"%@\n",rowStr);
    }
    NSLog(@"------------------------");
}

- (BOOL)canPutHerCol:(NSInteger)col row:(NSInteger)row
{
    for (NSInteger currentCol = 0;currentCol < self.queensColDic.count; currentCol++) {
        NSInteger currentRow = [self.queensColDic[@(currentCol)] integerValue];
        if (currentRow == row || currentCol == col) {
            return NO;
        }
        if (labs(row - currentRow) == labs(currentCol - col)) {
            return NO;
        }
    }
    return YES;
}

- (NSMutableDictionary *)queensColDic
{
    if (!_queensColDic) {
        _queensColDic = [NSMutableDictionary dictionary];
    }
    return _queensColDic;
}

@end