Following code is solving n queen problem with c++ using backtracking. I saw other people solution they are very short like 20 to 30 lines. Is there way improve following code?

#include <iostream>
#include <vector>

bool put_in(std::vector<std::vector<int>> &Board, std::vector<std::vector<int>> &Stack, int row, int col, int n);
void insert_into_stack(std::vector<std::vector<int>> &Stack, int row, int col);
bool check_horizontal(std::vector<std::vector<int>> &Stack, int row);
bool check_vertical(std::vector<std::vector<int>> &Stack, int col);
bool check_diagonal_left_to_right(std::vector<std::vector<int>> &Stack, int row, int col, int n);
bool check_diagonal_right_to_left(std::vector<std::vector<int>> &Stack, int row, int col, int n);
void print_board(std::vector<std::vector<int>> &Board);
void print_stack(std::vector<std::vector<int>> &Stack);
void reset_board(std::vector<std::vector<int>> &Board, std::vector<std::vector<int>> &Stack);
void reset_stack(std::vector<std::vector<int>> &Stack, int &row, int &col, int n);

main() 
 // Board size
 int n = 10;
 int number_of_solution = 1;

 // Stack
 std::vector<std::vector<int>> Stack;
 Stack.reserve(n);
 for (auto &it : Stack)
 it.resize(2);

 // Board
 std::vector<std::vector<int>> Board(n);
 for (auto &it : Board)
 it.resize(n);

 for (int row = 0; row < n; row++) 
 for (int col = 0; col < n + 1; col++) 
 if (col == n) 
 // ! IMPORTANT
 // * Ends when row is 0 and col is n!
 if (row == 0 && col == n) 
 return 0;
 
 // * End condition
 // ! IMPORTANT

 Board[Stack[Stack.size() - 1][0]][Stack[Stack.size() - 1][1]] = 0;
 row = Stack[Stack.size() - 1][0];
 col = Stack[Stack.size() - 1][1];
 Stack.pop_back();

 continue;
 
 if (check_horizontal(Stack, row)) 
 continue;
 

 if (check_vertical(Stack, col)) 
 continue;
 

 if (check_diagonal_left_to_right(Stack, row, col, n)) 
 continue;
 

 if (check_diagonal_right_to_left(Stack, row, col, n)) 
 continue;
 

 if (put_in(Board, Stack, row, col, n)) 
 if (Stack.size() == n) 
 std::cout << std::endl;
 std::cout << number_of_solution++ << std::endl;
 print_board(Board);
 reset_board(Board, Stack);
 reset_stack(Stack, row, col, n);
 continue;
 
 break;
 
 
 
 print_board(Board);

 return 0;


bool put_in(std::vector<std::vector<int>> &Board, std::vector<std::vector<int>> &Stack, int row, int col, int n) 
 if (Board[row][col] == 0) 
 Board[row][col] = 1;
 insert_into_stack(Stack, row, col);
 return true;
 else
 return false;


void insert_into_stack(std::vector<std::vector<int>> &Stack, int row, int col) 
 std::vector<int> position;
 position.reserve(2);
 position.push_back(row);
 position.push_back(col);
 Stack.push_back(position);


bool check_horizontal(std::vector<std::vector<int>> &Stack, int row) 
 for (auto &s : Stack) 
 if (s[0] == row)
 return true;
 
 return false;


bool check_vertical(std::vector<std::vector<int>> &Stack, int col) 
 for (auto &s : Stack) 
 if (s[1] == col)
 return true;
 
 return false;


bool check_diagonal_left_to_right(std::vector<std::vector<int>> &Stack, int row, int col, int n) 
 int c_row = row, c_col = col;
 while (c_row >= 0 && c_col >= 0) 
 for (auto &s : Stack) 
 if (s[0] == c_row && s[1] == c_col)
 return true;
 
 c_row--;
 c_col--;
 

 c_row = row;
 c_col = col;
 while (c_row <= n && c_col <= n) 
 for (auto &s : Stack) 
 if (s[0] == c_row && s[1] == c_col)
 return true;
 
 c_row++;
 c_col++;
 
 return false;


bool check_diagonal_right_to_left(std::vector<std::vector<int>> &Stack, int row, int col, int n) 
 int c_row = row, c_col = col;
 while (c_row <= n && c_col >= 0) 
 for (auto &s : Stack) 
 if (s[0] == c_row && s[1] == c_col)
 return true;
 
 c_row++;
 c_col--;
 

 c_row = row;
 c_col = col;
 while (c_row >= 0 && c_col <= n) 
 for (auto &s : Stack) 
 if (s[0] == c_row && s[1] == c_col)
 return true;
 
 c_row--;
 c_col++;
 
 return false;


void print_board(std::vector<std::vector<int>> &Board) 
 // Print Board
 for (auto &it : Board) 
 for (auto &val : it) 
 std::cout << val;
 
 std::cout << std::endl;
 

void print_stack(std::vector<std::vector<int>> &Stack) 
 for (auto &it : Stack) 
 for (auto &val : it) 
 std::cout << val;
 
 std::cout << std::endl;
 


void reset_stack(std::vector<std::vector<int>> &Stack, int &row, int &col, int n) 
 col = Stack[Stack.size() - 1][1];
 Stack.pop_back();


void reset_board(std::vector<std::vector<int>> &Board, std::vector<std::vector<int>> &Stack) 
 Board[Stack[Stack.size() - 1][0]][Stack[Stack.size() - 1][1]] = 0;

Welcome to Code Review. This post is a mixture between review, remarks, tutorial and general guidelines. Overall, your code has two complexity issues: space complexity due to types (see "Tip: Use implicit data") and algorithmic complexity due to algorithms (see "Diagonals"). Several of your references should be const (see "Tip: Use const Type& if you don't want to change the argument"), and some of your names could be chosen better.

Every section of this post should be readable on its own, however, some code uses declarations and types written in earlier examples, so keep that in mind.

Stacks

When we use a backtracking algorithm, a stack is usually used throughout its execution. In programming languages that provide function calls, there is always an implicit stack present: the function call stack. We have a caller and a callee. The caller calls the callee, and at some point, the callee either returns and hands control back to the caller, or the callee terminates the program.

Why is this important? Because it provides a tool for backtracking problems with limited depth: instead of an explicit stack, we can use the implicit one. So if you were to solve the N-queens problem for a limited $N$, the use of the implicit stack would be a lot simpler. But more on that later.

Types

The code at hand is a mouthful. That's mostly due to the std::vector<std::vector<int>>. There are two issues we can find there:

1. the Board is either 0 or 1, so a smaller type is more suitable


2. the Stack's elements always contain exactly two elements, so a std::pair<int,int> is more appropriate.

Regardless, a simple typedef or using can make the code much easier to read:

using board_type = std::vector<std::vector<int>>;
using stack_type = std::vector<std::vector<int>>;

bool put_in(board_type &Board, stack_type &Stack, int row, int col, int n);
void insert_into_stack(stack_type &Stack, int row, int col);
bool check_horizontal(const stack_type &Stack, int row);
bool check_vertical(const stack_type &Stack, int col);
bool check_diagonal_left_to_right(const stack_type &Stack, int row, int col, int n);
bool check_diagonal_right_to_left(const stack_type &Stack, int row, int col, int n);
void print_board(const board_type &Board);
void print_stack(const stack_type &Stack);
void reset_board(board_type &Board, stack_type &Stack);
void reset_stack(stack_type &Stack, int &row, int &col, int n);

Although both type synonyms have the same meaning, their different name already tells us that we want to use a stack or a board at certain positions. Still, std::vector<std::pair<int,int>> would be more fitting for the stack.

Tip: Use initializer lists when possible

That's obvious if we have a look at the only place where Stack gets new elements:

void insert_into_stack(std::vector<std::vector<int>> &Stack, int row, int col) 
 std::vector<int> position;
 position.reserve(2);
 position.push_back(row);
 position.push_back(col);
 Stack.push_back(position);

If we want to create a vector with two elements, a std::initializer_list is the right tool:

void insert_into_stack(stack_type &Stack, int row, int col) 
 const std::vector<int> position = row, col;
 Stack.push_back(position);

At that point we can just skip the temporary position and use Stack.emplace_back with the list, but the compiler should generate the same code either way:

void insert_into_stack(stack_type &Stack, int row, int col) 
 Stack.emplace_back(row, col);

Remark: Remove unused parameters

Several functions have an int n parameter you never use. You should remove that. Also, enable compiler warnings. GCC and Clang use -Wall.

Remark: Always use return types on functions

Your main doesn't have a return type. Add int.

The implicit Board

However, even with that in mind (and std::pair), we still carry around a lot of information with us all the time. The Board gets updated in every iteration, whenever we put a new queen on the board. We need that Board for print_board, right?

Actually, no. We can recreate a Board from a Stack whenever we want to:

void fill_board_from_stack(board_type &Board, const stack_type& Stack) 
 // simple exercise

That will take at most $mathcal O(n^2)$. Since print_board will also take $mathcal O(n^2)$, we're not going to increase the asymptotic complexity of our program.

Tip: Use const Type& if you don't want to change the argument

As you can see, I've used const stack_type& above, as I want to make sure that my code doesn't accidentally change the Stack. Similarly, the print_* functions should also take a const reference:

void print_board(const board_type &Board);
void print_stack(const stack_type &Stack);

That way the function's type already tells us that this function won't change its argument, and we will get a compiler error if we erroneously try to.

The same holds for all the check_ functions, see declarations above.

Names

Throughout the range-based for loops, it and s get used. What's it? For example, what is it in the following loop?

for (auto &it : Board) 
 for (auto &val : it) 
 std::cout << val;
 
 std::cout << std::endl;

Well, it's the Board's row. So we should call it row, not it. it is fine if we use iterators, but with range-based for loops, we already have a value or a reference at hand, not a raw iterator. The name it is therefore misleading.

For s, we can use placement, position, pos or even queen. The Stack can actually get renamed to Placements or even Queens, as it contains the queens' positions. The form can yield a name, but the name should foremost fit the contents.

By the way, the check_ functions are ambiguous. If a check returns true, does that mean that the queen is safe? Or does true mean that the queen is threatened? A name like can_place_, is_safe_ or threatens_ is unambiguous.

Algorithms and data

Even with those small tips, the code will be larger than the other variants you've encountered. That's due to a small, but significant optimization that's usually applied to the board: we don't store the row. Indeed, one dimension is never stored, at all. It's already implicit in the Stack, if we reorder it.

Tip: Use implicit data

Let's take a step back from our code for a moment and just think about what Stack contains at the end of our algorithm. It will look like this:

0100
0001
1000
0010

Stack = 0, 1,
 1, 3,
 2, 0,
 3, 2;

As you can see, throughout the Stack we have the following property:

for(int i = 0; i < Stack.size(); ++i) 
 assert(i == Stack[i][0]);

But if that holds, we can just get rid of the row and use using stack_type = std::vector<int>.

Diagonals

That simplifies the code tremendously: check_horizontal can get removed completely, and check_diagonal_left_to_right and check_diagonal_right_to_left can get replaced by a single function:

bool threatens_diagonally(const stack_type &Stack, int col)
 for(int i = 0; i < Stack.size(); ++i) 
 if(Stack[i] + (Stack.size() - i) == col 
 return false;

This optimization was also possible in your original code, though, and is easier to explain there:

bool check_diagonal_left_to_right(const stack_type & Stack, int row, int col, int n)
 for (auto &s : Stack) 
 if (s[0] - row == s[1] - col)
 return true;
 
 
 return false;

If we have x = s[0] - row and y = s[1] - col, we can interpret x as the rows we need to traverse to get from s to the new queen, and y as the respective columns. If both are the same, both queens are on the same diagonal. Similarly for the other function:

bool check_diagonal_right_to_left(const stack_type & Stack, int row, int col, int n)
 for (auto &s : Stack) 
 if (s[0] - row == -(s[1] - col))
 return true;
 
 
 return false;

If we have x = s[0] - row and y = -(s[1] - col), we can interpret x as the rows we need to traverse to get from s to the new queen, and y as the respective columns in the other direction. If both are the same, both queens are on the same diagonal (this time the right-to-left diagonals).

If we put both conditions in a single function, we end up with:

bool threatens_diagonally(const stack_type & Stack, int row, int col)
 for (auto &s : Stack) s[0] - row == -(s[1] - col))
 return true;
 
 
 return false;

To get back to the variant with the implicit row, just remember that Stack[i] is the queen at i, Stack[i], and col will be the Stack.size(), col queen (the row is now implicit!).

The implicit stack

We now come back to the first remark on stacks. If we employ all the tips above, we will end up with something like:

int main() 
 // Board size
 int n = 10;
 int number_of_solution = 1;

 // Stack
 stack_type Stack;
 Stack.reserve(n);

 // Board
 board_type Board(n);
 for (auto &it : Board)
 it.resize(n);

 for (int col = 0; col < n + 1; col++) threatens_diagonally(Stack, col)) 
 continue;
 

 if (put_in(Board, Stack, col)) 
 if (Stack.size() == n) 
 std::cout << std::endl;
 std::cout << number_of_solution++ << std::endl;
 print_board(Board);
 reset_board(Board, Stack);
 reset_stack(Stack, col);
 continue;
 
 break;
 
 
 print_board(Board);

 return 0;

Remember, the row is implicit, so we don't have to carry it with us. Before I present an alternative, let's go back to the backtracking algorithm. For the sake of simplicity, let's use pseudo-code:

# That's actually almost the whole valid python solution.
def solve(n, queens):
 if len(queens) == n:
 print(queens)
 for i in range(n):
 if safe(queens, i):
 solve(n, queens + [i])

So let's try to write that in C++:

bool threatened(const stack_type& queens, int col)
 // exercise


void solve(int N, stack_type & queens) 
 if(queens.size() == N) 
 print_stack(queens);
 
 for(int i = 0; i < N; ++i) 
 if(not threatened(queens, i)) 
 queens.push_back(i);
 solve(N, queens);
 queens.pop_back();
 
 

It's a little bit longer, but that's the complete C++ code necessary to solve the problem, we just need to call solve on an empty initial stack. Every recursive function can get rewritten into a non-recursive one if we use an explicit stack, however, we will end up with a function that's similar to your original one, so that's left as an exercise.