Understanding ConstrainedArray

[dlidstrom]

I'm confused about why this little sample is giving a lot of results. I'm trying to solve part of a puzzle using VariableIntegers and ConstrainedArray. Here's the sample code:

    // find all solutions to this simple (subset) problem
    // two numbers are correct but wrong placed: [2] [0] [6]
    var validElements = new List<int>
    {
        0, 1, 2, 4, 6, 8, // all these are available in the whole problem
    };
    var first = new VariableInteger("first", validElements);
    var second = new VariableInteger("second", validElements);
    var third = new VariableInteger("third", validElements);

    // first can be 0 or 6
    var allowedForFirst = new ConstrainedArray(new[] { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 });

    // second can be 2 or 6
    var allowedForSecond = new ConstrainedArray(new[] { 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 });

    // third can be 2 or 0
    var allowedForThird = new ConstrainedArray(new[] { 1, 0, 1, 0, 0, 0, 0, 0, 0, 0 });

    // allow 2 in their correct places
    var constraint = new ConstraintInteger(
        allowedForFirst[first] + allowedForSecond[second] + allowedForThird[third] == 2);

    var variables = new[] { first, second, third, };
    var constraints = new List<IConstraint>
        {
            constraint, new AllDifferentInteger(variables),
        };

    IState<int> state = new StateInteger(variables, constraints);

    state.StartSearch(out StateOperationResult searchResult, out var solutions);
    Console.WriteLine("Result:\t{0}Runtime:\t{1}\nBacktracks:\t{2}\n", searchResult, state.Runtime, state.Backtracks);

    foreach (var solution in solutions)
    {
        Console.WriteLine($"[{solution["first"]}] [{solution["second"]}] [{solution["third"]}]");
    }

This is giving a total of 120 combinations (among others, 0-1-4 which is an incorrect solution). I am (probably mistakenly) assuming that the ConstraintInteger would reduce this down to 2. Can you see where this is wrong? Thanks!

[lifebeyondfife]

Hi Daniel,

Thanks again for taking the time to let me know about an issue with the solver, much appreciated.

I've been busy the last few days so thanks for bearing with the delay. That definitely looks suspect, I agree - the total for [0,1,4] is 1 and thus constraint should be false so not a solution. I'll need some time to debug the problem which may be a while (maybe a week or two), but I will get back to you.

Cheers, Iain

[lifebeyondfife]

I'll need some time to debug the problem which may be a while (maybe a week or two), but I will get back to you.

I'm going to have to remove time bounded promises to my commitments because I simply cannot keep them, sorry.

The master branch of Decider has been updated to include a MetaExpression concept which will correctly rule out invalid answers when searching for all solutions using constrained arrays. So, in the above example [0, 1, 4] is no longer listed as a solution.

I won't be publishing a new library version just yet because I can still see issues with valid solutions being rejected. I will update this issue again once a final resolution has been found.

[dlidstrom]

Hi Iain, no problem I can totally relate. I am in no need to actually use this library as I have no real problems to solve. I just thought it looked nice and deserves a decent bug report when I noticed it didn’t work in this case. Thanks for putting in the effort!

[lifebeyondfife]

No bother at all, and thanks again I really appreciate the bug report. Without it I wouldn't have known the extent of how broken the Constrained Array feature was.

This issue has been fixed by https://github.com/lifebeyondfife/Decider/commit/aa223942ae7ad8e1c803817f8e50c38c5a712c18 and https://github.com/lifebeyondfife/Decider/commit/bf6515b985049259fc30cfa5d135b498334827cc