We have already learnt how to generate permutations of non-identical items in a 1d array by taking levels as items and choices/edges as one of the empty boxes.

In this problem, we are given the **queens as non-identical items**, and there is a slight variation that instead of 1d array of boxes, we are given a 2d array/grid of the chessboard.

So, we will take the **queens as the levels** in the recursion tree, and the **choice/edge will be choosing an empty cell of the grid.**

Also, please remember the conversion from 2d coordinates to 1d indices of the cells, which we saw in the previous solution.

Then, what is the difference in this problem?

As mentioned in the problem statement, queens should be placed such that no two queens can kill each other.

Hence, no two queens can be in the same **row**, or in the same **column**, or in the same **left diagonal** or in the same **right diagonal**.

So, isn't it simple? Instead of traversing through a 1d array, we need to traverse through the 2d array and find all the empty cells such that placing the queen in them will result in a valid configuration, and hence generate the permutations by placing the current queen in them.

Now, the only point of difference is checking whether we can place a queen in the given cell or not. We should complete the function IsQueenSafe(chess, row, col).

We will check for any queen in the row, column, left or right diagonal, and if we find any cell filled with queen, then both can kill each other. Hence, we will return false in such a case. Else, if all the cells in 8 directions are empty, then we can return true, i.e. we can place a queen at (row, col).

Please note what should be the base case of this problem?

Base case can be considered when we have made a decision for all of the queens, i.e. the queens placed so far (qpsf) is equal to the total number of queens available (n or tq). When we hit the base case, we will print the grid, by appending the 'q' letter in front of the queen's item number, else print '-' followed by tab space for the empty cell.