We have already learnt how to generate combinations of identical items in a 1d array by taking levels as items (in increasing order only) and choices as selecting an empty box.
In this problem, we are given the queens as 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 (in increasing order only) as the levels in the recursion tree, and the choice/edge will be selecting an empty cell (after the last queen's cell).
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.
Hence, if the previous cell i which queen was placed had 1d index lcno, then we will traverse from all the cells in range [lcno + 1, n^2 - 1], find the 2d coordinates accordingly, and check whether placing a queen in that cell will lead to valid configuration or not.
Please note what should be the base case of this problem?
Base case will remain the same. It 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 writing the 'q' for filled cells, else print '-' followed by tab space for the empty cell.
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 4 directions are empty, then we can return true, i.e. we can place a queen at (row, col).