one recursive approach to solve hdu 1016, list all permutations, solve N-Queens puzzle. reference: the video of stanford cs106b lecture 10 by Julie Zelenski https://www.youtube.com/watch?v=NdF1QDTRkck
// hdu 1016, 795MS
const int MAXN=20;bool isPrime(int k) {static std::string prime={3,5,7,11,13,17,19,23,29,31,37}; return prime.find(k)!=std::string::npos;}void printResult(std::string str) {static char strbuf[2*MAXN+5], *p;p=strbuf;for(auto v:str) { p+=sprintf(p,”%d “,(int)v); }*–p=0;puts(strbuf);}void recSolvePrimeRing(std::string soFar, std::string rest) {if(rest.size()==1) {if(isPrime(rest[0]+soFar.back()) && isPrime(rest[0]+soFar.front()))printResult(soFar+rest);return;}for(int i=0;i<rest.size();++i) {int x=rest[i]+soFar.back();if(isPrime(rest[i]+soFar.back())) {recSolvePrimeRing(soFar+rest[i],rest.substr(0,i)+rest.substr(i+1));}}}void solvePrimeRing(int n) {static std::string rest{‘\002’};if(rest.back()<=n)for(int i=rest.back()+1;i<=n;++i) rest.push_back(i);else rest.resize(n-1);recSolvePrimeRing(“\001”,rest);}int main() {#ifndef ONLINE_JUDGEfreopen(“in.txt”,”r”,stdin);#endifint n,k=0;while(scanf(“%d”,&n)==1) {if(n>0 && n<=MAXN && (n&1)==0) {printf(“Case %d:\n”,++k);solvePrimeRing(n);putchar(‘\n’);}}return 0;}
// improved version for hdu 1016, 483MS, // encapsulated to a Solution class, function isprime more speedy,
{static const std::string primetable;static std::string prime;static inline bool isPrime(int k) {return (k&1) && prime.find(k)!=std::string::npos;}static void printResult(const std::string &str) {static char strbuf[2*MAXN+5], *p;p=strbuf;for(auto v:str) { p+=sprintf(p,”%d “,(int)v); }*–p=0;puts(strbuf);}static void recSolvePrimeRing(std::string soFar, std::string rest) {static int tmp;if(rest.size()==1) {if(isPrime(rest[0]+soFar.back()) && isPrime(rest[0]+soFar.front()))printResult(soFar+=rest);return;}for(int i=0;i<rest.size();++i) {if(isPrime(rest[i]+soFar.back())) {recSolvePrimeRing(soFar+rest[i],rest.substr(0,i)+rest.substr(i+1));}}}public:MAXN=20;static void solve(int n) {if(n>MAXN || n<2 || (n&1)) { return; }static std::string rest{‘\002’};if(rest.back()<=n)for(int i=rest.back()+1;i<=n;++i) rest.push_back(i);else rest.resize(n-1);prime.clear();n<<=1;for(int i=0;primetable[i]<n;++i) {prime.push_back(primetable[i]);}recSolvePrimeRing(“\001”,rest);}};const std::string SolutionPrimeRing::primetable={3,5,7,11,13,17,19,23,29,31,37,41};std::string SolutionPrimeRing::prime;int main() {#ifndef ONLINE_JUDGEfreopen(“in.txt”,”r”,stdin);#endifint n,k=0;while(scanf(“%d”,&n)==1) {printf(“Case %d:\n”,++k);SolutionPrimeRing::solve(n);putchar(‘\n’);}return 0;}找一个让心里安静和干净的地方，
