We have already learnt how to generate permutations of non-identical items in a 1d array by taking levels as boxes and choices as selecting a non-identical item out of the items not placed so far, or letting the box remain empty.
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 cells of the grid as the levels in the recursion tree, and the choice/edge will be selecting a queen not placed so far or letting the box remain empty
So, the only change will be how to take cells of the grid as the levels instead of indices of 1d array in the simpler version.
We will take the row number and the column number of the cell. There are two possibilities:
- If the current cell is the last cell in it's row, then the next cell will be the first cell of the next row, i.e. if the current cell is (r, n-1), then the next cell will be (r + 1, 0).
- If the current cell is not the last cell in it's row, then the next cell will be the neighbouring cell in right, i.e. if the current cell is (r, c), then the next cell will be (r, c+1).
Please note what should be the base case of this problem?
Base case can be considered when we have taken all the cells of the grid in consideration. Please note that the last cell in the recursion tree will be the bottom-right most cell i.e. (n-1, n-1). Hence, the base case can be considered as when the row number becomes n, because the next cell of (n-1, n-1) will be (n, 0) but it does not exist in the grid.