N-Queens – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
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 1:
Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1 Output: [["Q"]]
Constraints:
1 <= n <= 9
C++ N-Queens LeetCode Solution
class Solution {
public:
std::vector<std::vector<std::string> > solveNQueens(int n) {
std::vector<std::vector<std::string> > res;
std::vector<std::string> nQueens(n, std::string(n, '.'));
solveNQueens(res, nQueens, 0, n);
return res;
}
private:
void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, int row, int &n) {
if (row == n) {
res.push_back(nQueens);
return;
}
for (int col = 0; col != n; ++col)
if (isValid(nQueens, row, col, n)) {
nQueens[row][col] = 'Q';
solveNQueens(res, nQueens, row + 1, n);
nQueens[row][col] = '.';
}
}
bool isValid(std::vector<std::string> &nQueens, int row, int col, int &n) {
//check if the column had a queen before.
for (int i = 0; i != row; ++i)
if (nQueens[i][col] == 'Q')
return false;
//check if the 45° diagonal had a queen before.
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
if (nQueens[i][j] == 'Q')
return false;
//check if the 135° diagonal had a queen before.
for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
if (nQueens[i][j] == 'Q')
return false;
return true;
}
};
Java N-Queens LeetCode Solution
public class Solution {
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
board[i][j] = '.';
List<List<String>> res = new ArrayList<List<String>>();
dfs(board, 0, res);
return res;
}
private void dfs(char[][] board, int colIndex, List<List<String>> res) {
if(colIndex == board.length) {
res.add(construct(board));
return;
}
for(int i = 0; i < board.length; i++) {
if(validate(board, i, colIndex)) {
board[i][colIndex] = 'Q';
dfs(board, colIndex + 1, res);
board[i][colIndex] = '.';
}
}
}
private boolean validate(char[][] board, int x, int y) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < y; j++) {
if(board[i][j] == 'Q' && (x + j == y + i || x + y == i + j || x == i))
return false;
}
}
return true;
}
private List<String> construct(char[][] board) {
List<String> res = new LinkedList<String>();
for(int i = 0; i < board.length; i++) {
String s = new String(board[i]);
res.add(s);
}
return res;
}
}
Python 3 N-Queens LeetCode Solution
def solveNQueens(self, n):
def DFS(queens, xy_dif, xy_sum):
p = len(queens)
if p==n:
result.append(queens)
return None
for q in range(n):
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
result = []
DFS([],[],[])
return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below
