/** 全局的二維數(shù)組（用于八皇后遞歸算法） */
@property(nonatomic,strong) NSMutableArray<NSMutableArray *> *eightQueens;

#pragma mark - 懶加載視圖
#pragma mark -
- (NSMutableArray<NSMutableArray *> *)eightQueens {
  if (!_eightQueens) {
    _eightQueens = [NSMutableArray array];
    for (int i = 0; i < 8; i++) {
      NSMutableArray *tempArray = [NSMutableArray array];
      for (int i = 0; i < 8; i++) {
        [tempArray addObject:@(0)];
      }
      [_eightQueens addObject:tempArray];
    }
  }
  return _eightQueens;
}

#pragma mark - OC八皇后遞歸算法
#pragma mark -

/**
 八皇后的遞歸方法

 @param row 開始行
 */
- (void)eightQueen:(int)row{
  if (row == 8) {
    NSLog(@"這是第%lu種解法",self.count +1);
    for (int i = 0; i < 8; i++) {
      for (int j = 0; j < 8; j ++) {
        printf("%d ",[self.eightQueens[i][j] intValue]);
      }
      printf("\n");
    }
    _count++;

  }else {
    for (int k = 0; k < 8; k++) {
      //查看是否這一行的這些列中是否就是存放皇后的位置
      if ([self isQueenPosition:row col:k]) {
        //接著下一行找合適的皇后插入位置
        [self eightQueen:row + 1];
      }
      //row行 k列情況試探完畢 將對應位置重置為0 防止干擾下次結果
      self.eightQueens[row][k] = @(0);
    }
  }
}


/**
 判斷當前位置是否可以存放皇后

 @param row 當前要求解的行
 @param col 位置的列數(shù)
 @return 是否可以存放皇后
 */
- (BOOL)isQueenPosition:(int)row col:(int)col {
  //判斷列的方向 也就是豎直方向
  for (int i = 0; i < 8; i++) {
    if ([self.eightQueens[i][col] integerValue] == 1) {
      //表示不能放皇后在這個位置
      return NO;
    }
  }
  //判斷左上方
  for (int i = row -1,j = col - 1; i >= 0 && j>=0; i--,j--) {
    if ([self.eightQueens[i][j] integerValue] == 1) {
      //表示不能放皇后在這個位置
      return NO;
    }
  }

  //判斷右上方
  for (int i = row - 1,j = col + 1; i >= 0 && j < 8 ; i--,j++) {
    if ([self.eightQueens[i][j] integerValue] == 1) {
      //表示不能放皇后在這個位置
      return NO;
    }
  }

  //判斷右下方（由于是從第0行開始排列 所以這里可以不用判斷）
  for (int i = row,j = col; i < 8 && j < 8; i++,j++) {
    if ([self.eightQueens[i][j] integerValue] == 1) {
      //表示不能放皇后在這個位置
      return NO;
    }
  }


  //判斷左下方（由于是從第0行開始排列 所以這里可以不用判斷）
  for (int i = row,j = col; i < 8 && j >= 0 ; i++,j--) {
    if ([self.eightQueens[i][j] integerValue] == 1) {
      //表示不能放皇后在這個位置
      return NO;
    }
  }
  //表示這個位置可以放皇后了
  self.eightQueens[row][col] = @(1);
  return YES;
}

#pragma mark - C語言實現(xiàn)八皇后算法
#pragma mark -
const int QueensNumber = 8 ;//皇后數(shù)量
int queens[QueensNumber][QueensNumber] = {0};//初始化數(shù)組
static int QueensCount = 0;//記錄解法數(shù)量

void printSolution() {
  printf("這是第%d種解法",QueensCount +1);
  printf("\n");
  for (int i = 0; i < QueensNumber; i++) {
    for (int j = 0; j < QueensNumber; j ++) {
      printf("%d ",queens[i][j]);
    }
    printf("\n");
  }
}

bool rightPosition(int row,int col) {
  //判斷列也就是豎直方向是否有皇后
  for (int i = 0; i < QueensNumber; i++) {
    if (queens[i][col] == 1) {
      return false;
    }
  }

  //判斷左上角
  for (int i = row - 1,j = col -1; i >= 0 && j >= 0; i--,j--) {
    if (queens[i][j] == 1) {
      return false;
    }
  }

  //判斷右上角
  for (int i = row - 1,j = col + 1; i >= 0 && j < QueensNumber; i--,j++) {
    if (queens[i][j] == 1) {
      return false;
    }
  }

  //走到這里證明皇后是可以插入的 此時將它標記為1
  queens[row][col] = 1;
  return true;
}

void eightQueen(int row) {
  if (QueensNumber == row) {
    //當行數(shù)為8時 直接打印 count++
    printSolution();
    QueensCount++;
  }else {
    //判斷當前行的所有列中是否有一個位置可以插入皇后
    for (int col = 0; col < QueensNumber; col++) {
      if (rightPosition(row,col)) {
        //如果上一行位置合適了 接著找下一行
        eightQueen(row + 1);
      }
      //這里如果是不能插入皇后 就要將當前行所有的元素賦值為0 防止對下次造成干擾
      queens[row][col] = 0;
    }
  }
}