← All solutions

The solution is based on realising that a minister can have at most one unsatisfied vote (or in the case of k = 1 or k = 2, a minister must have all votes satisfied). This can be expressed by k · (k − 1) implications (if the decision on vote i is opposite to the minister’s opinion, then the decision on vote j must be according to the minister’s opinion, for all i 6= j). Alternatively, it can be expressed as a 2-CNF formula (for each pair of two votes, at least one must be satisfied). Either way, this gives an efficient way of determining whether a solution exists, as 2-SAT is efficiently solvable.

To find out all values which are uniquely determined, the easiest way is to compute the transitive closure of the implications mentioned above, and then apply all known values. A variable is known if it is included in a k = 1 or k = 2 vote, or if it is implied by its negation.