<p>The <strong>n-queens</strong> puzzle is the problem of placing <code>n</code> queens on an <code>n x n</code> chessboard such that no two queens attack each other.</p>

<p>Given an integer <code>n</code>, return <em>the number of distinct solutions to the&nbsp;<strong>n-queens puzzle</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/queens.jpg" style="width: 600px; height: 268px;" />
<pre>
<strong>Input:</strong> n = 4
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are two distinct solutions to the 4-queens puzzle as shown.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 9</code></li>
</ul>

class Solution {
public:
    int number_of_solutions = 0;

    int totalNQueens(int n) {
      std::set<std::pair<int, int>> available_positions;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            available_positions.insert(std::make_pair(i, j));
        }
      }

      totalNQueen(available_positions, 0, n);
      return number_of_solutions;
    }

    void totalNQueen(std::set<std::pair<int, int>>& available_positions, int row_index, int n) {
      if (row_index >= n) {
        //std::cout << "available position size: " << available_positions.size() << std::endl;
        ++number_of_solutions;
        return;
      }

      if (available_positions.empty()) {
        return;
      }

      for (int i = 0; i < n; ++i) {
        auto coord = std::make_pair(row_index, i);
        if (available_positions.contains(coord)) {
          std::set<std::pair<int, int>> newly_unavailable_positions;
          
          // horizontal 
          for (int j = 0; j < n; ++j) {
            if (available_positions.contains(std::make_pair(coord.first, j))) {
              newly_unavailable_positions.insert(std::make_pair(coord.first, j));
            }
          }

          // vertical
          for (int j = 0; j < n; ++j) {
            if (available_positions.contains(std::make_pair(j, coord.second))) {
              newly_unavailable_positions.insert(std::make_pair(j, coord.second));
            }
          }

          // diagonal
          for (int j = -n; j < n; ++j) {
            auto new_coord = std::make_pair(coord.first + j, coord.second + j);
            if (new_coord.first >= 0 && new_coord.first < n &&
                new_coord.second >= 0 && new_coord.second < n &&
                available_positions.contains(new_coord)) {
              newly_unavailable_positions.insert(new_coord);
            }
          }

          // diagonal
          for (int j = -n; j < n; ++j) {
            auto new_coord = std::make_pair(coord.first + j, coord.second - j);
            if (new_coord.first >= 0 && new_coord.first < n &&
                new_coord.second >= 0 && new_coord.second < n &&
                available_positions.contains(new_coord)) {
              newly_unavailable_positions.insert(new_coord);
            }
          }

          //std::cout << "picked queen position: " << coord.first << "," << coord.second << std::endl;
          for (auto coord_to_erase : newly_unavailable_positions) {
          //std::cout << "unavailable  position: " << coord_to_erase.first << "," << coord_to_erase.second << std::endl;
            available_positions.erase(coord_to_erase);
          }
          totalNQueen(available_positions, row_index + 1, n);
          available_positions.insert(newly_unavailable_positions.begin(), newly_unavailable_positions.end());
        }
      }
    }
};
18172