LeetCode N-Queens I and II: Backtracking and DFS

Overview

LeetCode N-Queens I and II are the classic backtracking problems which could be solved by using DFS + Pruning to enumerate all the solutions.

LeetCode N-Queens I and II

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.

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

For example,
There exist two distinct solutions to the 4-queens puzzle:

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

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

(2)
Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Analysis:  Backtracking and DFS

Both could be solved by backtracking algorithm with pruning. When generating candidates, remove all the positions which obviously lead to conflicts (Queens attack). After all the n queens are placed, the final configuration is stored for I and the global count increases by 1 for II. The following code enumerates all the valid solutions for the N-Queens problem and could be adjusted a bit to solve the second one and it is accepted by LeetCode OJ to pass both N-Queens problems:

class Solution {
    public:
        vector<vector<string>> results;
        vector<string> board;
        vector<int> cols;

        void dfs(int k, int n) {
            if (k == n) {
                for (int i = 0; i < n; ++i) {
                    for (int j = 0; j < n; ++j) {
                        board[i][j] = '.';
                        if (cols[i] == j) board[i][j] = 'Q';
                    }
                }
                results.push_back(board);
                return ;
            }

            for (int j = 0; j < n; ++j) {
                bool cand = true;
                for (int i = 0; cand && i < k; ++i) {
                    if (cols[i] == j || abs(k - i) == abs(cols[i] - j)) {
                        cand = false;
                    }
                }

                if (cand) {
                    cols[k] = j;
                    dfs(k + 1, n);
                }
            }
        }

        vector<vector<string> > solveNQueens(int n) {
            results.clear();
            if (n == 1) {
                vector<string> vec;
                vec.push_back("Q");
                results.push_back(vec);
                return results;
            }
            if (n <= 3)
                return results;

            cols.resize(n);
            fill(cols.begin(), cols.end(), -1);
            board.resize(n);
            for (int i = 0; i < n; ++i) board[i].resize(n);

            dfs(0, n);
            return results;
        }
};

Remarks:

  1. For II, one might still save some time computation by the symmetric property. And for this classical N-Queens problem, n can’t be too large, when n = 14, it might take several minutes to solve.
  2. What about iterative implementation? Is it easier? You might also want to search the bit mask solution for any further reference

Summary

LeetCode N-Queens I and II are the classic backtracking problems which could be solved by using DFS + Pruning to enumerate all the solutions.

Written on May 26, 2013