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

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