Read More

## Algorithm with Runtime Complexity O(n!)

The brute-force algorithm is meant to find all possible positions of mines on the board that will match a given board. The algorithm starts with only knowing how many mines are there and the size of the given board. The algorithm starts with an empty board and then performs trial and error until it ends up with a position that matches the given board.

Each candidate solution is represented as a 1-dimensional list which represents a board arrangement. The target board is a 2-dimensional list. The candidate solution can be transformed as a 2-dimensional list to easily compare with the target board. The reason why the candidate solution is represented as a 1-dimensional list is that it makes it easier to calculate possible arrangements.

For example, a 2-dimensional board:

A B

C D

can be represented as a 1-dimensional board:

A B C D

Now we were given the 1-dimensional board, we can find all possible arrangement through permutation:

Arrangement 1: A B C DArrangement 2: A B DC

Arrangement 3: A C B DArrangement 3: A C D B

Arrangement 4: A D B C

Arrangement 5: A D C B

Arrangement 6: B A C D

... (and so on)

But of course, our board only consists of 2 known characters which are "x" (mine) and "-“ (open space). Using the same idea above, we can arrange the mine and open space characters in the list which we can convert as a 2-dimensional board and compare it to the target board.

For example, the target-board board is:

- –

x x

The algorithm will start with an initial arrangement and then find all possible arrangement:

Arrangement 1: x x - - (fails)

Arrangement 2: x – x – (fails)

Arrangement 3: x - - x (fails)

Arrangement 4: - x – x (fails)

Arrangement 5: - - x x (succeeds and stops)

The permutation algorithm is a recursive solution that tries to swap values between 2 positions for all possible combinations. This solution makes it certain that it will at some point find the correct solution. This permutation algorithm makes sure that it only swaps mines and open space characters to avoid generating an arrangement that has already been tried previously (this shortens the time).

The runtime complexity of the algorithm is O(n!). The length or the size of the list which we need to find all possible arrangements affects the efficiency of the code. For instance, a list with size 4 will have 24 possible arrangements.