N-Queens via Relaxation Labeling

Final project by

Ilana Koreh & Luba Rashkovsky


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?

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

Results

We run the simulator on 100 programs for each N (from 4 to 15). This are our results:

Problems

Conclusions

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