题目:将上下对称、左右对称棋局、主副对角线对称棋局和旋转后重复视为重复,则要求输出去重后的N皇后问题的棋盘布局
这道题是一道作业题,我都惊到了,一向弱智的作业题中竟然冒出一道这样的题,这题最起码橙黄之间的难度,标个黄应该也没什么问题。我竟然写了一百多行代码,在不影响可读性的情况下去掉无用行后仍有98行(如果舍弃结构化编程思想全部写入主函数内的话还能再减少几十行,但那是很不好的编程习惯,所以没那么做)。可见这道作业题还是蛮麻烦的,总体来说就是一个模拟方阵各类操作+常规N皇后求解的问题
Code
#include <iostream>
#include <vector>
using namespace std;
int N,ans;
vector<int> S,A[20];
int ud(const vector<int>& A,const vector<int>& B)
{
for(int i=1;i<=N;i++)
if(A[i]!=B[N+1-i])//i,j->n+1-i,j
return 0;
return 1;
}
int lr(const vector<int>& A,const vector<int>& B)
{
for(int i=1;i<=N;i++)
if(A[i]+B[i]!=N+1)//i,j->i,n+1-j
return 0;
return 1;
}
int lk(const vector<int>& A,const vector<int>& B)
{
for(int i=1;i<=N;i++)
if(i+B[N+1-A[i]]!=N+1) //i,j->n+1-j,n+1-i
return 0;
return 1;
}
int rk(const vector<int>& A,const vector<int>& B)
{
for(int i=1;i<=N;i++) //i,j->j,o
if(B[A[i]]!=i)
return 0;
return 1;
}
const vector<int> spin(const vector<int> A)
{
vector<int>B;//i,j->j,n+1-i
for(int i=0;i<=N;i++)
B.push_back(0);
for(int i=1;i<=N;i++)
B[A[i]]=N+1-i;
return B;
}
int r1(const vector<int>& A,const vector<int>& B)
{
if(spin(A)==B)return 1;
return 0;
}
int r2(const vector<int>& A,const vector<int>& B)
{
if(spin(spin(A))==B)return 1;
return 0;
}
int r3(const vector<int>& A,const vector<int>& B)
{
if(spin(spin(spin(A)))==B)return 1;
return 0;
}
void f(int n)
{
if(n==N+1)
{
for(int i=1;i<=ans;i++)
if(ud(A[i],S)||lr(A[i],S)||lk(A[i],S)||rk(A[i],S)||r1(A[i],S)||r2(A[i],S)||r3(A[i],S))
return;
A[++ans]=S;
}
for(int i=1;i<=N;i++)
{
int flag=1;
for(int k=1;k<n;k++)
if(S[k]==i||S[k]-k==i-n||S[k]+k==i+n)
{
flag=0;
break;
}
if(flag==1)
{
S.push_back(i);
f(n+1);
S.pop_back();
}
}
}
signed main()
{
cin>>N;
S.push_back(0);
f(1);
for(int i=1;i<=ans;i++)
{
cout<<"No"<<i<<':';
for(int j=1;j<=N;j++)
cout<<A[i][j]<<' ';
cout<<endl;
}
return 0;
}