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

八皇后算法介绍

知道国际象棋的朋友们应该知道里面的皇后是最厉害的角色，她可以上下左右通吃，和中国象棋里面的车（ju 一声）一样，但是她比车更强大，她可以在斜线上也做到通吃，而我们的八皇后问题其实简单来说就是如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后

八皇后算法思路解析

既然任意一个皇后都无法吃掉其他的皇后，也就是说任两个皇后都不能处于同一条横行、纵行或斜线上，我们将棋盘当做一个二维数组，将皇后的位置标记为1 而其他位置默认都为0，这样我们就可以使用递归的方式将棋盘以打印的方式打印出来，问题也就解决了，下面我将以oc和c语言两种方式来实现，当然思路都是一样的，有些人可能不熟悉oc，所以这里也顺带提供一份c语言的

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;
}

c语言实现八皇后

#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;
    }
  }
}

总结

总得来说c语言的思路和oc是一样的，都是通过递归的方式来寻找皇后合适的插入位置，当然递归并不是唯一的实现方式，今天我们先谈递归的实现，以后有机会我会使用回溯法的方式来实现，有需要的继续关注就好

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。