8-Queens algorithm example?

Question

Anybody knows good/concise algorithm examples for 8-queens? I did a Web search and did not find any good example.

Answer 1

Here's a simple Java implementation of the naive recursive algorithm; it should be instructive.

public class NQueens {
    final static int N = 4;
    static int[] position = new int[N];

    public static void main(String[] args) {
        solve(0);
    }

    static boolean isSafe(int k, int p) {
//      for (int i = 1; i <= k; i++) {
//          int other = position[k - i];
//          if (other == p || other == p - i || other == p + i) {
//              return false;
//          }
//      }
        return true;
    }
    static void solve(int k) {
        if (k == N) {
            System.out.println(java.util.Arrays.toString(position));
        } else {
            for (char p = 0; p < N; p++) {
                if (isSafe(k, p)) {
                    position[k] = p;
                    solve(k+1);
                }
            }
        }
    }
}

Note that isSafe contains commented lines right now; it's done on purpose. With these lines commented, the program becomes a recursive N-tuple generator, where each value is between 0 (inclusive) and N (exclusive). That is, the program as is generates the following output:

[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 2]
[0, 0, 0, 3]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 0, 1, 2]
[0, 0, 1, 3]
:
:
[3, 3, 3, 0]
[3, 3, 3, 1]
[3, 3, 3, 2]
[3, 3, 3, 3]

This N-tuple generation is a concrete sub-problem of the NQueens problem. There are many questions already on stackoverflow on how to write an N-nested loops, when you don't know what N is. I feel that it's instructional to make a temporary stop at this problem and first understand its solution, with isSafe commented out to simply return true;, to first get a feel of what the recursion does.

Once you're comfortable that this recursive tuple generator works, simply uncomment those lines, and you will get a simple, naive, but working, NQueens solver. With N=5 and isSafe lines uncommented, the program now generates the following output:

[0, 2, 4, 1, 3]
[0, 3, 1, 4, 2]
[1, 3, 0, 2, 4]
[1, 4, 2, 0, 3]
[2, 0, 3, 1, 4]
[2, 4, 1, 3, 0]
[3, 0, 2, 4, 1]
[3, 1, 4, 2, 0]
[4, 1, 3, 0, 2]
[4, 2, 0, 3, 1]

Each line is a solution to the 5-queens problem. The i-th element of the array denotes the row position of the i-th queen placed on the i-th column (all indices are 0-based). So, the first solution looks like this on the board:

[0,2,4,1,3]

 Q · · · ·
 · · · Q ·
 · Q · · ·
 · · · · Q
 · · Q · ·

I will leave it as an exercise to understand why isSafe works, and how to print the board layout, and how to implement faster but more complicated recursive algorithms.

Happy learning.