Some doubts about 8 queen problems algorithm [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

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:

1. At the beginning put a queen in a random location of the board
2. Mark as unserviceable al the locations that are on the horizontal line, on the vertical line and on the two diagonal lines of the current queen.
3. Place another queen in any location still free on the board
4. Iterate this process (from point 2) untill there are usable location on the board

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

Answer 1

@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:

• Each queen will have its own column, so queen 1 goes in column 1, queen 2 in column 2, etc.
• So the goal really is to pick a row for each queen. Starting with the first queen, let try each row in turn. We do this by placing a queen in a possible row, then making a recursive call to place the second, third, and fourth queen.

• 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.

Answer 2

Add backtracking to your algorithm. If placing the 7th queen results in a position where there's no room for an 8th one, then it was a bad spot for the 7th queen. So remove it and pick a different spot for it. If you run out of places for the 7th queen that means the 6th queen was in a bad spot, etc.