N-Queens via Relaxation Labeling
Final project by
Introduction
The goal of the project was to solve the N-Queens problem (problem from the computer science world), by Relaxation labeling algorithm (taken from the vision world).
N-Queens problem is a NP-Complete problem.
Empirical observations of smaller-size problems show that the number of solutions increases exponentially with increasing N. Alternatively, search-based algorithms have been developed. For example, a backtracking search will systematically generate all possible solution sets for a given NªN board, different search heuristic methods, local search and conflict minimization techniques,some method from the area of neural networks, etc.
In this project we tried another method for solving the problem - Relaxation Labeling.
Approach and Method
Describe here how you addressed the problem, what observations or ideas you employed, what computational tools you used, etc...
It it could simplify the presentation, go ahead and use several subsections here, or split this section into
several sections.
Reduction of N-Queens to Relaxation labeling algorithm
Objects -> |
the queens, what means the algorithm will work with N objects. |
Labels -> |
assignments of queens.
The labels that will be choose by the algorithm, will determine does the problem has consistent solution.
|
Pi_0 -> |
for the first queen we choose the assignment randomly. This label will get the highest probability. All other queens will get some label (also randomly) that is consistent with the first queen.
|
R_ij -> |
this value between queen i and queen j, calculated accordingly to the given constraints for N-Queens problem.
|
A(p) -> |
the “stop” condition of the algorithm.
|
How do we decide what will be the assignment for the queens?
- For each queen we choose the best label.
- This label is the assignment this queen will get.
- Best label is chosen by maximal probability for each queen. In case that there are more than one label that got same probability, best label will be chosen randomly.
Queen's assignment by probability
How do we decide what will be the assignment for the queens?
For each queen we choose the best label. This label is the assignment this queen will get. Best label is chosen by maximal probability for each queen. In case that there are more than one label that got same probability, best label will be chosen randomly.
Simulator
- Can run the algorithm on different Ns.
- Can run “step by step” or “until convergence”.
- Show visual and textual results of each iteration.
- Can dome statistical calculations.
Results
We run the simulator on 100 programs for each N (from 4 to 15). This are our results:
- As N increases, the number of problems the algorithm solves decreases.
The main reason for this is different purpose of the two problems (will be explained in "Problems" part).
- As N increases, the time to converge (or solving) the problem increases also.
Problems
- Different purposes of two algorithms
N-Queens - find consistent solution. The algorithm should stop when it finds at least one consistent solution.
Relaxation Labeling - find some assignments of labels to objects, such that the solution will converge to max average local consistency.
This difference causes to the relaxation labeling algorithm to stop (when it converges) even if current assignment of labels to queens doesn't make consistent solution (in terms of N-Queens problem).
- In N-Queens problem, each object is affected by all other objects
In that case, the support for assignment of label to queen can be very high (if it consistent with most of the queens), even if it doesn't consistent with all the queens.
When the support is high, there is no reason for the relaxation labeling algorithm to change the probability for next iteration, and the problem can converge, but in terms of N-Queens the solution doesn't consistent.
- Many possibilities for equal values
Relaxation labeling algorithm don't handle this problem.
We solved this problem by using the random method (but maybe it's not the best method).
- Solution != Convergence
Solution of the problem doesn't means convergence for the relaxation labeling, so the algorithm will continue running, even if the solution was found.
- Random in C# - not really random.
Conclusions
- For make a decision if relaxation labeling algorithm is good for the N-Queens problem, many another experiments should be done.
- Relaxation labeling algorithm probably not the best choice algorithm for solving N-Queens problem.
Solving it with backtracking methods gave much better results.
But for being sure, many additional experiments are needed.
Additional Information
References
[1] On the Foundations of Relaxation Labeling Processes, by Hummel and Zucker 1983
[2] The N-Queens Problem
[3] Perceptual Organization (III), CS 202-1-5251, BGU, Ohad Ben-Shahar
[4] Demo for N-Queens by backtracking