DFS#8 TLE 问一下大佬该如何优化？

#include<bits/stdc++.h>
using namespace std;
int n,a[15][15],vis[15][15],vis2[15][15],ans=0,an[15],cn = 1;
void bfs(int x,int y,int cnt){
    int dx = x-y,dy = y+x;
    for(int i = 1;i<=n;i++){
        if(vis[x][i] == 1 || vis[i][y] == 1 || vis[i+dx][i] == 1 || vis[dy-i][i] == 1){
            return;
        }       
    }
    an[x] = y;
    if(cnt == n) {
        if(cn <= 3){
            for(int i = 1;i<=n;i++){
                cout<<an[i]<<" ";
            }
            cout<<endl;
            cn++;
        }
        ans++;
        return;
    }       
    vis[x][y] = 1;
    for(int i =1;i<=n;i++){
        bfs(x+1,i,cnt+1); 
    }
    vis[x][y] = 0;
    return ;
}
int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        bfs(1,i,1);
    }
    cout<<ans;
    return 0;
}