I am doing an exhaustive search in N-queens code I wrote in C++. How can I optimize this code further?
It takes an input n
(the number of queens) and returns a vector<vector<string>>
having all possible arrangements. Looking at the code, I think the operations like pop_back()
is slowing the entire runtime.
#include "stdafx.h"
#include "string"
#include "vector"
using namespace std;
//Struct to store previously placed queens.
struct rowCol {
int row;
int col;
rowCol(int r, int c) {
row = r;
col = c;
}
};
class Solution {
public:
bool check(int row, int col, vector<rowCol*>& history) {
//check diagonals
for (auto i : history) {
if (abs(i->row - row) == abs(i->col - col))
return 0;
}
//check columns
for (auto i : history) {
if (i->col == col)
return 0;
}
return 1;
}
void recurse(vector<rowCol*>& history, int row, int n,vector<string>& res,vector<vector<string>>& result) {
if (row < n) {
for (int j = 0; j < n; j++) {
if (check(row, j, history)) {
std::string x(n, '.');
history.push_back(new rowCol(row, j));
x[j] = 'Q';
res.push_back(x);
if (res.size() == n) {
result.push_back(res);
}
recurse(history, row+1, n, res,result);
res.pop_back();
history.pop_back();
}
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<rowCol*> history;
vector<string> res;
recurse(history, 0, n,res,result);
return result;
}
};
int main()
{
Solution s;
s.solveNQueens(4);
return 0;
}