2
$\begingroup$

When you pick up some reading about CSP the main focus is how to solve it. My goal is to compute/decide if CSP is ambiguous (has 2 or more solutions) or not (has 1 solution).

Of course brute-force approach would be to solve it and see the outcome. But I am looking for something simpler (read: way faster).

Background: I would like to write Zebra puzzle generator. There is no much resources about it, as with regular CSP, most are solvers, and 2 links I followed take such approach -- start from all clues, at each step reduce by one and solve it. If it unsolvable, get back that clue, and continue.

$\endgroup$
1
$\begingroup$

You shouldn't be able to beat the complexity of brute-forcing (because of having to check all possible assignments in the case that the CSP is not satisfiable). Instead, I offer the possibility of smart brute-forcing:

Solve the CSP normally and find a single assignment that satisfies it, if one exists. Add the negation of that assignment as a new constraint and jump back to the immediate last decision assignment you made and continue from there. This is a typical procedure for SAT solvers which traverse Implication Graphs and add conflicting clauses as constraints before backtracking to the last assignment decision. However, in the case of solving a SAT problem, each boolean variable can only have one of two possible assignments which is not true for the domains of constraints of CSPs, so you might actually need to backtrack further to find another complete assignment of all variables if one should exist (as per usual brute-forcing).

Let's suppose you have a CSP of three variables $A, B, C$. If you find a solution to the CSP whereby (let's say) C was assigned last, you could backtrack to the point right before making the assignment to C and continue from there, seeing if the same assignments of $A$ and $B$ could lead to a second solution with a different assignment of $C$. After finding your second solution, you could immediately terminate, knowing that the CSP is ambiguous. However, you might have to very well check all possible assignments of each variable in the case your initial solution to the CSP were the only solution (or even when your CSP is not satisfiable), in which case it would be unambiguous. So clearly, this procedure would only improve your efficiency for ambiguous CSPs where any two of all solutions differ with a single variable assignment.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.