Skip to content

anonymous /N-Queens

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
N-Queens implementaion. Needs a new algo.
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.