• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1141
  • Last Modified:

N queens problem with simulated annealing algorithm solution

I have asked in the previous question the data structure I will follow for solving the N Queens problem.
Here is my previous question about N -queens  algorithm.

http://www.experts-exchange.com/Programming/Q_21810242.html 
and
http://www.experts-exchange.com/Programming/Q_21811122.html

It is better to read it first to understand this question.

I want to ask how can i now move the queens randomly according to the number of conflicts they have?
The bigger the number of conflicts the bigger probability to move further. The queens are also restricted in the N x N space.
I don't want to follow a hill climbing approach but a simulated annealing algorithm where in the beginning i will have big probability to accept bad soution .
0
xenoula
Asked:
xenoula
1 Solution
 
ozoCommented:
A typical simulated annealing algorithm would try a move to a random neighbouring state,
(you might consider neighbouring state to be a move of one queen by one space, or moving one queen to any other space, or moving one queen horizonally, or moving any number of queens by one space.  It could help if you can define your neighborhood such that good solutions tend to be close to other good solutions)
and reject that move if e^-D/T > (random number between 0 and 1) where D is the change in energy and T is the temperature.
0
 
xenoulaAuthor Commented:
I have as valid positions the queens to move in the same column so i eliminate big proportion of the state space .
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now