N Queens Puzzle - Amazon Top Interview Questions
Problem Statement :
The n queens puzzle asks to place n queens on an n×n chessboard so that no two queens are attacking each other.
Given a partially filled two-dimensional integer matrix where 1 represents a queen and 0 represents an empty cell, return whether this configuration of the board can solve the puzzle.
Constraints
1 ≤ n ≤ 15
Example 1
Input
matrix = [
[1, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0]
]
Output
True
Explanation
One solution is:
[1, 0, 0, 0, 0]
[0, 0, 1, 0, 0]
[0, 0, 0, 0, 1]
[0, 1, 0, 0, 0]
[0, 0, 0, 1, 0]
Solution :
Solution in C++ :
int N;
bool canPlace(vector<vector<int>>& matrix, int row, int col) {
for (int i = 0; i < N; ++i) {
if (matrix[i][col] or matrix[row][i]) return false;
}
int x = row, y = col;
while (x >= 0 and y >= 0) {
if (matrix[x--][y--]) return false;
}
x = row, y = col;
while (x >= 0 and y < N) {
if (matrix[x--][y++]) return false;
}
x = row, y = col;
while (x < N and y >= 0) {
if (matrix[x++][y--]) return false;
}
x = row, y = col;
while (x < N and y < N) {
if (matrix[x++][y++]) return false;
}
return true;
}
bool alreadyFilled(vector<vector<int>>& matrix, int row) {
for (int j = 0; j < N; ++j) {
if (matrix[row][j]) return true;
}
return false;
}
bool nQueen(vector<vector<int>>& matrix, int row) {
if (row == N) {
return true;
}
if (alreadyFilled(matrix, row)) return nQueen(matrix, row + 1);
for (int j = 0; j < N; ++j) {
if (canPlace(matrix, row, j)) {
matrix[row][j] = 1;
if (nQueen(matrix, row + 1)) return true;
matrix[row][j] = 0;
}
}
return false;
}
bool solve(vector<vector<int>>& matrix) {
N = matrix.size();
return nQueen(matrix, 0);
;
}
Solution in Java :
import java.util.*;
class Solution {
// TOP LEFT TO BOTTOM RIGHT
private Set<Integer> ord;
// bottom left to top right
private Set<Integer> wack;
private Set<Integer> rows;
private Set<Integer> columns;
private int[][] matrix;
public boolean solve(int[][] matrix) {
this.matrix = matrix;
ord = new HashSet();
wack = new HashSet();
rows = new HashSet();
columns = new HashSet();
int count = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 1) {
count++;
rows.add(i);
columns.add(j);
wack.add(i + j);
ord.add(i - j);
}
}
}
return recurse(0, 0, count);
}
public boolean recurse(int i, int j, int count) {
if (count == matrix.length) {
return true;
}
if (j == matrix[0].length) {
i++;
j = 0;
}
if (i == matrix.length)
return false;
if (!rows.contains(i) && !columns.contains(j) && !wack.contains(i + j)
&& !ord.contains(i - j)) {
rows.add(i);
columns.add(j);
wack.add(i + j);
ord.add(i - j);
if (recurse(i, j + 1, count + 1))
return true;
rows.remove(i);
columns.remove(j);
wack.remove(i + j);
ord.remove(i - j);
}
return recurse(i, j + 1, count);
}
}
Solution in Python :
class Solution:
def solve(self, board):
n = len(board)
rows, cols = [False] * n, [False] * n
diagll, diagrr = [False] * (2 * n - 1), [False] * (2 * n - 1)
def handleBlocking(row, col, action):
board[row][col] = rows[row] = cols[col] = action
diagll[row + col] = diagrr[row - col + n - 1] = action
def isSafe(row, col):
ans = (
board[row][col]
+ rows[row]
+ cols[col]
+ diagll[row + col]
+ diagrr[row - col + n - 1]
)
return ans == 0
for i in range(n):
for j in range(n):
if board[i][j] == 1:
handleBlocking(i, j, 1)
def nqueen(row=0):
if row == n:
return True
if 1 in board[row]:
return nqueen(row + 1)
for col in range(n):
if isSafe(row, col):
handleBlocking(row, col, 1)
if nqueen(row + 1):
return True
handleBlocking(row, col, 0)
return False
ans = nqueen()
return ans
View More Similar Problems
Pair Sums
Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v
View Solution →Lazy White Falcon
White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi
View Solution →Ticket to Ride
Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o
View Solution →Heavy Light White Falcon
Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim
View Solution →Number Game on a Tree
Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy
View Solution →Heavy Light 2 White Falcon
White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr
View Solution →