leetcode N-Queens II

N-Queens II

Follow up for N-Queens problem.

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

< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+VGhlIGNvZGUgc2ltaWxhciB0byBJIGlzIFRMRTwvcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">class Solution { public: bool check(vector >& board, int x, int y) { int size = board.size(), xx, yy; for (int i = 0; i < x; ++i) if (board[i][y]) return false; for (int i = 0; i < size; ++i) if (board[x][i]) return false; for (xx = --x, yy = --y; xx >= 0 && yy >= 0; --xx, --yy) if (board[xx][yy]) return false; for (xx = --x, yy = ++y; xx >= 0 && yy < size; --xx, ++yy) if (board[xx][yy]) return false; return true; } void dfs(vector >& board, int& count, int start) { int size = board.size(); if (start == board.size()) { ++count; return; } for (int i = 0; i < size; ++i) { if (check(board, start, i)) { board[start][i] = 1; dfs(board, count, start + 1); board[start][i] = 0; } } } int totalNQueens(int n) { if (n == 0) return 0; int res = 0; vector > board(n, vector (n, 0)); dfs(board, res, 0); return res; } };The main problem is that the check function wastes too much time.

Two ways to avoid this:

1. Use an array to record the position row[i] , col[i](true, false)

2. BIt manipulation

class Solution {
 public:
  unsigned int upperlimit;
  void dfs(int& count, unsigned int row, unsigned int ld, unsigned int rd) {
    if (row == upperlimit)
      ++count;
    unsigned int pos = (row | ld | rd) & upperlimit; // the bit 1 simplify the position can't place the queue any more
    unsigned int p = (~pos) & upperlimit,digit = 0;
    while (p) {
      digit = p - (p & (p - 1)); // Find the rightest 1
      //digit = p&(~p + 1);
      dfs(count, row + digit, (ld + digit) >> 1, (rd + digit) << 1);
      p -= digit;
    }
  }
  int totalNQueens(int n) {
    upperlimit = 0;
    int count = 0;
    for (int i = 0; i < n; ++i)
      upperlimit |= (1<