Algorithms Analysing of Eight Queens Problem

Problem Intro

Eight queens problem is based on Chess, it’s for determining how to place 8 queens in chess board of size 8 × 8, and make sure any of the queens cannot capture the other 7 queens. To getting this approach, any of two queens cannot be at the same row, column, and the same diagonal. Actually it has been generalized into N queens problem which the board size is N × N and number of queens is also N, this N queens problem is solvable only iff N = 1 or N ≥ 4.

Implementing Algorithms

Depth-First Search (DFS)

Depth-First Search (abbr. DFS) Algorithms is a famous algorithms to traversal Searching-Tree and Graph. The way of traversal is Depth-First which stepping into sub-nodes rather than siblings nodes, and backtracking (goes back to it’s super-node) when all the edges of current node has been visited. And ending the searching when all of the nodes has been visited. DFS is a famous algorithms in Graph Theory, it can be used to determine graph-related topological sorting table, that can make the problem solving such as shortest-path more straight-forward.

Here is an example of using DFS to traversal a tree, you can follow the path to emulate the DFS process.

def traversalTree(root):
  root.visited = True                    # Marking Visited
  if root.hasSub():
    for node in root.sub:
        traversalTree(node)              # Recursion
  else:
    return                               # Backtracking

# DFS Order  
1 ➔ 2 ➔ 3 ➔ 4 ➔ 5 ➔ 6 ➔ 7 ➔ 8 ➔ 9 ➔ 10 ➔ 11 ➔ 12

Implemenation of such kind of problems is recursion and backtracking. Note that fhe following example is a general solution of recursion and backtracking which are the keys of DFS.

/* DFS template implemented in C++
** Using C/C++ to solve N-Queen problem is by far the fastest approach
** So I will use C++ in following codes
*/
void dfs(int now) {
    // ...
    for (int j = 1; j <= N; j++) {
        if ((!d[j]) && (!l[now + j]) && (!r[now - j + N])) {
            pos[now] = j; d[j] = 1; l[now + j] = 1; r[now - j + N] = 1; // Marking
            dfs(now + 1); // Recursion
            d[j] = 0; l[now + j] = 0; r[now - j + N] = 0; // Backtracking
        }
        // ...
    }

Queens Placement Method

We need spaces to save queens’ position, in this problem, it’s obvious that any of two queens cannot in the same row or same column. Placing queens from top to bottom, and recording in a specific row which grid cannot be placed with a queen, which needs dynamic arrays to maintain. pos[N] array to record every column’s queen position(in which row), pos[2] = 3 means there is a queen in row 3 column 2. d[N] is for maintaining every queens’ down-side cannot have another queens. l[N] and r[N] arrays is for maintaining left-bottom and right-bottom grids cannot have queens. when every recursion to deeper, l and r arrays to be calculated whether the position can place a queen. This process is very easy to understand using the coordinate system.

C++ Code

/* N-Queens Problem
** Code by Ex10si0n
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
int N, cnt, pos[100], d[100], r[100], l[100];

void print() {
    if (cnt > 3)
        return;
    for (int i = 1; i <= N; i++)
        cout << pos[i] << " ";
    cout << endl;
}

void dfs(int now) {
    if (now > N) {
        cnt++;
        print();
        return;
    }
    else {
        for (int j = 1; j <= N; j++) {
            if ((!d[j]) && (!l[now + j]) && (!r[now - j + N])) {
                pos[now] = j; d[j] = 1; l[now + j] = 1; r[now - j + N] = 1;
                dfs(now + 1);
                d[j] = 0; l[now + j] = 0; r[now - j + N] = 0;
            }
        }
    }
}

int main() {
    cin >> N;
    dfs(1);
    cout << cnt << endl;
    return 0;
}

/*

   1 2 3 4 (x)
 1 . x . .
 2 l d r . 
 3 . d . r
 4 . d . .
(y)

x ➜ d, l, r;
d.all = x;
r.all = x - y;
l.all = x + y;

. . . x . .
x . . . . .
. . . . x .
. x . . . .
. . . . . x
. . x . . .

*/

Bonus: Implemented by C++ bit Operations

int upperlim = (1 << n) - 1; // Initialize upperlim with all 1 digits
void work(int row, int ld, int rd) {
    int pos, p;
    if (row != upperlim) {
        pos = upperlim & ~(row | ld | rd);
        // row | ld | rd represent next permutation not be recorded by 1,and negate this value,that is marking avaliable by 1,OR with upperlim,result is the next recording position
        while (pos != 0) {
            p = pos & -pos; // Marked by the rightest 1
            pos = pos - p; // Marking pos
            work(row | p, (ld | p) << 1, (rd | p) >> 1); // search next permutation
        }
    }
    else
        sum++;
}