Eight Queens Problem in Minizinc

There’s a few things that I’m really good at, and one of them is procrastination. I can find anything to do that will delay me getting inevitable tasks done. Today it’s because I have an exam tomorrow and still have a lot of studying that I should do for that. I have also been given a research task to do.

Instead of doing either of those tasks, I’ve knocked up a solution to the eight queens problem using the Minizinc constraints programming language. The eight queens problem simply is, how to arrange eight queens on a chessboard so that none of them are in check.

Not sure if it works correctly – did it in about two seconds flat – so bonus points if you can find problems with it.

include "globals.mzn";

array[1..8] of var 1..8: xpos;
array[1..8] of var 1..8: ypos;

%no two queens can have the same xvalue
constraint
    forall (i in 1..8) (
        forall (j in 1..8 where j!=i) (
            xpos[i] != xpos[j]
        )
    );

%no two queens can have the same yvalue
constraint
    forall (i in 1..8) (
        forall (j in 1..8 where j!=i) (
            ypos[i] != ypos[j]
        )
    );

%none on the diagonals
constraint
    forall (i in 1..8) (
        forall (j in 1..8 where j!=i) (
            (xpos[i] - xpos[j] != ypos[i] - ypos[j]) /\
            (xpos[i] - xpos[j] != ypos[j] - ypos[i]) /\
            (xpos[j] - xpos[i] != ypos[i] - ypos[j])
        )
    );

solve satisfy;

output [ "X: " ++ show(xpos[i]) ++ " " ++
         "Y: " ++ show(ypos[i]) ++ "\n" | i in 1..8 ];

The output that I get is:

X: 4 Y: 8
X: 2 Y: 7
X: 7 Y: 6
X: 3 Y: 5
X: 6 Y: 4
X: 8 Y: 3
X: 5 Y: 2
X: 1 Y: 1

Now to find something else to procrastinate with..

~ by jessiespaghetti on 22nd June, 2009.