I am a 16 years old guy and recently I was solving n-queens problem but my code is giving different answers.Basically my code's intention is to put a queen on a specific row and then mark the left diagonals as well as right diagonals and columns marked as danger.And then placing other queens on the other positions where is no danger.Please explain briefly what is the problem in my code.
vector<vector<int>> v;
int c=0;
void solve(int y){
if(y==v.size()){// base case
c++;
return ;
}
else{
for(int i=0;i<v.size();i++){
if(v[y][i]!= -1) continue;
else{
int a=y,b=i;
while(a<v.size() && b<v[y].size()){// marking all right diagonals as danger
v[a][b]=y;
++a;
++b;
}
a=y,b=i;
while(a<v.size() && b>=0){ // marking left diagonals as danger
v[a][b]=y;
++a;
--b;
}
a=y,b=i;
while(a<v.size()){// marking columns as danger
v[a][b]=y;
++a;
}
solve(y+1);//recursive call and also the starting point of backtracking
a=y,b=i;
while(a<v.size() && b<v[y].size()){
v[a][b]=-1;
++a;
++b;
}
a=y,b=i;
while(a<v.size() && b>=0){
v[a][b]=-1;
++a;
--b;
}
a=y,b=i;
while(a<v.size()){
v[a][b]=-1;
++a;
}
}
}
}
}
int main(){
int n;
cin>>n;
v.resize(n,vector<int>(n,-1);
solve(0);
cout<<c<<endl;
}
Edit: I have modified my code and after this I inspected the backtracking and my question is why each i is making 2 calls
vector<vector<int>> v;
int c=0;
void solve(int y){
if(y==v.size()){
c++;
return ;
}
else{
for(int i=0;i<v.size();i++){
if(v[y][i]!= -1) continue;
for(int j=0;j<v[y].size();j++){
v[y][j]=y;
}
int a=y,b=i;
while(a<v.size() && b<v[y].size()){
v[a][b]=y;
a++;
b++;
}
a=y,b=i;
while(a<v.size() && b>=0){
v[a][b]=y;
a++;
b--;
}
a=y,b=i;
while(a<v.size()){
v[a][b]=y;
a++;
}
// Inspecting before the recursion call
cout<<"When y is "<<y<<endl;
for(auto i:v){
for(int j:i){
cout<<j<<" ";
}
cout<<endl;
}
solve(y+1);
a=y,b=i;
while(a<v.size() && b<v[y].size()){
v[a][b]=-1;
a++;
b++;
}
a=y,b=i;
while(a<v.size() && b>=0){
v[a][b]=-1;
a++;
b--;
}
a=y,b=i;
while(a<v.size()){
v[a][b]=-1;
a++;
}
for(int j=0;j<v[y].size();j++){
v[y][j]=-1;
}
// this is basically for seeing what is happening after the recursive call
cout<<"When y is "<<y<<endl;
for(auto i:v){
for(int j:i){
cout<<j<<" ";
}
cout<<endl;
}
}
}
}
Please explain why it is printing each i for 4 times :(
Without digging into too deep you have a fundamental problem:
You mark all further fields reachable from current one with your current recursion depth and reset all of these unconditionally to -1. So you clear out the marks yet incomplete previous recursions, too.
Without digging too deep into the code I noticed that you do not mark the columns.
However, introducing that, you will risk illegally overwriting marks set in previous columns:
q _ _ _ _ _ _ _
- + _ Q _ _ _ _
- - X - * - - -
- * - + - * - -
...
-: free field
_: implicit danger of any queen
q: first queen
+: danger of first queen
Q: second queen
*: danger of second queen
X: danger of second queen overwriting danger of previous queen
Additionally, you do not mark the column fields for the queues (just going downwards from current queen). Introducing this, the problem gets even worse.
So you need a couple of changes:
while(/*...*/) // for any loop before recursive call:
{
if(v[a][b] == -1)
v[a][b] = y;
}
Same way, you need to remove the mark only if it has been set with current recursion:
while(/*...*/) // for any loop after recursive call:
{
if(v[a][b] == y)
v[a][b] = -1;
}
By the way (core problem solved here, from now on following some recommendations to improve your code – including a modified algorithm not suffering from the overwrite problem): You can combine all your while loops – before and after recursive call respectively – into one single loop:
int a = i, b = i, max = v[y].size() - 1;
for(int j = y + 1; j < v.size(); ++j)
{
if(v[j][i] == -1)
v[j][i] = y;
if(a > 0)
{
--a;
if(v[j][a] == -1)
v[j][a] = y;
}
if(b < max)
{
++b;
if(v[j][b] == -1)
v[j][b] = y;
}
}
If you look more closely, you'll notice that the the loops do not differ before and after the recursive call – apart from -1 and y being swapped.
So you could combine into a separate function (or local lambda to avoid visibility outside) providing -1, y or y, -1 as arguments:
// lambda example
auto markFields = [](int row, int column, condition, value)
{
// combined loops with y being row, i being column
// or separate ones from your solution, just as you prefer
}
for(/*...*/)
{
// ...
markFields(y, i, -1, y);
solve(y + 1);
markFields(y, i, y, -1);
}
(If you introduce a class at some point later, prefer a private helper function over the lambda; as being private, it is still invisible to outside, but complexity of solve function is reduced.)
You can avoid the problem of overwriting marks of previous iterations and at the same time get more efficiently if you change your board representation:
2*n - 12*n - 1[1] compass points
You now mark entire columns or diagonals at once by just setting a flag (which then does not even need to differ from recursion to recursion) in the appropriate array.
Indices into the columns array are trivial, just the value of our loop counter: columns[i].
Indices into the two diagonal arrays are a bit more complicated; fields on the same NW-SE diagnal have in common that the difference between row and column is the same, so you get them by y - i + n - 1 (you might skip the subtraction of 1 by enlarging the array by 1 and use index 0 as sentinel).
Fields on the same NE-SE diagnal have the same sum of row and column, so you identfy these by y + i.
Your loop then might look as follows (assuming boolean arrays/vectors/..., initialised to all true, meaning 'free' and diagnoals array enlarged for one sentinel):
for(int i = 0; i < n; ++i)
{
int nwse = y - i + n;
int nesw = y + i;
if(column[i] && nwseDiagonals[nwse] && neswDiagonals[nesw])
{
// can place a queen!
column[i] = false;
nwseDiagonals[nwse] = false;
neswDiagonals[nesw] = false;
solve(y + 1);
column[i] = true;
nwseDiagonals[nwse] = true;
neswDiagonals[nesw] = true;
}
}
I recommend packing this infrastructure into a class, you get better encapsulation that way then:
class Solver
{
public:
Solver(size_t n)
: n(n), c(0)
{
// vectors already constructed here
columns.reserve(n);
n *= 2;
nwseDiagonals.reserve(n);
neswDiagonals.reserve(n - 1);
};
void solve()
{
solve(0);
}
private:
size_t n;
size_t c;
// std::vector<bool> has a specialization packing multiple bits into
// a single byte – saves memory, costs runtime as bits need to be
// unpacked; choice left upon to you, but please the same for all...
std::vector<char /* or bool */> columns;
std::vector<char /* or bool */> nwseDiagonals;
std::vector<char /* or bool */> neswDiagonals;
void solve(size_t row)
{
// your implementation
}
};
void demo()
{
Solver s(8); // classic chess board...
s.solve();
}
If you prefer, you can make solve function static, too. It would then look like this:
static void solve(size_t n)
{
Solver s(n);
s.solve();
}
void demo()
{
Solver::solve(8); // classic chess board
}
Constructor should be moved to private section then.
In both variants, prefer not letting the Solver do any output, but the solve function return some appropriate result (number of solutions found, vector of all solutions, ...). IO in general should be done outside, that improves reusability of the class.