Created
July 16, 2012 19:13
-
-
Save anonymous/3124451 to your computer and use it in GitHub Desktop.
N-Queens implementaion. Needs a new algo.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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