N Queen Problem C++

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
4
down vote

favorite












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;










share|improve this question









New contributor




Sam Dan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.























    up vote
    4
    down vote

    favorite












    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;










    share|improve this question









    New contributor




    Sam Dan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.





















      up vote
      4
      down vote

      favorite









      up vote
      4
      down vote

      favorite











      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;










      share|improve this question









      New contributor




      Sam Dan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      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;







      c++ backtracking n-queens






      share|improve this question









      New contributor




      Sam Dan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|improve this question









      New contributor




      Sam Dan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|improve this question




      share|improve this question








      edited 45 mins ago









      Zeta

      14.5k23267




      14.5k23267






      New contributor




      Sam Dan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 6 hours ago









      Sam Dan

      211




      211




      New contributor




      Sam Dan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Sam Dan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Sam Dan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          3
          down vote













          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)
          Stack[i] - (Stack.size() - i) == col
          )
          return true;


          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)
          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++)
          if (col == n)
          // ! IMPORTANT
          // * Ends when row is 0 and col is n!
          if (Stack.empty())
          return 0;

          // * End condition
          // ! IMPORTANT

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

          continue;

          if (threatens_vertically(Stack, col)
          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.






          share|improve this answer






















            Your Answer




            StackExchange.ifUsing("editor", function ()
            return StackExchange.using("mathjaxEditing", function ()
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
            );
            );
            , "mathjax-editing");

            StackExchange.ifUsing("editor", function ()
            StackExchange.using("externalEditor", function ()
            StackExchange.using("snippets", function ()
            StackExchange.snippets.init();
            );
            );
            , "code-snippets");

            StackExchange.ready(function()
            var channelOptions =
            tags: "".split(" "),
            id: "196"
            ;
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function()
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled)
            StackExchange.using("snippets", function()
            createEditor();
            );

            else
            createEditor();

            );

            function createEditor()
            StackExchange.prepareEditor(
            heartbeatType: 'answer',
            convertImagesToLinks: false,
            noModals: false,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            );



            );






            Sam Dan is a new contributor. Be nice, and check out our Code of Conduct.









             

            draft saved


            draft discarded


















            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f206325%2fn-queen-problem-c%23new-answer', 'question_page');

            );

            Post as a guest






























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            3
            down vote













            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)
            Stack[i] - (Stack.size() - i) == col
            )
            return true;


            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)
            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++)
            if (col == n)
            // ! IMPORTANT
            // * Ends when row is 0 and col is n!
            if (Stack.empty())
            return 0;

            // * End condition
            // ! IMPORTANT

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

            continue;

            if (threatens_vertically(Stack, col)
            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.






            share|improve this answer


























              up vote
              3
              down vote













              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)
              Stack[i] - (Stack.size() - i) == col
              )
              return true;


              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)
              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++)
              if (col == n)
              // ! IMPORTANT
              // * Ends when row is 0 and col is n!
              if (Stack.empty())
              return 0;

              // * End condition
              // ! IMPORTANT

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

              continue;

              if (threatens_vertically(Stack, col)
              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.






              share|improve this answer
























                up vote
                3
                down vote










                up vote
                3
                down vote









                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)
                Stack[i] - (Stack.size() - i) == col
                )
                return true;


                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)
                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++)
                if (col == n)
                // ! IMPORTANT
                // * Ends when row is 0 and col is n!
                if (Stack.empty())
                return 0;

                // * End condition
                // ! IMPORTANT

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

                continue;

                if (threatens_vertically(Stack, col)
                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.






                share|improve this answer














                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)
                Stack[i] - (Stack.size() - i) == col
                )
                return true;


                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)
                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++)
                if (col == n)
                // ! IMPORTANT
                // * Ends when row is 0 and col is n!
                if (Stack.empty())
                return 0;

                // * End condition
                // ! IMPORTANT

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

                continue;

                if (threatens_vertically(Stack, col)
                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.







                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited 36 mins ago

























                answered 57 mins ago









                Zeta

                14.5k23267




                14.5k23267




















                    Sam Dan is a new contributor. Be nice, and check out our Code of Conduct.









                     

                    draft saved


                    draft discarded


















                    Sam Dan is a new contributor. Be nice, and check out our Code of Conduct.












                    Sam Dan is a new contributor. Be nice, and check out our Code of Conduct.











                    Sam Dan is a new contributor. Be nice, and check out our Code of Conduct.













                     


                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f206325%2fn-queen-problem-c%23new-answer', 'question_page');

                    );

                    Post as a guest













































































                    Comments

                    Popular posts from this blog

                    Long meetings (6-7 hours a day): Being “babysat” by supervisor

                    Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

                    Confectionery