NQueens
A Classic Backtracking Problem

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
Problem Statement:
The nqueens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Two queen can attack each other when they share the same row, column, or diagonal.
One of the many valid configurations for 8Queens problem:
Given an integer n, return all distinct solutions to the nqueens puzzle.
Each solution contains a distinct board configuration of the nqueens' 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.."]]
Example 2:
Input: n = 1
Output: [["Q"]]
Solution:
 NOTE: I highly recommend going through the Backtracking chapters in the order they are given in the Index page to get the most out of it and be able to build a rocksolid understanding.
Prerequisite: Backtracking Fundamentals
Since we have N queens and the puzzle board is N X N, every row in the board needs to have a queen. So we can proceed in the increasing order of row. For each row the suitable candidates would be all the columns that would create no conflict with any of the queens placed in the board so far.
For every suitable candidate we recursively call backtrack( .. ) method to see if that leads to a complete solution. Whenever we get a complete solution, we move on to compute other complete solutions, if any.
You might be tempted to use a 2D array to store the partial solutions. But we can do better than that which would result in space optimization. We can achieve this just by using an 1D array. The index of the array would represent row, and the value would represent in which column in that row we would place a Queen. This is a very powerful technique and often this kind of thinking process impresses the interviewers if you are looking to appear in coding interviews. You can reuse this technique while solving other problems as well.
How would we know if two queens are located diagonally ? Notice that we have two types of diagonals: if you look from top to bottom they either (1) go from left to right, or (2) from right to left. Notice how in the left to right diagonals, for every cell in the board with coordinate [row, col] the value of (row  col) remains the same. On the other hand for right to left diagonals the every cell with coordinate [row, col] the value of (row + col) remains the same. Now suppose we have two cells [row1, col1] and [row2, col2]. If they are on a same diagonal which goes from left to right then we would have
row1  col1 = row2  col2
=> row1  row2 = col1  col2
If the two cells are on a diagonal from right to left then we would have
row1 + col1 = row2 + col2
=> row1  row2 = col2  col1
We consolidate the above two cases by checking if (Math.abs(row1  row2) == Math.abs(col1  col2))
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Time Complexity:
This is a Premium Content. Please subscribe to access the rest of the content.
After subscribing please come back and refresh this page.
Don't forget to take indepth look at the other backtracking problems because that is what would make you comfortable with using the backtracking template and master the art of Backtracking:
 Letter Case Permutation
 Power Set
 All Paths Between Two Nodes
 Word Search
 Sudoku
 Word Square
 Generate Parentheses
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn