Print all unique combinations of setting N pieces on an NxN board

Given an integer N, the task is to print all the unique combinations of putting N pieces in an NxN board.

Note: Print (“*”) for pieces and (“-“) for an empty space.

Example:

Input: N = 2
Output:
* *
– –

* –
* –

* –
– *

– *
* –

– *
– *

– –
* *
Explanation: The total number of empty spaces are 2*2=4 and the pieces to be set is 2 so there are 4C2 combinations ((4!/(2!*2!))=6) possible which is represented above.

Input: N = 1
Output: *

Approach: This problem can be solved by using recursion to generate all possible solutions. Now, follow the steps below to solve this problem:

1. Create a function named allCombinations, which will generate all possible solutions.
2. It will take an integer piecesPlaced denoting the number of total pieces placed, integer N denoting the number of pieces needed to be placed, two integers row and col denoting the row and column where the current piece is going to be placed and a string ans for storing the matrix where pieces are placed, as arguments.
3. Now, the initial call to allCombinations will pass 0 as piecesPlaced, N, 0 and 0 as row and col and an empty string as ans.
4. In each call, check for the base case, that is:
   • If row becomes N and all pieces are placed, i.e. piecesPlaced=N. Then print the ans and return. Else if piecesPlaced is not N, then just return from this call.
5. Now make two calls:
   • One to add a ‘*’ at the current position, and one to leave that position and add ‘-‘.
6. After this, the recursive calls will print all the possible solutions.

Below is the implementation of the above approach.

*    *
-    -

*    -
*    -

*    -
-    *

-    *
*    -

-    *
-    *

-    -
*    *

Time Complexity: O(2^M), where M=N*N
Auxiliary Space: