n皇后问题

xiaoxiao2021-02-28  11

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

n皇后问题可以用暴力求解,同时也是回溯法应用的一个经典案例

参考代码如下:

#include<stdio.h> //回溯+暴力 #include<math.h> int count1=0; int judge(int t,int *a1){ int i; int j; for(i=0;i<t;i++){ for(j=i+1;j<=t;j++){ if(a1[i]==a1[j]){ return 0; } if(abs(i-j)==abs(a1[i]-a1[j])) return 0; } } return 1; } void traceback(int t,int n,int *a1){ int i; if(t==n){ count1++; for(i=0;i<n;i++){ printf("%d",a1[i]); } printf("\n"); return ; } for(i=0;i<n;i++){ a1[t]=i; if(judge(t,a1)) traceback(t+1,n,a1); } } int main(){ int count=0; int i,j,k; int *a,*a1; int num,n; printf("number:"); scanf("%d",&n); a = new int[n]; a1 = new int[n]; for(i=0;i<n;i++){ a1[i]=0; } for(num=0;num<pow(n,n);num++){ j = num; for(i=0;i<n;i++){ a[i]=j%n; j= j/n; } k=1; for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ if(a[i]==a[j] || abs(i-j)==abs(a[i]-a[j])){ //排除掉不同列同一行以及同一斜线上的情况 k=0; break; } } } if(k==1) count++; } printf("result:%d\n",count); traceback(0,n,a1); printf("%d\n",count1); return 0; } 因为是在暴力求解的代码上直接加的回溯法,会有些乱,望海涵。

转载请注明原文地址: https://www.6miu.com/read-1750335.html

最新回复(0)