• 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 n-queens 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 8-Queens problem:

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 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 rock-solid 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 in-depth 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:


The above content is written by:

Abhishek Dey

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave