This demo shows finite domain constraints and search to solve the -Queens problem: how to place -Queens on a $n\times n$ chess-board such that the queens do not attack each other.

The problem is solved with finite domain constraints, for a discussion see Section 5.1 of ``Finite Domain Constraint Programming in Oz. A Tutorial.''. The demo visualizes constraint propagation and different distribution heuristics.

Note that the size of the board as well as the following heuristics to place a queen can be selected:

Brute Force: Try fields in a top-down, left-right fashion.
First Fail: Choose the row with the least remaining possibilities first, and place the queen leftmost in this row.
Middle Out: Choose the row as above, where rows near to the center of the board are preferred. Place the queen in the middle of this row.
Up First: Choose the row with the least remaining possibilities first, where rows where it is possible to place the queen left most are chosen first. Place the queen left most.

Implementation

Root functor: AnimateQueens.oz

1 Animated Queens

Christian Schulte

Implementation