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.."] ]----------------------------------------------------------------------
Typical DFS. Set up 3 vector<bool>s to indicate conflict
Red is backslash
Blue is slash
Green is row
class Solution {
public:
void queens(vector<vector<string> > &ret,vector<bool> &slash, vector<bool> &backslash, vector<bool> &usedRow, vector<string> cur, int col, int n) {
if (col == n) {
ret.push_back(cur);
return;
}
for (int row = 0; row < n; row++) {
// check conflicts in diagonals and same row
if (slash[col + row] && backslash[row-col + n] && usedRow[row]) {
cur[row][col] = 'Q';
slash[col + row] = false;
backslash[row-col + n] = false;
usedRow[row] = false;
queens(ret,slash,backslash,usedRow,cur,col+1,n);
// backtrack
cur[row][col] = '.';
slash[col + row] = true;
backslash[row-col + n] = true;
usedRow[row] = true;
}
}
}
vector<vector<string> > solveNQueens(int n) {
vector<vector<string> > ret;
vector<bool> slash(n*2,true);
vector<bool> backslash(n*2,true);
vector<bool> usedRow(n,true);
// populate vectors
string str = "";
for (int i = 0; i < n; i++) {
char c = '.';
str += c;
}
vector<string> cur(n,str);
queens(ret,slash,backslash,usedRow,cur,0,n);
return ret;
}
};
Update Feb-10-2015Using bit operation
class Solution {
public:
string getString(int n, int p) {
string s(n,'.');
s[p] = 'Q';
return s;
}
void queens(vector<vector<string> > &rt, vector<string> cur,int slash, int backSlash, int row, int n) {
int upperLimit = (1 << n) - 1;
if (row == upperLimit) {
rt.push_back(cur);
return;
}
int possiblePositions = upperLimit & (~(slash | backSlash | row));
int itr = possiblePositions;
int p = n - 1;
while (possiblePositions != 0) {
int rightMost = possiblePositions & (-possiblePositions);
if (itr & 1) {
string s = getString(n,p);
vector<string> temp = cur;
temp.push_back(s);
possiblePositions -= rightMost;
queens(rt,temp,(slash + rightMost) << 1,(backSlash + rightMost) >> 1,row + rightMost,n);
}
p--;
itr >>= 1;
}
}
vector<vector<string> > solveNQueens(int n) {
vector<vector<string> > rt;
vector<string> cur;
queens(rt,cur,0,0,0,n);
return rt;
}
};
Java, updated on Sep-8th-2018
O(n!)
T(n) = n * T(n - 1)
class Solution {
public List> solveNQueens(int n) {
boolean[] cols = new boolean[n];
boolean[] diag = new boolean[n * 2]; // row + col
boolean[] antiDiag = new boolean[n * 2]; // row - col + n - 1
List> rt = new ArrayList<>();
dfs(0, n, new ArrayList(), rt, cols, diag, antiDiag);
return rt;
}
private void dfs(int row, int n, List sofar, List> rt,
boolean[] cols, boolean[] diag, boolean[] antiDiag) {
if (row >= n) {
rt.add(sofar);
return;
}
String cur = "";
for (int i = 0; i < n; i++) {
if (!cols[i] && !diag[row + i] && !antiDiag[row - i + n - 1]) {
cols[i] = true;
diag[row + i] = true;
antiDiag[row - i + n - 1] = true;
String tmp = cur + "Q";
for (int j = i + 1; j < n; j++) tmp += ".";
List tmpSofar = new ArrayList<>(sofar);
tmpSofar.add(tmp);
dfs(row + 1, n, tmpSofar, rt, cols, diag, antiDiag);
cols[i] = false;
diag[row + i] = false;
antiDiag[row - i + n - 1] = false;
}
cur += ".";
}
}
}
N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
---------------------------------------------------------------------
Solution #1 similar to previous problem
Note that usedRow[row] should be checked first otherwise it exceeds OJ's time limit
class Solution {
public:
void queens(int &ret,vector<bool> &slash, vector<bool> &backslash, vector<bool> &usedRow, int col, int n) {
if (col == n) {
ret++;
return;
}
for (int row = 0; row < n; row++) {
if (usedRow[row] && slash[col + row] && backslash[row-col + n]) {
slash[col + row] = false;
backslash[row-col + n] = false;
usedRow[row] = false;
queens(ret,slash,backslash,usedRow,col+1,n);
// backtrack
slash[col + row] = true;
backslash[row-col + n] = true;
usedRow[row] = true;
}
}
}
int totalNQueens(int n) {
vector<bool> slash(n*2,true);
vector<bool> backslash(n*2,true);
vector<bool> usedRow(n,true);
int ret = 0;
queens(ret,slash,backslash,usedRow,0,n);
return ret;
}
};
Solution #2http://www.matrix67.com/blog/archives/266
Update on Nov-13-2014
基本思路为DFS
~(row | slash | backSlash) 代表每行上的可放位置，当切入到下一行时，slash跟backSlash分别需要位移一位
possiblePosition 代表当前行所有可放入棋子的位置
rightMostOne 代表当前放入棋子的位置
拿一个例子走一遍代码，立即能明白此算法
class Solution {
public:
void bitOP(int &num, int row, int slash, int backSlash, int n) {
int upperLimit = (1 << n) - 1; // upperLimit has n of '1'
if (row == upperLimit) {
num++;
return;
}
int possiblePosition = upperLimit & (~(row | slash | backSlash)); // get posiible positions for queen in a row
while (possiblePosition != 0) {
int rightMostOne = possiblePosition & (-possiblePosition); // get the most right '1' as new queen's position
possiblePosition -= rightMostOne;
bitOP(num, row + rightMostOne, (slash + rightMostOne) << 1, (backSlash + rightMostOne) >> 1,n);
}
}
int totalNQueens(int n) {
int num = 0;
bitOP(num,0,0,0,n);
return num;
}
};
Spiral MatrixGiven a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]You should return
[1,2,3,6,9,8,7,4,5].-----------------------------------------------------------
Similar to #59, Spiral Matrix II
start at the outer most layer
class Solution {
public:
void spiral (vector<vector<int> > &matrix, vector<int> &ret, int m, int n, int k) {
if (m <= 0 || n <= 0) {
return;
}
if (m == 1) {
for (int i = 0; i < n; i++) {
ret.push_back(matrix[k][k + i]);
}
return;
}
if (n == 1) {
for (int i = 0; i < m; i++) {
ret.push_back(matrix[k + i][k]);
}
return;
}
// going right
for (int i = 0; i < n - 1; i++) {
ret.push_back(matrix[k][i + k]);
}
// going down
for (int i = 0; i < m - 1; i++) {
ret.push_back(matrix[k + i][n - 1 + k]);
}
// going left
for (int i = 0; i < n - 1; i++ ) {
ret.push_back(matrix[m - 1 + k][n - 1 + k - i]);
}
// going up
for (int i = 0; i < m - 1; i++ ) {
ret.push_back(matrix[k + m - 1 - i][k]);
}
spiral(matrix,ret,m-2,n-2,k+1);
}
vector<int> spiralOrder(vector<vector<int> > &matrix) {
int m = matrix.size();
vector<int> ret;
if (m == 0) return ret;
int n = matrix[0].size();
spiral(matrix,ret,m,n,0);
return ret;
}
};
No comments:
Post a Comment