I am studying the 8 queen problem and I have think the following algorithm to solve this problem (but it seems not correct)
My algorithm work in this way on an 8X8 chessboard:
I have try this solution on paper but, often I can place only 7 queen and not queen...
So I am thinking that this solution is able to place a number of queens that can not eat each other but it don't ensure that, if I am using an nXn board, I can always place 8 queens...
Is it true?
Tnx
Andrea
@miorel is exactly correct about backtracking. Just for fun I tried to solve this brute force in C/C++ using a simple recursive algorithm, with a one simple optimization:
We know that for any given problem size N, each queen will be in a separate column. So we don't even try other columns. So the idea is this:
When checking if placing is compatible, we only need to check a) whether there is a queen in the same row and b) whether there are any diagonal queens.
#include <stdlib.h>
#include <stdio.h>
int solveQueens(int queenIndex, int sz, int * positions) {
for (int i=0; i<sz; i++) {
int valid = 1;
for (int j=0; j<queenIndex; j++) {
int diff = queenIndex-j;
if (
(positions[j]==i)
|| (positions[j]+diff == i)
|| (positions[j]-diff == i)
) {
valid = 0;
break;
}
}
if (valid) {
positions[queenIndex]=i;
if (queenIndex < sz-1) {
// Recursive call
int res = solveQueens(queenIndex+1, sz, positions);
if (res)
return 1;
} else {
return 1;
}
}
}
return 0;
}
void printQueens(int sz, int * positions) {
for (int i=0; i<sz; i++) {
printf("%c%d ", (char)(i+(int)'A'), positions[i]+1);
}
}
void queens(int sz) {
int * positions = (int *)malloc(sizeof(int)*sz);
if (solveQueens(0, sz, positions)) {
printQueens(sz, positions);
} else {
printf("No solutions found\n");
}
free(positions);
}
int main() {
queens(24);
return 0;
}
I am sure this is not the optimal algorithm, but it works under 1 sec on board sizes of 24.