N-Queens implementaion. Needs a new algo.

N-Queens.cc

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

set<vector<int> > answers;
int answers_count = 0;


int min(int a, int b) {
	if(a < b)
		return a;

	return b;
}


bool is_legal(vector<vector<int> > board) {
	//Horizontals:
	bool flag = false;
	for(int i=0; i<board.size(); i++) {
		for(int j=0; j<board.size(); j++) {
			if(board[i][j] == 1) {
				if(flag)
					return false;
				flag = true;
			}
		}

		flag = false;
	}

	//Verticals:
	for(int i=0; i<board.size(); i++) {
		for(int j=0; j<board.size(); j++) {
			if(board[j][i] == 1) {
				if(flag)
					return false;
				flag = true;
			}
		}

		flag = false;
	}


	//Diagonals:
	//There are 2n-1 diagonals for a square of side n. Don't forget to check / and \ diagonals!
	for(int i=0; i<2*board.size()-1; i++) {
		int diagonal_length = min(i+1, 2*board.size()-1-i);

		int vertical_index, horizontal_index;
		if(i<=board.size()-1) {
			vertical_index = i;
			horizontal_index = 0;

			for(int j=0; j<diagonal_length; j++) {
				if(board[vertical_index][horizontal_index] == 1) {
					if(flag)
						return false;
					flag = true;
				}

				vertical_index--;
				horizontal_index++;
			}

			flag = false;
		}

		else {
			vertical_index = board.size()-1;
			horizontal_index = i-board.size()+1;

                        for(int j=0; j<diagonal_length; j++) {
                                if(board[vertical_index][horizontal_index] == 1) {
                                        if(flag)
                                                return false;
                                        flag = true;
                                }
                                vertical_index--;
                                horizontal_index++;
                        }

                        flag = false;
                }
	}


	//Other diagonal:
	for(int i=0; i<2*board.size()-1; i++) {
		int diagonal_length = min(i+1, 2*board.size()-1-i);

		bool flag = false;
		if(i<=board.size()-1) {
			int vertical_index = i;
			int horizontal_index = board.size()-1;

			for(int j=0; j<diagonal_length; j++) {
				if(board[vertical_index][horizontal_index] == 1) {
					if(flag)
						return false;
					flag = true;
				}

				vertical_index--;
				horizontal_index--;
			}
		}

		else {
			int vertical_index = board.size()-1;
			int horizontal_index = 2*(board.size()-1)-i;

			for(int j=0; j<diagonal_length; j++) {
				if(board[vertical_index][horizontal_index] == 1) {
					if(flag)
						return false;
					flag = true;
				}

				vertical_index--;
				horizontal_index--;
			}
		}
	}


	return true;
}


void dump_board(vector<vector<int> > board) {
	for(int i=0; i<board.size(); i++) {
		for(int j=0; j<board.size(); j++)
			cout << board[i][j] << " ";
		cout << endl;
	}

	cout << endl;
	return;
}


vector<vector<int> > update_board(int size, vector<int> positions) {
	vector<vector<int> > return_me(size, vector<int>(size, 0));

	for(int i=0; i<positions.size(); i++)
		return_me[i][positions[i]] = 1;

	return return_me;
}


void solution(vector<int> positions) {
	if(answers_count >= 3) {
		answers_count++;
		return;
	}


	vector<int> insert_me(positions.size(), 0);

	for(int i=0; i<positions.size(); i++) {
		insert_me[positions[i]] = i;
	}

	answers.insert(positions);
	answers_count++;
	return;
}


void get_answer(vector<vector<int> > board, int depth, vector<int> positions) {
	if(depth >= board.size())
		return;


	for(int k=0; k<board.size(); k++) {
		vector<int> temp_positions = positions;
		temp_positions.push_back(k);

		vector<vector<int> > temp_board = update_board(board.size(), temp_positions);
		if(!is_legal(temp_board))
			continue;

		if(depth == board.size()-1)
				solution(temp_positions);

		get_answer(temp_board, depth+1, temp_positions);
	}
}


int main() {
	ifstream fin("checker.in");
	ofstream fout("checker.out");

	int size;
	fin >> size;

	vector<vector<int> > board(size, vector<int>(size, 0));

	get_answer(board, 0, vector<int>());
	for(set<vector<int> >::iterator it=answers.begin(); it!=answers.end(); ++it) {
		for(int i=0; i<size-1; i++)
			fout << (*it)[i]+1 << " ";
		fout << (*it)[size-1]+1 << endl;
	}

	fout << answers_count << endl;


	return 0;
}