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 knights 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 knights (in increasing order only) as the levels in the recursion tree, and the choice/edge will be selecting an empty cell (after the last knight'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, knights should be placed such that no two knights can kill each other.
Hence, no two knights can be at one knight's move from each other.
If the previous cell i which knight 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 knight 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 knights, i.e. the knights placed so far (kpsf) is equal to the total number of knights available (n or tk). When we hit the base case, we will print the grid, by writing the 'k' 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 knight in the given cell or not. We should complete the function IsKnightSafe(chess, row, col).
We will check for cells (i-1, j-2) , (i-2, j-1) , (i - 2, j+1) , (i-1, j+2) whether there is any knight in at least one of the four cells. (Also, before checking for chess[r][c], check whether (r, c) are valid coordinates or not). If there is no knight present in all 4 cells, then return true, else return false.
Note: We are only checking 4 out of 8 possible knight's moves because we are sure that there will be no knight in the cells after the current row and current column. This is because we are filling cells in increasing order only.