锐客网

  1. 首页 > it技术 > >

八皇后问题----回溯法的应用(c语言描述)

其他

题目简介：
在8*8的国际象棋棋盘上，要求在每一行(或者每一列)放置一个皇后，且能做到在水平方向、竖直方向和斜方向都没有冲突。请列出所有解法。
思路：
八皇后问题是回溯法解题的基本问题。首先我们考虑一种简单情况—四皇后问题。四皇后问题我们的思路是，先在棋盘的第一行第一列放第一颗子。在下第二颗子的时候我们同样希望它被放置在第一行，即第一行第二列，但显然违背了题目要求。所以尝试其放于第二行第二列，但我们发现，这时其又不满足斜方向冲突的要求。所以尝试将其放到第三行第二列。在我们放置第三颗子时，根据前面的经验，首先尝试第一行第三列，与第一颗子在同一行，失败！尝试第二行第三列，与第二颗子在斜方向，失败！尝试第三行第三列，与第二颗子在同一行，失败！尝试第四行第三列，与第二颗子在斜方向，失败！
全部失败，仿佛我们没有了办法，这时该怎么办呢？没错，我们可以调整上一颗棋子的位置来使第三颗棋子有地可下！同样的道理，如果再失败，我们可以调整上上颗的位置。这，就是我们的回溯法了，在子问题走不通的情况下，返回上一个问题的另外一种情况。下面上代码：

#include #include #include int sum=0; int main() { int a[100]; Serch(a,0); printf("%d\n",sum); return 0; } void Serch(int a[],int current_layer) { //终止情况 if(current_layer>=8) { sum++; return; } //遍历可行的行 for(int i=0; i<8; i++) { a[current_layer]=i; if(check(a,current_layer)) Serch(a,current_layer+1); a[current_layer]=NULL; } } //判定放子是否正确的函数 intcheck(int a[],int n) { if (n==0) return 1; for(int i=0; i

【八皇后问题----回溯法的应用(c语言描述)】有问题可在评论贴出，一般都会看，转载请注明出处！

    推荐阅读


    上一篇：操作系统|大话程序链接过程（一）

    下一篇：pwn|2017 0ctf babyheap