I have variables x y and z, and I have the values that they can be assigned to, I.E. x can be assigned 1,2, or 3, y can be 1, and z can be 2. The problem is a constraint that says once a value has been taken by a variable, no other variables can have that value.

The issue that I am running into is if I start with x, how can I efficiently tell that it's value should be 3?

  • $\begingroup$ Is the set of possible values can contain an infinite number of elements? $\endgroup$ – user3563894 Sep 3 '18 at 16:06
  • $\begingroup$ Also, how the set of possible values is represented by? $\endgroup$ – user3563894 Sep 3 '18 at 16:09
  • $\begingroup$ Set of values is finite, and I am not sure I understand your second question. $\endgroup$ – Krispies Sep 3 '18 at 16:14
  • $\begingroup$ Can we assume that the set of values is represented by a set $S=\{v_1,v_2,\ldots,v_n \}$? $\endgroup$ – user3563894 Sep 3 '18 at 16:16
  • $\begingroup$ And is there a single constraint as described above, or there are multiple constraints, and one of them is that "once a value has been taken by a variable, no other variables can have that value"? $\endgroup$ – user3563894 Sep 3 '18 at 16:19

The problem you are describing amounts to constraint programming and the specific constraint you are talking about is the alldifferent constraint. I'm not offering a purely algorithmic solution, but reading a bit on constraint programming could give you some ideas on how to construct a search tree where you make a decision (i.e., assign a value to a variable) at each node, and how to backtrack to a feasible node when you reach an infeasible node.


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.