n皇后问题（回溯法优化和拉斯维加斯算法）附完整代码，代码简洁

问题描述：

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

算法思路：

一、使用回溯法，即先穷举后优化的思想。ps：data[0] = 2表示第1列的第二个

• 先穷举出所有的可能性
• 检查是否符合不在同一行或同一斜线上
• 再优化：
  不满足的就不执行了

if (index > 1) {
    if (!check_data(data, index - 1)) return;
  }

注意，这里只需检查是否在同一行或同一斜线上即可，因为本身就是一个赋一个位置的值 然后赋下一列的，同一列的不会赋两次值，就不用判断。

if (data[index] == data[i])
      //判断是否在一行
      return false;

    if ((index + data[index]) == (i + data[i]))
      if (data[index] == data[i])
      //判断是否在一行
      return false;

    if ((index + data[index]) == (i + data[i]))
      //判断斜向上的对角线 (行号+列号) 和相等
      return false;

    if ((index - data[index]) == (i - data[i]))
      //判断斜向下的对角线（行号-列号）差相等
      return false;
}

完整代码：

#include <iostream>
#include <vector>
using namespace std;

const int N = 4;
static int count = 0;

bool check_data(vector<int> &data, int index) {
  //本身就是一个付一个位置的值,然后付下一列的,同一列的不会付两次值,就不用判断是否在同一列
  if (index == 0) return true;
  for (int i = 0; i < index; i++) {
    if (data[index] == data[i])
      //判断是否在一行
      return false;

    if ((index + data[index]) == (i + data[i]))
      //判断斜向上的对角线 (行号+列号)是否相等
      return false;

    if ((index - data[index]) == (i - data[i]))
      //判断斜向下的对角线（行号-列号）是否相等
      return false;
  }

  return check_data(data, index - 1);  //回溯
}

void init_data(vector<int> &data, int index) {
  if (index == N) {
    if (check_data(data, N - 1)) {
      for (int i = 0; i < data.size(); i++) {
        cout << data[i] << " ";
      }
      count++;
      cout << endl;
    }
    return;  //递归退出
  }

  if (index > 1) {
  	//剪枝优化
    if (!check_data(data, index - 1)) return;
  }

  //递归穷举
  for (int i = 1; i <= N; i++) {
    data[index] = i;
    init_data(data, index + 1);  //横走
  }
}

int main() {
  vector<int> data(N);
  init_data(data, 0);
  cout << "有" << count << "种解" << endl;
  return 0;
}

二、拉斯维加斯算法

拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解，因此通常用一个bool型函数表示拉斯维加斯型算法。当算法找到一个解时，返回true，否则返回一个false。

说明：在用回溯发解n后问题时，实际上是在系统地搜索整个解空间树的过程中找出满足要求的解。但忽略了一个重要事实：对于n后问题的任何一个解而言，每个皇后在棋盘上的位置无任何规律，不具有系统性，而更像是随机放置的。由此容易想到下面的拉斯维加斯算法。在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容的放置好，或已没有下一个皇后的可放置位置时为止。

完整代码：

#include <iostream>
#include <vector>
using namespace std;

const int N = 4;
static int count = 0;

bool check_data(vector<int> &data, int index) {
  //本身就是一个付一个位置的值,然后付下一列的,同一列的不会付两次值,就不用判断是否在同一列
  if (index == 0) return true;
  for (int i = 0; i < index; i++) {
    if (data[index] == data[i])
      //判断是否在一行
      return false;

    if ((index + data[index]) == (i + data[i]))
      //判断斜向上的对角线 (行号+列号)相等
      return false;

    if ((index - data[index]) == (i - data[i]))
      //判断斜向下的对角线（行号-列号）相等
      return false;
  }

  return check_data(data, index - 1);  //回溯
}

void lasVegas() {
  vector<int> data(N);
  while (1) {
    for (int i = 0; i < data.size(); i++) {
      data[i] = 1 + rand() % N;  //产生1-4之间的数（0—3）+1
    }

    if (check_data(data, N)) {
      for (int i = 0; i < data.size(); i++) {
        cout << data[i] << " ";
      }
      cout << endl;
      return;
    }
  }
}

int main() {
  lasVegas();
  // cout << "有" << count << "种解" << endl;
  return 0;
}