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

/** 全局的二维数组（用于八皇后递归算法） */@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 位置的列数 @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语言实现八皇后算法#pragma mark -const int QueensNumber = 8 ;//皇后数量int queens[QueensNumber][QueensNumber] = {0};//初始化数组static int QueensCount = 0;//记录解法数量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) {    //当行数为8时 直接打印 count++    printSolution();    QueensCount++;  }else {    //判断当前行的所有列中是否有一个位置可以插入皇后    for (int col = 0; col < QueensNumber; col++) {      if (rightPosition(row,col)) {        //如果上一行位置合适了 接着找下一行        eightQueen(row + 1);      }      //这里如果是不能插入皇后 就要将当前行所有的元素赋值为0 防止对下次造成干扰      queens[row][col] = 0;    }  }}