algorithm - Algorithm to find all solutions for a boolean sum of products without negation

Question

I'm developing a puzzle game where each level can be completed by making a series of moves. There are eight distinct moves labelled a-h. I have developed a solving function that can be passed a level L and a set of available moves S and it will return whether or not the level can be solved using only the moves from S.

For example, if I call solve(L, {a,b}) then the function may find that the series of moves aaabbaaba solves the puzzle and therefore it returns True.

I'm interested in writing an algorithm to find all sets of available moves that are sufficient to solve a level. Since there are eight distinct moves, there are 2⁸ = 256 possible sets of moves. I could check them all, but that seems rather wasteful. The solver is comparatively slow, so the goal is to use logic to reduce the number of times I need to run the solver.

If just move c is sufficient to solve a level (i.e. solve(L, {c}) == True) then the level would also be solvable with both moves c and d (where move d is available but unnecessary). Likewise, if a level is unsolvable with every move except c (i.e. solve(L, {a,b,d,e,f,g,h}) == False), then the level would also remain unsolvable with every move except both c and d.

More generally:

• If solve(L, S) == True and S⊆T, then solve(L, T) == True
• If solve(L, S) == False and T⊆S, then solve(L, T) == False

I believe this means that the level can be expressed as a Sum of Products without negation. For example, one level may be expressed as a ∨ c∧d∧e ∨ d∧e∧f. (In this case, the level would be solvable with the sets {a}, {c,d,e}, {d,e,f}, and any superset of those sets.)

I suspect that a good algorithm may start by checking the sets containing just one move and those with all but one move so that large numbers of possibilities may be pruned. I tried to come up with a recursive algorithm but I had trouble incorporating both types of pruning.

标签： algorithmperformanceoptimizationlogicboolean-logic

Answer 1

Given n distinct moves, even the best algorithm will need to run the solver very nearly O(2ⁿ) times in the worst case, which is hardly any better than brute-force.

Consider the case with eight distinct moves and a level that can be solved by any combination of four moves. These sets of moves would look like {a,b,c,d}, {a,b,c,e}, etc. There are 8 choose 4 = 70 sets of four moves selected from the eight choices. None of these sets are subsets of each other, so the simplest Sum of Products expression for this level would contain 70 terms.

Consider an algorithm that is already provided with the fact that all 56 sets of three moves don't provide a solution to this level. The algorithm would still, at a minimum, need to check all 70 sets of four moves to validate that each set is sufficient.

Generalizing this worst-case level, given n distinct moves an algorithm would need to run the solver at least n choose ⁿ/₂ times. For large n,

source

Therefore, there is no highly efficient algorithm that performs well in all cases. As j_random_hacker and kcsquared surmised, the best strategy would necessarily depend on the characteristics of the population of levels and the algorithmic complexity of the solver.