Created
December 7, 2014 00:38
-
-
Save LordZamy/7fcebcd3188047a4b523 to your computer and use it in GitHub Desktop.
N-Queens in C++ using depth first search
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> | |
using namespace std; | |
int N = 8; | |
int board[8][8]; | |
int numQueens = 0; | |
int sols = 0; | |
void searchCol(int col) { | |
// base case | |
if(numQueens >= N) { | |
// print solution and exit | |
for(int i = 0; i < N; i++) { | |
for(int j = 0; j < N; j++) { | |
cout << board[i][j] << "\t"; | |
} | |
cout << "\n"; | |
} | |
cout << "\n"; | |
sols++; | |
return; | |
} | |
// for each row | |
for(int i = 0; i < N; i++) { | |
// if cell is not attacked | |
if(board[i][col] > -1) { | |
// set queen and mark all cells in cross and diagonal | |
board[i][col] = 1; | |
for(int j = 0; j < N; j++) { | |
if(j != col) board[i][j]--; | |
if(j != i) board[j][col]--; | |
} | |
for(int j = 1; j < N; j++) { | |
if(i - j >= 0 && col - j >= 0) board[i - j][col - j]--; | |
if(i + j < N && col + j < N) board[i + j][col + j]--; | |
if(i - j >= 0 && col + j < N) board[i - j][col + j]--; | |
if(i + j < N && col - j >= 0) board[i + j][col - j]--; | |
} | |
numQueens++; | |
searchCol(col + 1); | |
// remove queens and markers | |
board[i][col] = 0; | |
for(int j = 0; j < N; j++) { | |
if(j != col) board[i][j]++; | |
if(j != i) board[j][col]++; | |
} | |
for(int j = 1; j < N; j++) { | |
if(i - j >= 0 && col - j >= 0) board[i - j][col - j]++; | |
if(i + j < N && col + j < N) board[i + j][col + j]++; | |
if(i - j >= 0 && col + j < N) board[i - j][col + j]++; | |
if(i + j < N && col - j >= 0) board[i + j][col - j]++; | |
} | |
numQueens--; | |
} | |
} | |
} | |
int main() { | |
searchCol(0); | |
cout << sols << "\n"; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment