尝试用BFS解决这个问题，最后超时了，有大佬可以教教优化的方法吗？

#include<iostream>
#include<queue>
using namespace std;

int tmp[100];

int n;
int tmp1;
int tmp2;

int otp = 3;
int cnt = 0;

struct sj
{
    int rw;
    int ret[100];
};

queue<sj> que;

void canbeput(int result[], int row)//目前要排第row行的棋子 
{
    for (int i = 1; i <= n; ++i)
    {
        tmp[i] = 1;
    }

    for (int i = 1; i < row; ++i)
    {
        tmp[result[i]] = 0;
        tmp1 = result[i];
        tmp2 = result[i];
        for (int j = i; j < row; ++j)
        {
            tmp1++;
            tmp2--;
        }
        if (tmp1 <= n) tmp[tmp1] = 0;
        if (tmp2 >= 1) tmp[tmp2] = 0;
    }
    //tmp中1的位置即为可以放棋子的位置 
}

void bfs()
{
    for (int i = 1; i <= n; ++i)
    {
        sj tmp;
        tmp.ret[1] = i;
        tmp.rw = 1;
        que.push(tmp);
    }
    while (!que.empty())
    {
        sj noww;
        noww = que.front();
        que.pop();
        if (noww.rw == n)
        {
            otp--;
            cnt++;
            if (otp >= 0)
            {
                for (int i = 1; i <= n; ++i)
                {
                    cout << noww.ret[i] << " ";
                }
                cout << endl;
            }
            continue;
        }
        canbeput(noww.ret, noww.rw+1);
        for (int i = 1; i <= n; ++i)
        {
            if (tmp[i] == 1)
            {
                sj neww;
                neww = noww;
                neww.rw++;
                neww.ret[neww.rw] = i;
                que.push(neww);
            }
        }
    }
    cout << cnt << endl;
}

int main()
{
    cin >> n;
    bfs();
    return 0;
}