Given a minesweeper configuration. How many way are there to fill it to make the configuration correct.
Is there any better solution than brute-force method ?
Example:
Given configuration:
1_11_2__b (b = bomb, _ = blank)
one way to fill it is:
1b11b2b2b
Standard 2D minesweeper has been shown to be NP complete-that finding if there is a way to solve a given partially filled in board is hard. I would guess that 1D is not, there isn't enough room to make the required structures. In any case, you probably want one pass that fills in all the squares that have to be one kind or the other-for example your first blank. That would solve all the squares except the last, which can be b or 2. Then start a backtracking algorithm-try one and see if it works, then the other. You may well have to split into subcases. Dynamic programming makes structuring this easier.