#### DFS n-queens problem. Why my code is so slow?

Recently got an assignment on solving n-queens problem using BFS/DFS.
My BFS stops at N=7 and I think it’s understandable but DFS has problem with N=8 and goes on for few minutes.

Do you have any suggestions how to speed it up?
Also can you recommend what should I learn to speed up my code in general?

Here’s my code:

``````#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <chrono>
#include <stack>

using namespace std;

const int N = 6;

int states_generated = 1;

void tree(vector<int> data) {
string arr[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
arr[i][j] = " -";
}
}

for (int i = 0; i < data.size(); i++) {
arr[data[i] - 1][i] = " *";
}

cout << endl;

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << arr[i][j];
}
cout << endl;
}
}

vector<int>* gen_v_variants(vector<int> parent) {
if (parent.size() == N) return nullptr;

vector<int>* vector_box = new vector<int>[N];

for (size_t i = 0; i < N; i++) {
vector_box[i] = parent;
vector_box[i].push_back(i + 1);
states_generated++;
}

return vector_box;
}

struct Node {
vector<int> queens;
bool checked = false;
queue<vector<int>> kids;

Node(vector<int> queens) {
this->queens = queens;
vector<int>* vector_box = gen_v_variants(queens);

if (vector_box != nullptr) {
for (int i = 0; i < N; i++) {
kids.push(vector_box[i]);
}
}

delete[] vector_box;
}

bool check() {
checked = (this->kids.size() == 0) ? true : false;
return checked;
}

~Node() {
}
};

bool validator(vector<int> data) {
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (data[i] == data[j] || abs(i - j) == abs(data[i] - data[j])) return false;
}
}

tree(data);
return true;
}

class DFS {
public:
int N;
stack<Node> st;
int states_checked = 0;
int n_queens_solved = 0;

DFS(int N, Node data) {
this->N = N;
this->st.push(data);
}

void begin() {
while (this->st.size() > 0) {

if (this->st.top().queens.size() < N && !this->st.top().check()) {
}
else if (this->st.top().queens.size() == N) {

if (validator(st.top().queens)) {
this->n_queens_solved++;
this->states_checked++;
}
else {
this->states_checked++;
}

this->st.top().checked = true;
st.pop();
}
else if (this->st.top().check()) {

st.pop();
}

}

result();
}

Node* parent = &this->st.top();
st.push(parent->kids.front());
parent->kids.pop();
parent = nullptr;
}

void result() {
cout << endl << "States: " << states_generated << "nStates checked for n-queen problem: " << this->states_checked
<< "nN-Queens problems solved: " << this->n_queens_solved << endl;
}

~DFS() {}
};

int main() {
using chrono::high_resolution_clock;
using chrono::duration_cast;
using chrono::duration;
using chrono::milliseconds;

auto t1 = high_resolution_clock::now();
vector<int> start;
Node a(start);
DFS test(N, a);
test.begin();
auto t2 = high_resolution_clock::now();

duration<double, milli> ms_double = t2 - t1;
cout << ms_double.count() / 1000 << "s";

}
``````

Source: Windows Questions C++