??八皇后問題是一個(gè)以國(guó)際象棋為背景的問題：如何能夠在 8×8 的國(guó)際象棋棋盤上放置八個(gè)皇后，使得任何一個(gè)皇后都無法直接吃掉其他的皇后？為了達(dá)到此目的，任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的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 皇后問題個(gè)數(shù) 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) {
        // 找到了一個(gè)解
        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