#include <iostream>

#include <vector>

#include <string>

using namespace std;

class Solution {

public:

	int N;

	vector<int> pos;

	int result;

	bool visited[10];

	bool attack(const int &row, const int &col) {

		for(int i = 0; i < pos.size(); i ++) {

			if(abs(pos[i]-col) == abs(i-row))

				return true;

		}

		return false;

	}

	void dfs(const int &depth) {

		if( depth == N) {

			result += 1;

		}

		for(int i = 0; i < N; i ++) {

			if(visited[i] == 0 ) {

				if( pos.size() > 0 && attack(depth, i))

					continue;

				visited[i] = 1;

				pos.push_back(i);

				dfs(depth+1);

				pos.pop_back();

				visited[i] = 0;

			}

		}

	}

    int totalNQueens(int n) {

		pos.clear();

		result=0;

		memset(visited, 0, sizeof(visited));

        N = n;

		dfs(0);

		return result;

    }

};

int main() {

	Solution solution;

	int res = solution.totalNQueens(9);

	cout << res << endl;

	return 0;

}

#include <iostream>

#include <vector>

#include <string>

using namespace std;

class Solution {

public:

	int N;

	vector<int> pos;

	vector<vector<string> > result;

	bool visited[10];

	bool attack(const int &row, const int &col) {

		for(int i = 0; i < pos.size(); i ++) {

			if(abs(pos[i]-col) == abs(i-row))

				return true;

		}

		return false;

	}

	void dfs(const int &depth) {

		if( depth == N) {

			vector<string> temp;

			string str;

			for(int i = 0; i < N; i ++) {

				str.clear();

				for(int j = 0; j < N; j ++) {

					if(pos[i] == j)

						str.push_back('Q');

					else

						str.push_back('.');

				}

				temp.push_back(str);

			}

			result.push_back(temp);

		}

		for(int i = 0; i < N; i ++) {

			if(visited[i] == 0 ) {

				if( pos.size() > 0 && attack(depth, i))

					continue;

				visited[i] = 1;

				pos.push_back(i);

				dfs(depth+1);

				pos.pop_back();

				visited[i] = 0;

			}

		}

	}

    vector<vector<string> > solveNQueens(int n) {

		pos.clear();

		result.clear();

		memset(visited, 0, sizeof(visited));

        N = n;

		dfs(0);

		return result;

    }

};