8황후 문제, 해결 사고방식과 코드

관련 질문1: [LeetCode] N-Queen N 황후
관련 질문 2:
팔황후 문제는 오래되고 유명한 문제로 역추적 알고리즘의 전형적인 예제이다.
여기 8황후 문제에 대한 해답을 드리겠습니다.사고방식은 해답 트리를 깊이 있게 훑어보고 8층에 도착했을 때 우리는 해답을 찾았다.8층에 도착하기 전에 해답나무의 노드가 8황후 문제의 요구를 위반한 것을 발견하면 거슬러 올라간다.
구체적인 코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<iterator>
using namespace std;

bool test_col(int c, vector<bool> col)
{// true if the c-th column is occupied.
        return col.at(c);
}

bool test_main(int r, int c, vector<bool> main_diag)
{// true if the main diag passing through (r,c) is occupied 
        return main_diag.at(r-c+7);
}

bool test_counter(int r, int c, vector<bool> counter_diag)
{// true if the counter diag passing through (r, c) is occupied
        return counter_diag.at(r+c);
}

void eight_queen(vector<int> pos, vector<bool> col, vector<bool> main_diag, vector<bool> counter_diag)
{
        if(pos.size()==8)
        {
                // copy can be used to print out the elements in an iterator range
                copy(pos.begin(), pos.end(), ostream_iterator<int>(cout, "|") );
                cout<<"
";
                return;
        }
        else
        {
                for(int i=0; i<8; i++)
                {
                        if(!(test_col(i, col) || test_main(pos.size(), i, main_diag) || test_counter(pos.size(), i, counter_diag) ))
                        {
                                col.at(i) = true;
                                main_diag.at(pos.size()-i+7) = true;
                                counter_diag.at(pos.size()+i) = true;
                                pos.push_back(i);
                                eight_queen(pos, col, main_diag, counter_diag);
                                pos.pop_back();
                                col.at(i) = 0;
                                main_diag.at(pos.size()-i+7) = 0;
                                counter_diag.at(pos.size()+i) = 0;
                        }
                }
        }
        return;
}

int main()
{
        vector<bool> col(8, 0); // false: no queen is occupying this column. true: a queen is now occupying this column.
        vector<bool> main_diag(15, 0); // false: no queen is occupying this main diag. true: a queen is now occupying this main diag.
        vector<bool> counter_diag(15, 0); // false: no queen is occupying this counter diag. true: a queen is now occupying this counter diag.
        vector<int> pos;
        eight_queen(pos, col, main_diag, counter_diag);
}