Home
Using Recursive Backtracking Algorithm to Solve Classic N Queen Problem
Tags:, , ,

Using Recursive Backtracking Algorithm to Solve Classic N Queen Problem

January 2, 2020 No Comments algorithms, c / c++, DFS, recursive

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.

8-queens Using Recursive Backtracking Algorithm to Solve Classic N Queen Problem algorithms c / c++ DFS recursive

8-queens

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
Example:

Input: 4

1
2
3
4
5
6
7
8
9
10
11

Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],
 
 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Backtracking Algorithm for N Queen

The backtracking algorithm is implemented in Recursion where we repeatedly try the valid positions for current queen then next queen and so on. We pass the current solution (for placing the first N queens) into the Recursive function, then we can try N positions for current queen if it does not violate the rules with the existing solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    int totalNQueens(int n) {
        int r = 0;
        dfs({}, n, r);
        return r;
    }
private:
    void dfs(vector<int> cur, int n, int &r) {
        if (cur.size() == n) {
            ++ r;
            return;
        }
        for (int i = 0; i < n; ++ i) {
            if (validQueenPosition(cur, i)) {
                cur.push_back(i);
                dfs(cur, n, r);
                cur.pop_back();
            }
        }
    }
    
    bool validQueenPosition(vector<int> cur, int x) {
        for (int i = 0; i < cur.size(); ++ i) {
            // on the same diag 
            if (abs(i - (int)cur.size()) == abs(x - cur[i])) {
                return false;
            }
            // on the same column
            if (x == cur[i]) return false;
        }
        return true;
    }    
};
class Solution {
public:
    int totalNQueens(int n) {
        int r = 0;
        dfs({}, n, r);
        return r;
    }
private:
    void dfs(vector<int> cur, int n, int &r) {
        if (cur.size() == n) {
            ++ r;
            return;
        }
        for (int i = 0; i < n; ++ i) {
            if (validQueenPosition(cur, i)) {
                cur.push_back(i);
                dfs(cur, n, r);
                cur.pop_back();
            }
        }
    }
    
    bool validQueenPosition(vector<int> cur, int x) {
        for (int i = 0; i < cur.size(); ++ i) {
            // on the same diag 
            if (abs(i - (int)cur.size()) == abs(x - cur[i])) {
                return false;
            }
            // on the same column
            if (x == cur[i]) return false;
        }
        return true;
    }    
};

If we want the detailed solutions rather than the count, we can modify the DFS (Depth First Search) terminating condition – when N queens are placed successfully. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> r;
        dfs({}, n, r);
        return r;
    }
 
private:
    void dfs(vector<int> cur, int n, vector<vector<string>> &r) {
        if (cur.size() == n) {
            vector<string> ans;
            for (const auto &s: cur) {
                string row(n, '.');
                row[s] = 'Q';
                ans.push_back(row);
            }
            r.push_back(ans);
            return;
        }
        for (int i = 0; i < n; ++ i) {
            if (validQueenPosition(cur, i)) {
                cur.push_back(i);
                dfs(cur, n, r);
                cur.pop_back();
            }
        }
    }
    
    bool validQueenPosition(vector<int> cur, int x) {
        for (int i = 0; i < cur.size(); ++ i) {
            // on the same diag 
            if (abs(i - (int)cur.size()) == abs(x - cur[i])) {
                return false;
            }
            // on the same column
            if (x == cur[i]) return false;
        }
        return true;
    }
};
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> r;
        dfs({}, n, r);
        return r;
    }

private:
    void dfs(vector<int> cur, int n, vector<vector<string>> &r) {
        if (cur.size() == n) {
            vector<string> ans;
            for (const auto &s: cur) {
                string row(n, '.');
                row[s] = 'Q';
                ans.push_back(row);
            }
            r.push_back(ans);
            return;
        }
        for (int i = 0; i < n; ++ i) {
            if (validQueenPosition(cur, i)) {
                cur.push_back(i);
                dfs(cur, n, r);
                cur.pop_back();
            }
        }
    }
    
    bool validQueenPosition(vector<int> cur, int x) {
        for (int i = 0; i < cur.size(); ++ i) {
            // on the same diag 
            if (abs(i - (int)cur.size()) == abs(x - cur[i])) {
                return false;
            }
            // on the same column
            if (x == cur[i]) return false;
        }
        return true;
    }
};

We are using the C++ std::string(n, char) constructor to initialise a string that is size n and pre-filled with character char.

Please note that there are faster implementation on finding the number of valid solutions for N queen problem using bitwise techniques: N Queen Problem in Back Tracing, Bit-logics

See other implementations of N-Queen Problems:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
787 words
Last Post: Using Recursive Merge Sort Algorithm to Sort a Linked List in O(NLogN)
Next Post: Know The Effective and Smart SEO Reporting Tool You Must Use

The Permanent URL is: Using Recursive Backtracking Algorithm to Solve Classic N Queen Problem

Related posts:

  1. Algorithm to Reformat the Phone Number You are given a phone number as a string number. number consists of digits, spaces...
  2. Simple Calculation without Integration Q: Compute without integration. A: We know , Therefore, Therefore, The normal method: –EOF (The...
  3. C++ Coding Reference: is_sorted_until() and is_sorted() We talked about sorting (unstable and stable) algorithms implemented in C++ STL. The STL algorithm...
  4. Develop a Load Balancer using AWS Lambda Why Lambda? AWS Lambda is serverless and low costs. We don’t need to maintain (upgrade,...
  5. Bruteforce or Line Sweep Algorithms to Remove Covered Intervals Given a list of intervals, remove all intervals that are covered by another interval in...
  6. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  7. How to Implement Integer Square Root in C/C++? Question: Implement integer square root for int sqrt(int x) There are many ways to compute the...
  8. C++ Chess Board Printing in Windows Using CodePage 437 – Extended ASCII Well, most people, when they start programming in C/C++, they would like to print something...

Leave a Reply