I want minizinc to find solution in a particular order to minimize the overlap with existing solutions.

Sort of bredth first search instead of depth first search, if that makes sense.

I am using a simple nqueens program to demonstrate my requirement.

int: n; % The number of queens.

array [1..n] of var 1..n: q;

include "alldifferent.mzn";

constraint alldifferent(q);
constraint alldifferent(i in 1..n)(q[i] + i);
constraint alldifferent(i in 1..n)(q[i] - i);

If I run minizinc -D n=8 nqueens.mzn --all-solutions --soln-sep '' | head -n 5

I get following output

q = [4, 2, 7, 3, 6, 8, 5, 1];
q = [5, 2, 4, 7, 3, 8, 6, 1];
q = [3, 5, 2, 8, 6, 4, 7, 1];
q = [3, 6, 4, 2, 8, 5, 7, 1];
q = [5, 7, 1, 3, 8, 6, 4, 2];

Here are overlap scores

First: 0 (Obviously - since there are no prior solutions) Second: 2 (Queens 1 and 8 are in same position) Third: 2 (Queens 1 and 6 are in positions they have been before) Fourth: 4 (Queens 1, 7, 4 and 3 are in positions they have been before)

Is there a way I can keep track of this score in the program and find solution in a particular order? Or even simple methods like search heuristics?

I am interested in finding more novel solutions first.

Symmetry: Original application does not have any symmetry, so we can ignore the symmetry in this nqueens problem.

I want minizinc to find solution in a particular order to minimize the overlap with existing solutions.

Sort of bredth first search instead of depth first search, if that makes sense.

I am using a simple nqueens program to demonstrate my requirement.

int: n; % The number of queens.

array [1..n] of var 1..n: q;

include "alldifferent.mzn";

constraint alldifferent(q);
constraint alldifferent(i in 1..n)(q[i] + i);
constraint alldifferent(i in 1..n)(q[i] - i);

If I run minizinc -D n=8 nqueens.mzn --all-solutions --soln-sep '' | head -n 5

I get following output

q = [4, 2, 7, 3, 6, 8, 5, 1];
q = [5, 2, 4, 7, 3, 8, 6, 1];
q = [3, 5, 2, 8, 6, 4, 7, 1];
q = [3, 6, 4, 2, 8, 5, 7, 1];
q = [5, 7, 1, 3, 8, 6, 4, 2];

Here are overlap scores

First: 0 (Obviously - since there are no prior solutions) Second: 2 (Queens 1 and 8 are in same position) Third: 2 (Queens 1 and 6 are in positions they have been before) Fourth: 4 (Queens 1, 7, 4 and 3 are in positions they have been before)

Is there a way I can keep track of this score in the program and find solution in a particular order? Or even simple methods like search heuristics?

I am interested in finding more novel solutions first.

Symmetry: Original application does not have any symmetry, so we can ignore the symmetry in this nqueens problem.

• minizinc
• gecode

Share Improve this question Follow edited Mar 7 at 10:19 Laurent Perron 11.1k11 gold badge99 silver badges2626 bronze badges asked Mar 7 at 9:07 KrishnaKrishna 1,42222 gold badges1313 silver badges3535 bronze badges 1

• I see or-tools tag is removed. Is it not possible with or-tools? – Krishna Commented Mar 7 at 10:28

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

I found an iterative approach to achieve this. I am pretty sure this is not the efficient way, but this is all I got after a week, so posting here.

Open for suggestions on improvements.

The full code is below

Using minizinc in Python, I am keeping track of solution frequency and asking the model to minimize the overlap score with latest solution frequency at each iteration.

Like I said there should be a better way to do this.

#! /usr/bin/env python3
import minizinc


def getModel(i, freq):
    '''Returns the model for the n-Queens problem with n=i'''

    freqStr = ', '.join(str(x) for x in freq)
    modelStr = f'''
        int: n={i};
        array[1..n, 1..n] of int: freq = array2d(1..n, 1..n, [{freqStr}]);

        array[1..n] of var 1..n: q;

        include "alldifferent.mzn";

        constraint all_different(q);
        constraint all_different(i in 1..n) (q[i]+i);
        constraint all_different(i in 1..n) (q[i]-i);

        solve minimize sum(i in 1..n)(freq[i, q[i]]);
    '''

    # print(modelStr)
    model = minizinc.Model()
    model.add_string(modelStr)

    return model


def main():
    'The main function'

    n = 8
    solFreq = [0] * n * n
    for trial in range(100):
        model = getModel(n, solFreq)

        # Find the MiniZinc solver configuration for Gecode
        gecode = minizinc.Solver.lookup("gecode")

        # Create an Instance of the n-Queens model for Gecode
        instance = minizinc.Instance(gecode, model)

        result = instance.solve()['q']
        overlapScore = 0
        for row, col in enumerate(result):
            if solFreq[row * n + col-1]:
                overlapScore += solFreq[row * n + col-1]

            solFreq[row * n + col-1] += 1

        print(trial, result, overlapScore)


main()