Programming for the Puzzled - Puzzle 5: Keep Those Queens Apart
Programming for the Puzzled - Puzzle 6: A Profusion of Queens
51. N-Queens
Difficulty: Hard
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:
Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
Solution 1: Place queen row by row
Language: C++
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<int>> boards;
vector<int> board(n, -1);
solveNQueens(n, 0, &board, &boards); // fill row by row
return reconstructBoard(n, boards);
}
void solveNQueens(const int size, const int cur, vector<int>* const board,
vector<vector<int>>* const boards) {
if (board == nullptr || boards == nullptr) {
return;
}
if (cur >= size) {
boards->emplace_back(*board);
return;
}
// for cur-th row, set the column which Queen should be put in
for (int i = 0; i < size; ++i) {
board->at(cur) = i;
if (isValid(cur, *board)) {
solveNQueens(size, cur + 1, board, boards);
}
}
}
bool isValid(const int cur, const vector<int>& board) {
for (int i = 0; i < cur; ++i) {
if (board[i] == board[cur] || abs(board[i] - board[cur]) == cur - i) {
return false;
}
}
return true;
}
vector<vector<string>> reconstructBoard(const int n,
const vector<vector<int>>& boards) {
vector<vector<string>> res(boards.size(),
vector<string>(n, string(n, '.')));
for (size_t i = 0; i < boards.size(); ++i) {
const vector<int>& board = boards[i];
for (size_t j = 0; j < n; ++j) {
// jth row, board[j]-th column is Queen
res[i][j][board[j]] = 'Q';
}
}
return res;
}
};
Solution 2
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<int> cur(n);
for (int i = 0; i < n; ++i) {
cur[i] = i;
}
sovleNQueensHelper(res, cur, n, 0);
return res;
}
private:
void sovleNQueensHelper(vector<vector<string>>& res, vector<int>& cur,
const int& n, int start) {
if (start == n) {
vector<string> r(n, string(n, '.'));
for (int i = 0; i < n; ++i) {
r[i][cur[i]] = 'Q';
}
res.push_back(r);
return;
}
for (int i = start; i < n; ++i) {
std::swap(cur[start], cur[i]);
if (isValid(cur, start)) {
sovleNQueensHelper(res, cur, n, start + 1);
}
std::swap(cur[start], cur[i]);
}
}
bool isValid(const vector<int>& cur, const int& end) {
for (int i = 0; i <= end - 1; ++i) {
for (int j = i + 1; j <= end; ++j) {
if (i - j == cur[i] - cur[j] || j - i == cur[i] - cur[j]) {
return false;
}
}
}
return true;
}
};
52. N-Queens II
Difficulty: Hard
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 the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Solution
Language: C++
class Solution {
public:
int totalNQueens(int n) {
vector<int> board(n, -1);
int sum = 0;
solveNQueens(n, 0, &board, &sum);
return sum;
}
void solveNQueens(const int n, const int cur, vector<int>* const board,
int* const sum) {
if (board == nullptr || sum == nullptr) {
return;
}
if (cur >= n) {
++(*sum);
return;
}
for (int i = 0; i < n; ++i) {
board->at(cur) = i;
if (isValid(cur, *board)) {
solveNQueens(n, cur + 1, board, sum);
}
}
}
bool isValid(const int cur, const vector<int>& board) {
for (int i = 0; i < cur; ++i) {
if (board[i] == board[cur] || abs(board[i] - board[cur]) == cur - i) {
return false;
}
}
return true;
}
};
1001. Grid Illumination
Difficulty: Hard
On a N x N grid of cells, each cell (x, y) with 0 <= x < N and 0 <= y < N has a lamp.
Initially, some number of lamps are on. lamps[i] tells us the location of the i-th lamp that is on. Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).
For the i-th query queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.
After each query (x, y) [in the order given by queries], we turn off any lamps that are at cell (x, y) or are adjacent 8-directionally (ie., share a corner or edge with cell (x, y).)
Return an array of answers. Each value answer[i] should be equal to the answer of the i-th query queries[i].
Example 1:
Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation:
Before performing the first query we have both lamps [0,0] and [4,4] on.
The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,4] is the bottom right corner:
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 1 1
1 1 1 1 1
Then the query at [1, 1] returns 1 because the cell is lit. After this query, the lamp at [0, 0] turns off, and the grid now looks like this:
1 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
1 1 1 1 1
Before performing the second query we have only the lamp [4,4] on. Now the query at [1,0] returns 0, because the cell is no longer lit.
Note:
1 <= N <= 10^90 <= lamps.length <= 200000 <= queries.length <= 20000lamps[i].length == queries[i].length == 2
Solution
Language: C++
class Solution {
public:
vector<int> gridIllumination(const int N, const vector<vector<int>>& lamps,
const vector<vector<int>>& queries) {
vector<int> res;
unordered_map<int, int> x, y, a_d, d_d;
unordered_map<int, unordered_set<int>> ls;
for (const auto& l : lamps) {
auto i = l[0], j = l[1];
if (ls[i].insert(j).second) {
++x[i], ++y[j], ++a_d[i + j], ++d_d[i - j];
}
}
for (const auto& q : queries) {
auto i = q[0], j = q[1];
if (x[i] || y[j] || a_d[i + j] || d_d[i - j]) {
res.emplace_back(1);
for (auto li = i - 1; li <= i + 1; ++li)
for (auto lj = j - 1; lj <= j + 1; ++lj) {
if (ls[li].erase(lj)) {
--x[li], --y[lj], --a_d[li + lj], --d_d[li - lj];
}
}
} else {
res.emplace_back(0);
}
}
return res;
}
};
