八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解

我们可以先从数学的角度去思考这个问题:一开始我进入的是误区(对问题条件没有读透彻)直接利用的8!(阶乘)进行运算的,算过之后才觉得自己还是太年轻了。然后我注意到原来斜线也是不能进行放置的,那我就思考到第一个皇后的放置有八种选择,第二个当第一个不在上下边缘的话有六种情况,这六种情况里面对应的分别是第二皇后有五种8-1-2(对角线)种情况,然后第一皇后在上下边缘的时候又分别对与第二皇后的六种(8-1-1)摆放方法,以此类推。但是这个方法的话呢,运算量比较巨大,而且分支讨论的情况太多了,行列数少的时候可以这么计算,多了就反而累赘了。

那么对于计算机来说的话最不怕的就是计算量,所以我们可以实现很简单的穷举法(举出所有的例子,然后筛选出合格的):最简单的肯定是八个for循环解决一切,但是相对的会耗费很多的资源。

在程序员方面关于如何决定下一个皇后能不能放某个位置可以有两种思路,第一种是尝试维护一个8*8的二维矩阵,每次找到一个空位放下一个皇后就把对应行列对角线上的棋格做个标记,如果某行找不到可放皇后的格子就把上一个皇后拿走并把对应行列对角线的标记取消掉;第二种方法直接放弃构造矩阵来假装棋盘,我们把问题更加抽象化,八个皇后能放下一定是一行放一个,我们只需一个数组记录每个皇后的列数(默认第N个放第N行),那么问题就被抽象成了数组的第N个数和前N-1个数不存在几个和差关系即可(比如差不为零代表不在同一列)。

****关于这些在我后面的参考文献里面第一个链接有很好的解释,我也是从中摘录的。

接下来有提供两端代码,摘录自别处,感觉比我自己写得好很多,一个是c一个是C++的因为我觉得这两种语言比较易于理解,而且是大多数人都会的。


/*C++

*这一段代码是摘录自百度百科里面的

*/

#include

using namespace std;

static int gEightQueen[8] = { 0 }, gCount = 0;

 

/*print()

*print就是一个简单数组的输出

*在这里面的存在了两个for循环,当然写成一个for 循环里面进行判断然后输出也是可以的,但是这样就会相对的比较消耗资源,所以写成两个for循环一个判断是比较好的选择

* */

void print()//输出每一种情况下棋盘中皇后的摆放情况

{

 for (int i = 0; i < 8; i++)

 {

  int inner;

  for (inner = 0; inner < gEightQueen[i]; inner++)

   cout << “0”;

  cout <<“#”;

  for (inner = gEightQueen[i] + 1; inner < 8; inner++)

   cout << “0”;

  cout << endl;

 }

 cout << “==========================\n”;

}

/*check_pos_valid

*检查是否存在有多个皇后在同一行/列/对角线的情况

*

*参数

*loop :

*value :

*/

int check_pos_valid(int loop, int value)

{

 int index;

 int data;

 for (index = 0; index < loop; index++)

 {

  data = gEightQueen[index];

  if (value == data)

   return 0;

  if ((index + data) == (loop + value))

   return 0;

  if ((index – data) == (loop – value))

   return 0;

 }

 return 1;

}

void eight_queen(int index)

{

 int loop;

 for (loop = 0; loop < 8; loop++)

 {

  if (check_pos_valid(index, loop))

  {

   gEightQueen[index] = loop;

   if (7 == index)

   {

    gCount++, print();

    gEightQueen[index] = 0;

    return;

   }

   eight_queen(index + 1);

   gEightQueen[index] = 0;

  }

 }

}

int main(int argc, char*argv[])

{

 eight_queen(0);

 cout << “total=” << gCount << endl;

 return 0;

}


/*C

*这一段代码摘录自维基百科

*/

#include

#define QUEENS 8 /*皇后数量*/

#define IS_OUTPUT 1 /*(IS_OUTPUT=0 or 1),Output用于选择是否输出具体解,为1输出,为 >不输出*/

int A[QUEENS + 1], B[QUEENS * 3 + 1], C[QUEENS * 3 + 1], k[QUEENS + 1][QUEENS + 1];

int inc, *a = A, *b = B + QUEENS, *c = C;

void lay(int i)

{

 int j = 0, t, u;

 while (++j <= QUEENS)

  if (a[j] + b[j - i] + c[j + i] == 0)

  {

   k[i][j] = a[j] = b[j - i] = c[j + i] = 1;

   if (i < QUEENS) lay(i + 1);

   else

   {

    ++inc;

    if (IS_OUTPUT)

    {

     for (printf("(%d)\n", inc), u = QUEENS + 1; --u; printf("\n"))

      for (t = QUEENS + 1; --t; ) k[t][u] ? printf("Q ") : printf("+ ");

       printf("\n\n\n");

    }

   }

   a[j] = b[j - i] = c[j + i] = k[i][j] = 0;

  }
}

int main(void)

{

 lay(1);

 printf("%d皇后共计%d个解\n", QUEENS, inc);

 getchar();

 return 0;

}


https://blog.csdn.net/codes_first/article/details/78474226
https://www.cnblogs.com/space-place/p/6253542.html