In the Leetcode N-Queens II problem solution, 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 the number of distinct solutions to the n-queens puzzle.
Example 1:
Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
Example 2:
Input: n = 1
Output: 1
Constraints:
- 1 <= n <= 9
Solution in C Programming
int TotalNQueensInner(int nRet, char acCol[], char cIndex, char cN)
{
for(char i=0; i<cN; i++)
{
bool bIsValid = true;
for(char j=0; j<cIndex; j++)
{
// check verticle: i == acCol[j]
// check diagonal: cIndex - i == j - acCol[j]
// check anti diagonal: cIndex + i == j + acCol[j]
if(i == acCol[j] || cIndex-i == j-acCol[j] || cIndex+i == j+acCol[j])
{
bIsValid = false;
break;
}
}
if(bIsValid == false) continue;
// store
acCol[cIndex] = i;
if(cIndex < cN - 1)
{
nRet = TotalNQueensInner(nRet, acCol, cIndex+1, cN);
}
else
{
nRet++;
}
// restore
acCol[cIndex] = -1;
}
return nRet;
}
int totalNQueens(int n){
if(n == 2 || n == 3) return 0;
if(n == 1) return 1;
char acCol[n];
memset(acCol, -1, n*sizeof(char));
return TotalNQueensInner(0, acCol, 0, n);
}Solution in C++ Programming
class Solution {
public:
int solve(int col, int n, vector<int> &left, vector<int> &upperLeftDiag, vector<int> &lowerLeftDiag) {
if(col == n) {
return 1;
}
int count = 0;
for(int row = 0; row < n; row++) {
if(left[row] == 0 and upperLeftDiag[n - 1 + col - row] == 0 and lowerLeftDiag[row + col] == 0) {
left[row] = 1;
upperLeftDiag[n - 1 + col - row] = 1;
lowerLeftDiag[row + col] = 1;
count += solve(col+1, n, left, upperLeftDiag, lowerLeftDiag);
left[row] = 0;
upperLeftDiag[n - 1 + col - row] = 0;
lowerLeftDiag[row + col] = 0;
}
}
return count;
}
int totalNQueens(int n) {
// Start filling from first column
int col = 0;
vector<int> left(n, 0), upperLeftDiag(2*n - 1, 0), lowerLeftDiag(2*n - 1, 0);
return solve(col, n, left, upperLeftDiag, lowerLeftDiag);
}
};Solution in Java Programming
class Solution {
int count;
public int totalNQueens(int n) {
count = 0;
int[][] matrix = new int[n][n];
findPaths(matrix,0,n);
return count;
}
private void findPaths(int[][] mat, int row, int remQueens) {
if(remQueens == 0) {
count++;
return;
}
if(row == mat.length)
return;
for(int i = 0; i < mat.length; i++) {
if(mat[row][i] == 0 && isValidPath(mat,row,i)) {
mat[row][i] = 1;
findPaths(mat,row + 1, remQueens - 1);
mat[row][i] = 0;
}
}
}
private boolean isValidPath(int[][] matrix, int r, int c) {
int i = r - 1;
int j = c - 1;
while(i >=0 && j>=0) {
if(matrix[i--][j--] == 1)
return false;
}
i = r - 1;
j = c + 1;
while(j < matrix.length && i >= 0) {
if(matrix[i--][j++] == 1)
return false;
}
i = r - 1; j = c;
while(i >= 0) {
if(matrix[i--][j] == 1)
return false;
}
return true;
}
}Solution in Python Programming
class Solution(object):
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
self.out = 0
queens =[['.' for i in range(n)] for j in range(n)]
def isvalid(queens, row, col):
for i in range(row):
if queens[i][col]=='Q':
return False
i, j = row-1, col-1
while(i>=0 and j>=0):
if queens[i][j]=='Q':
return False
i-=1
j-=1
i, j = row-1, col+1
while(i>=0 and j<len(queens)):
if queens[i][j]=='Q':
return False
i-=1
j+=1
return True
def helper(queens, row, n):
if row==n:
self.out+=1
return
for i in range(n):
if isvalid(queens, row, i):
queens[row][i]='Q'
helper(queens, row+1, n)
queens[row][i]='.'
helper(queens, 0, n)
return self.out Solution in C# Programming
public class Solution {
int max = 0;
int count = 0;
int N;
public int TotalNQueens(int n) {
N = n;
if(n % 2 == 0) {
for(int i = 0; i < n/2; i++) {
int[,] board = new int[n,n];
Dictionary<int, int> newQueens = new Dictionary<int, int>();
newQueens.Add(i, 0);
board[0,i] = 1;
DFS(1, board, newQueens);
}
return count * 2;
}
else {
for(int i = 0; i < n; i++) {
int[,] board = new int[n,n];
Dictionary<int, int> newQueens = new Dictionary<int, int>();
newQueens.Add(i, 0);
board[0,i] = 1;
DFS(1, board, newQueens);
}
return count;
}
}
private void DFS(int row, int[,] board, Dictionary<int, int> queens) {
if(queens.Count == N) {
count++;
}
if(row >= N) {
return;
}
for(int i = 0; i < N; i++) {
if(!queens.ContainsKey(i) && !IsQueenDiagonal(row, i, board)) {
var newBoard = board.Clone() as int[,];
Dictionary<int, int> newQueens = new Dictionary<int, int>();
foreach(var kv in queens) {
newQueens[kv.Key] = kv.Value;
}
newQueens.Add(i, row);
newBoard[row,i] = 1;
DFS(row + 1, newBoard, newQueens);
}
}
}
private bool IsQueenDiagonal(int row, int col, int[,] board) {
for(int i = 1; ; i++) {
bool isValid = false;
if(row - i >= 0 && col - i >= 0) {
isValid = true;
if(board[row-i, col-i] == 1) {
return true;
}
}
if(row - i >= 0 && col + i < N) {
isValid = true;
if(board[row-i, col+i] == 1) {
return true;
}
}
if(!isValid) {
return false;
}
}
return false;
}
}Also read,