# Eight-Queens Puzzle

*A C++ code sample from me that uses the back-tracking to solve the eight queens problem.*

```
class Solution {
private:
int col_pos_at_row[8]{}; // put a {} to init。
int answer_count = 0;
public:
void place_queen(int row) { // call entrance from place_queen(row=0)
// when you reached
if (row == 8) {
// row 0~7 has done, which is 8 queens
cout << "Solution " << ++answer_count << endl;
print_queens();
return;
}
for (int col = 0; col < 8; ++col) {
if (is_valid(row, col)) {
/*
* back tracking happens here.
* test if at (row, col) is valid, if not, we don't set the value.
* basically means we put a value at (row, col) and if not valid,
* take it back. Because of the 1D-col-array,
* it is a little different from the 2D grid value.
* The magic is because of col_pos_at_row[row] is a single value,
* so when you hit row == 8 and it goes back to the next try,
* which is the next col value in the same row, you see it is not
* disturbed by our last col value.
*/
col_pos_at_row[row] = col;
place_queen(row + 1);
}
}
}
bool is_valid(int row, int col) {
int left_diag_up = col -1, right_diag_up = col +1;
// buttom up so the row is -1
for (int r = row-1; r >= 0 ; --r) {
if (col_pos_at_row[r] == col)
return false;
if (left_diag_up >=0 && col_pos_at_row[r] == left_diag_up)
return false;
if (right_diag_up < 8 && col_pos_at_row[r] == right_diag_up)
return false;
--left_diag_up, ++right_diag_up;
}
return true;
}
void print_queens() {
for (int row = 0; row < 8; ++row) {
cout << "R-" << row << ": ";
for (int col = 0; col < 8; ++col) {
if (col_pos_at_row[row] == col)
cout << "Q ";
else
cout << "* ";
}
cout << endl;
}
cout << "--------------" << endl;
}
};
int main() {
auto sol = Solution();
sol.place_queen(0);
}
```