一行,一个正整数n(1<=n<=20)
输出一个整数,代表解的个数。
8
92
20
39029188884
一般的回溯算法只能通过n<=13左右,以下给出n=14到20的答案。
对于想挑战原规模的选手请忽略以下答案。
365596, 2279184, 14772512, 95815104, 666090624, 4968057848, 39029188884
// // Created by yuanhao on 2019-9-3. // #include <iostream> using namespace std; class Solution { long long n; //n个皇后 long long total; //总共的解法 int *c; public: explicit Solution(long long n) : n(n), total(0), c(new int[n]) { } ~Solution() { delete[] c; } long long getTotal() { maxQueen(0); return total; } //八皇后问题共有92种解法(回溯法、递归实现) void maxQueen(int row) { if (row == n) { total++; } else { for (int col = 0; col != n; col++) { c[row] = col; if (isOk(row)) { maxQueen(row + 1); //递归调用,进行下一行的安排 } } } } //判断一个位置是否可以放置皇后 bool isOk(int row) { for (int j = 0; j != row; j++) { if ((c[row] == c[j]) || (row - c[row] == j - c[j]) || (row + c[row] == j + c[j])) return false; } return true; } }; //八皇后问题,是一个古老而著名的问题。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。利用回溯算法我们能很快的得到共有92种互不相同的解(独立解有12种)。当棋盘变成n行,n列,且皇后也有n个的时候(n<=20),问有多少种不同的解? // //输入描述: //一行,一个正整数n(1<=n<=20) // // //输出描述: //输出一个整数,代表解的个数。 //示例1 //输入 //8 //输出 //92 //示例2 //输入 //20 //输出 //39029188884 int main() { long long n = 0; cin >> n; // Solution s(n); // cout << s.getTotal() << endl; // 普通的解法肯定超时,最牛的大牛求解16皇后都要十几秒时间,更别说一秒钟之内求解20皇后问题了 // 所以,下面是唯一的办法了。。。 // 查表法,先全部算好,直接查表就行 // ^(^.^)^ long long a[20] = {1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184, 14772512, 95815104, 666090624, 4968057848, 39029188884}; cout << a[n - 1] << endl; }
#include<bits/stdc++.h> using namespace std; int hashtable[15]={0}; int p[15]; void DFS(int x,int d,int& count){ if(x==d+1){ count++; return; }else{ for(int i=1;i<=d;i++){ if(hashtable[i]==false){ bool flag=true; for(int pre=1;pre<x;pre++){ if(abs(x-pre)==abs(i-p[pre])){ flag=false; break; } } if(flag==true){ p[x]=i; hashtable[i]=true; DFS(x+1,d,count); hashtable[i]=false; } } } } } int main(){ int n; cin>>n; int count=0; DFS(1,n,count); cout<<count<<endl; }//最简单的回溯法,无悬念的超时了
/*用循环递归实现 可惜大数还是超时(ac 65%) */ import java.util.Scanner; public class Main{ public static void main(String []Args) { Scanner in=new Scanner(System.in); int num=in.nextInt();//行数 int count=0; //计数 chess queen=new chess(num); int n=0;//当前行号(0~~num-1) int m=0;//当前列号 if(num==1) { System.out.println("1"); return ; } while(!(n==0&&m>=num))//终点为第一行的所有元素都已经用完 { if(m>=num) //返回时过界(m进行了+1动作) { m=queen.element[--n]+1; continue; } //(1)当前行列号能使用 if(queen.set(n,m)==true) { if(n==num-1)//到达最后一行,记录该方式,回退(下一步让前驱值+1) { count++; m=queen.element[--n]+1;//前一值往后走 continue; } else//往下一行走 { n++;//前进 m=0;//后一值重新考虑所有情况 continue; } } //(2)当前行列号不能使用 else { if(m==num-1)//当前列无可再选,回退 { if(n==0)//当前0行,无可再选 { break; } m=queen.element[--n]+1;//前一值往后走 continue; } else{//往下列走 m++; continue; } } } System.out.println(count); } } class chess{ int[]element; int length; public chess(int n) { this.element=new int[n]; this.length=n; } public boolean set(int n,int m)//判断当前序号下标为n的地方能否插入m { if(n>=this.length||m>=this.length||n<0||m<0)//边界条件 { return false; } for(int i=0;i<n;i++) { if(m==this.element[i]||(m-n)==(this.element[i]-i)||(n+m)==(this.element[i]+i))//斜角及同列判断 { return false; //当前位置不合适,返回 } }//判断结束,可插入 this.element[n]=m; return true;//当前位置不能插入返回错误 } }
var n = parseInt(readline()); var method = 0; function queen(pos){ if(pos.length===n){ // console.log(pos); method++; }else{ for(var i=0; i<n; i++){ var status = true; for(var j=0; j<pos.length; j++){ if(pos[j]===i || pos[j]-i === pos.length-j || pos[j]-i===j-pos.length){ status = false; break; } } if(status){ queen(pos.concat([i])); } } } } if(n<=12){ queen([]); }else{ switch(n){ case 13: method = 73712; break; case 14: method = 365596; break; case 15: method = 2279184; break; case 16: method = 14772512; break; case 17: method = 95815104; break; case 18: method = 666090624; break; case 19: method = 4968057848; break; case 20: method = 39029188884; } } print(method);
#栈代替递归 #木大木大,该超时还是超时... n=int(input()) A, ans=[-1], 0 # 初始list,第n个元素为i,代表第n行第i列,注释中假设以最下面为第0行 while len(A): # list空后结束,即第一行(第0行)所有列的所有可能都已搜索完毕了 for A[-1] in range(A[-1]+1,n): # list中最后一个数字,即循环到的最高一行的列数继续递增 for row in range(len(A)-1): # 这一行和下面一行用来检测纵横斜有没有皇后 if A[row] == A[-1] or abs(A[-1] - A[row]) == len(A) - 1 - row: break # 有皇后break弹出(即不是成功循环结束,不运行循环结束的代码块) else: # 如果循环成功没有皇后 if len(A)==n: ans+=1 # 如果达到n层就输出 else: A += [-1]; break # 没达到则把A往上加一行,break弹出(即不是成功循环结束,不运行循环结束的代码块),加的最上面一行开始寻找 else: A.pop() # 该行的列数成功循环到上限,就把这行pop掉,在次行继续搜索 print(ans)