Royal battles' commanding queens
How I solved the N-Queens problem
The N-queens problem involves placing N chess queens on an NxN chessboard so that no two queens threaten each other. In other words, no two queens are allowed to be in the same row, column, or diagonal. It is an example of a combinatorial optimization problem, and has applications in fields such as artificial intelligence, computer vision, and operations research.
There are multiple possible solutions to any given NxN board. However, my method of using backtracking and recursive functions that would systematically checked all possible configurations of queen pacements and would print out the one that is the first possible solution.
Upon Checking the internet for supplementing my algorithm and other possible codes, I found that my solution was still inefficient in space complexity, however, I was proud that I was able to solve the N-Queens problem by myself with minimal help from online resources.
#include <iostream>
using namespace std;
#define size 8
int columnCheck[30] = { 0 };
int diagonalCheck[30] = { 0 };
int rowCheck[30] = { 0 };
bool squarChecker(char chessBoard[size][size], int numberOfQueens){
if (numberOfQueens >= size){
return true;
}
int a = 0;
while(a < size){
if((columnCheck[a - numberOfQueens + size - 1] != 1 &&
diagonalCheck[a + numberOfQueens] != 1) && rowCheck[a] != 1){
chessBoard[a][numberOfQueens] = 'Q';//assigns to
columnCheck[a - numberOfQueens + size - 1] = diagonalCheck[a + numberOfQueens] =
rowCheck[a] = 1;
if(squarChecker(chessBoard, numberOfQueens + 1)){
return true;
}
chessBoard[a][numberOfQueens] = '=';
columnCheck[a - numberOfQueens + size - 1] = diagonalCheck[a + numberOfQueens] =
rowCheck[a] = '=';
}
a++;
}
return false;
}
bool queenPositionAssignment(){
char board[size][size];
for (int i = 0; i < size; i++){
for (int j = 0; j < size; j++){
board[i][j] = '=';
}
}
if (squarChecker(board, 0) == false){
cout<<"Solution does not exist";
return false;
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
cout << " " << board[i][j] << " ";
}
cout << endl;
}
return true;
}
int main(){
cout << "Here is how an " << size << " by " << size <<
" board would look like: " << endl;
queenPositionAssignment();
cout << "\n'Q' is where the queens shall be positioned, while the" <<
" equal(=) character represent empty squares\n\n";
return 0;
}