LeetCode 51. N-Queens

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.."]
]

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<string> queensLayout(vector< vector<int> >& chessBoard) {
  vector<string> res;
  for(int i = 0; i < chessBoard.size(); ++i) {
    string tmp = "";
    for(int j = 0; j < chessBoard[i].size(); ++j) {
      if(chessBoard[i][j] == 1) tmp = tmp + "Q";
      else tmp += ".";
    }
    res.push_back(tmp);
  }
  return res;
}

bool checkRows(vector< vector<int> >& chessBoard, int i, int dep) {
  int tmp = 0;
  // just need to check until the dep-th column
  for(int k = 0; k < dep; ++k) {
    tmp += chessBoard[i][k];
  }
  return tmp == 0;
}

bool checkCols(vector< vector<int> >& chessBoard, int i, int dep) {
  int tmp = 0;
  // just need to check until the i-th row
  for(int k = 0; k < i; ++k) {
    tmp += chessBoard[k][dep];
  }
  return tmp == 0;
}
bool checkDiag(vector< vector<int> >& chessBoard, int i, int dep) {
  int tmp = 0;
  int row = i, col = dep;
  // check left-up diag.
  while(row >= 0 && col >= 0) {
    tmp += chessBoard[row][col];
    row--;
    col--;
  }
  if(tmp > 1) return false;
  tmp = 0;
  row = i, col = dep;
  // check left-down diag.
  while(row < chessBoard.size() && col >= 0) {
    tmp += chessBoard[row][col];
    row++;
    col--;
  }
  return tmp == 1;
}
bool noConflict(vector< vector<int> >& chessBoard, int i, int dep) {
  return checkRows(chessBoard, i, dep) && checkCols(chessBoard, i, dep) && checkDiag(chessBoard, i, dep);
}

void solveQueens(vector< vector<int> >& chessBoard, vector< vector<string> >& res, int dep) {
  if(dep == chessBoard.size()) {
    vector<string> tmp = queensLayout(chessBoard);
    res.push_back(tmp);
    return;
  }
  for(int i = 0; i < chessBoard.size(); ++i) {
    chessBoard[i][dep] = 1;
    if(noConflict(chessBoard, i, dep)) {
      solveQueens(chessBoard, res, dep+1);
    }
    chessBoard[i][dep] = 0;
  }
}

vector< vector<string> > solveQueens(int n) {
  vector< vector<int> > chessBoard(n, vector<int>(n, 0));
  vector< vector<string> > res;
  solveQueens(chessBoard, res, 0);
  return res;
}

int main(void) {
  vector< vector<string> > res = solveQueens(4);
  for(int i = 0; i < res.size(); ++i) {
    for(int j = 0; j < res[i].size(); ++j) {
      cout << res[i][j] << endl;
    }
    cout << endl;
  }
}

LeetCode 51. N-Queens

原文：http://blog.csdn.net/github_34333284/article/details/51343991