

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


/**
Return true if queen placement q[n] does not conflict with
other queens q[0] through q[n-1]
*/
isConsistent(List q, int n) {
  for (int i=0; i<n; i++) {
    if (q[i] == q[n]) {
      return false; // Same column
    }
 
    if ((q[i] - q[n]) == (n - i)) {
      return false; // Same major diagonal
    }
 
    if ((q[n] - q[i]) == (n - i)) {
      return false; // Same minor diagonal
    }
  }
 
  return true;
}
 
/**
Print out N-by-N placement of queens from permutation q in ASCII. 
*/
printQueens(List q) {
  int N = q.length;
  for (int i=0; i<N; i++) {
    StringBuffer sb = new StringBuffer();
    for (int j=0; j<N; j++) {
      if (q[i] == j) {
        sb.write("Q ");
      } else {
        sb.write("* ");
      }
    }
    print(sb.toString());
  }
  print("");
}
 
/**
Try all permutations using backtracking
*/
enumerate(int N) {
  var a = new List(N);
  _enumerate(a, 0);
}
 
_enumerate(List q, int n) {
  if (n == q.length) {
    printQueens(q);
  } else {
    for (int i = 0; i < q.length; i++) {
      q[n] = i;
      if (isConsistent(q, n)){
        _enumerate(q, n+1);
      }
    } 
  }
}
 
void main() {
  enumerate(4);
}