Click here to run the configurator





HOW TO GIVE PREFERENCES

The problem is the 9-queen problem, where each cell in the 9x9 board can have a certain preference value, indicating how much we like that a solution contains a queen in that cell. Preferences can also be associated to the constraints (vertical or diagonal), indicating how important it is that such constraints are satisfied.

Preferences are values between 0 and 1. They are combined using the min operator and are totally ordered, in a way that the higher values indicate a better preference. Thus, the goal of the problem is to maximize the minimum preference (fuzzy constraint solving).

To give preferences on a cell, you can press on it with the middle- mouse button; a menu with 11 values (from 0 to 1) will appear, and you can choose the desired preference value by clicking on one of those values. Changes can be made by re-clicking with the middle-mouse buttons over the same cell. The higher the preference is, the more important it is that the solution contains a queen in that cell. If you don't put any preference on a cell, the default value is 1 (the maximum value).

To give preferences to the constraints, you can press on the "Diagonal ur-bl" (that refers to the constraint over the diagonal from up-right to bottom-left), "Diagonal ul-br" (from up-left to bottom-right) and "Vertical" buttons and make your choices as before. The meaning of these preferences is that the higher the value is, the more important it is that the constraint is not violated. If you don't put any preference on a constraint, the default value is 1: it means that the violation of this constraint is not allowed, that is, it is a hard constraint. The configurator calculates the preference of each constraint between every two cells, in such a way that the importance of the constraint decreases when two cells are farther away from each other.

NEW

By clicking the "New" button, you start a new run of the configurator.

INITIAL AC

"AC" means Arc Consistency: once you have given the preferences on cells and constraints and before putting the first queen, you must click on this button: the configurator performs fuzzy arc consistency and shows the results on the chessboard, by showing the new preference value in each cell. It is necessary to click this button, because it may modify the initial preferences given by the user.

UB SOLUTION

"UB" means Upper Bound: when you click on this button (it can be done at anytime), each cell contains an upper bound to the value of all solutions that contain a queen in this cell, besides all other already positioned queens.

DELETIONS

When the user clicks on this button, the configurator shows on each cell how many cells will be deleted if he puts the next queen on that cell. A cell will be deleted if its preference becomes zero after applying AC.

QUEEN POSITIONING

To position a queen in a cell, it is enough to click on that cell with the left mouse button. If the selected cell is in a row where a queen has already been positioned, the queen is moved to the new position. After a queen is positioned, AC is automatically performed.

STEP BACK

By clicking on this button the user can undo the last positioning step.

OPTIMIZATION

Once a solution is found, not always it is the optimal solution. If the solution just found is optimal, a message will appear under the chessboard telling you the value of the solution. Otherwise, by clicking on the ''Optimization'' button, the system will start a new configuration problem that has the preferences of the previous problems but allows only for better solutions.

EXPLANATIONS

If the user wants to know the history of the preferences of a cell, it's enough to click on this cell with the right mouse button. The explanation, in the form of a list of preference lowerings, together with the causes for such changes, will appear in the area under the chessboard and, in the form of a tree, in the area on the left. The cause for a decrease of a preference value is always a previous queen positioning.