N Queens

Description

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.

Example
There exist two distinct solutions to the 4-queens puzzle:
[
  // Solution 1
  [".Q..",
   "...Q",
   "Q...",
   "..Q."
  ],
  // Solution 2
  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."
  ]
]

Challenge:
Can you do it without recursion?

Link

Lintcode_ladder

Method

1. find combination and test it
   • dfs find all combination
     vector row, index means row number
     and value means colunm num,
   • use isValid() to test the middle result's validation
   • use draw() to translate vector row to chessboard
   • use pruning and de-dup
2. x

Example

1. 1

class Solution {
public:
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    vector<vector<string> > solveNQueens(int n) {
        // write your code here
        vector<vector<string>> result;
        if (n < 1) {
            return result;
        }
        // --------------------------------------------------------------------
        // Version 1, 45ms
        // flat, using extra n^2 space
        // @param permutation: index means column, value means row
        vector<vector<int>> permutation;
        vector<int> row(n ,0);
        // find all permutation
        helper(permutation, row, 0);
        // transform permutation to the result
        display(result, permutation);
        return result;
        // --------------------------------------------------------------------
        // Version 2, 47ms
        // Integrate into one
        vector<int> row;
        helper(result, row, n);
        return result;
    }
    // ------------------------------------------------------------------------
    // Version 1, 45ms
    // flat, using extra n^2 space
    // permutation traversal
    void helper(vector<vector<int>>& result, vector<int>& row, int rownum) {
        int n = row.size();
        if (rownum == n) {
            result.push_back(row);
            return;
        }
        for (int i = 0; i < n; ++i) {
            // pruning unavlid status
            if (!isValid(row, i, rownum)) {
                continue;
            }
            row[rownum] = i;
            helper(result, row, rownum + 1);
            // row.erase(row.begin() + row.size() - 1);
            row[rownum] = 0;
        }
        return;
    }
    // valid tester
    bool isValid(vector<int>& row, int colnum, int rownum) {
        //  int rownum = row.size();
        for (int i = 0; i < rownum; ++i) {
            // vector<int> row has avoided the row conflict
            // this will avoid the column conflict
            if (row[i] == colnum) {
                return false;
            }
            // for the corss conflict
            // if diff of row == diff of col
            // .Q..
            // ..Q. has 1 row diff and 1 col diff => cross conflict
            if (abs(i - rownum) == abs(row[i] - colnum)) {
                return false;
            }
        }
        return true;
    }
    // display
    void display(vector<vector<string>>& result, 
        vector<vector<int>>& permutation
    ) {
        // vector<vector<string>> result(n, vector<sting>(n, "."));
        if (permutation.empty()) {
            return;
        }
        int len = permutation.size();
        int n = permutation[0].size();
        vector<string> raw(n);
        // for one solution 
        for (int i = 0; i < len; ++i) {
            // for one row
            for (int j = 0; j < n; ++j) {
                string row(n, '.');
                row[permutation[i][j]] = 'Q';
                // for current solution, add one row
                raw[j] = row;
            }
            // for ith solution
            result.push_back(raw);
        }
        return;
    }
    // ------------------------------------------------------------------------
    // Version 2, Integrate into one
    // find all permutations
    void helper(vector<vector<string>>& result, vector<int>& row, int n) {
        if (row.size() == n) {
            result.push_back(formatPermutation(row));
            return;
        }
        for (int i = 0; i < n; ++i) {
            // pruning unavlid status
            if (!isValid(row, i)) {
                continue;
            }
            row.push_back(i);
            helper(result, row, n);
            row.pop_back();
        }
        return;
    }
    // valid tester
    bool isValid(vector<int>& row, int colnum) {
         int rownum = row.size();
        for (int i = 0; i < rownum; ++i) {
            // vector<int> row has avoided the row conflict
            // this will avoid the column conflict
            if (row[i] == colnum) {
                return false;
            }
            // for the corss conflict
            // if diff of row == diff of col
            // .Q..
            // ..Q. has 1 row diff and 1 col diff => cross conflict
            if (abs(i - rownum) == abs(row[i] - colnum)) {
                return false;
            }
        }
        return true;
    }
    // format reault : from int array to string 
    vector<string> formatPermutation(vector<int>& row) {
        int n = row.size();
        vector<string> result;
        for (int i = 0; i < n; ++i) {
            string line(n, '.');
            line[row[i]] = 'Q';
            result.push_back(line);
            // cout<< "line = " << line << endl;
        }
        return result;
    }
};

Similar problems

x

Tags

x