当前位置: 代码迷 >> 综合 >> N皇后问题与回溯法
  详细解决方案

N皇后问题与回溯法

热度:86   发布时间:2024-01-16 14:03:33.0

八皇后问题,快三个月了,原来不会写现在还是不会,感觉递归还是不理解,每次看别人的代码都要想一下,更不讲自己写了

这里明显用到了回溯法,这种递归我看看是没问题的,可以说比较简单,但自己写就难了

回溯法要注意一个问题就是:如果在回溯法中用了辅助的全局变量,则一定要把它们恢复原状,特别的,如果函数有多个出口,每个出口都要及时恢复被修改的值

这也是比较好理解的,如果递归不成功返回的时候原本的值要恢复,否则会造成干扰,就像这个n皇后问题,如果i=0搜索完了,那么递归回来时要将原本修改的值全改回来


代码如下:

#include<stdio.h>
#include<string.h>
int c[1000], vis[3][1000];
int n,tot;void search(int cur)
{if (cur == n)tot++;for (int i = 0; i < n; i++){    //同一列;同一反对角线;同一正对角线,+n是为了变成正数,只要行列相减相同即可if (!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]){vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;search(cur + 1);vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;//回溯法每次都要把辅助的全局变量改回来}}
}int main()
{while (scanf("%d", &n), n){tot = 0;memset(vis, 0, sizeof(vis));search(0);printf("the number of the answers:%d\n", tot);}
}



  相关解决方案