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

N queens algorithm with simulated annealing algorithm

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 
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.

0
xenoula
Asked:
xenoula
  • 6
  • 5
7 Solutions
 
nayernaguibCommented:
In my openion, this will not be the most effective heuristic for solving the N-queens problem.

I think one possible heuristic would be to move the queen having the largest number of conflicts to a square in the same column where the number of conflicts would be minimum. Eventually, you will reach a solution.

_______________

  Nayer Naguib
0
 
xenoulaAuthor Commented:
Yes maybe this is a better heuristic to solve the problem. But also i can incorporate this heuristic in the simulated annealing algorithm. Not to move the queens randomly but  according this pattern where i would have minimum conflicts.
0
 
nayernaguibCommented:
Sorry! Forgot to mention that for the heuristic above to work correctly, your initial state should contain only one queen randomly placed in each column.

_______________

  Nayer Naguib
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
xenoulaAuthor Commented:
Yes my code places randomly the queen in the board.

sub Fill_queens_the_board()
' these is the procedure to place randomly the queens

'I want to put the queens randomly in the board
Dim i As Integer, j As Integer, n As Integer
Dim Random As Double, Random2 As Double
Dim flag As Boolean

For n = 1 To Dimen
    Do
                        Random = Rnd()
                        Random2 = Rnd()
                        'these are the row and the columns which are taken randomly
                         i = Int(Random * Upper_Of_rows) + 1
                         j = Int(Random2 * Upper_Of_rows) + 1
                  'in this if statement the array i check if the cell is placed another queen
                   If (Array1(i, j) = 0) Then
                          Array1(i, j) = n
                          flag = True
                          'The Queens ( n,3) are the main data structure for keeping information about each queen
                         
                          Queens(n, 1) = i
                          Queens(n, 2) = j
                                                   
                    Else
                   
                          flag = False
                         
                    End If
       Loop Until flag = True
       
'                 Next
'         Next
 Next

End Sub
------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------
Function Objective_function() As Double
'this is the objective function. I will calculate every time this function to find out if i have improvement
Dim Conflicts As Integer, i As Integer, j As Integer
Conflicts = 0


For i = 1 To Dimen
    For j = i + 1 To Dimen
     
'    If (3 = 3) Then
   
    If (Queens(i, 1) = Queens(j, 1) _
            Or Queens(i, 2) = Queens(j, 2) _
            Or (Abs(Queens(i, 1) - Queens(j, 1)) = Abs(Queens(i, 2) - Queens(j, 2))) _
        ) Then
   
    Conflicts = Conflicts + 1
    End If
       
    Next
   
Next


Objective_function = Conflicts

End Function
------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------

Sub find_the_conflicts_for_all_Queen()
'This sub i calculate for each  individual queen the conflicts and i store it to Queens(n, 3)
Dim Conflicts As Integer
Dim i As Integer, q1 As Integer, q2 As Integer, n As Integer


For n = 1 To Dimen
   
    Conflicts = -1
    q1 = Queens(n, 1)
    q2 = Queens(n, 2)
   
            For i = 1 To Dimen
           '    If (3 = 3) Then
           
            If (Queens(i, 1) = q1 _
                    Or Queens(i, 2) = q2 _
                    Or (Abs(Queens(i, 1) - q1) = Abs(Queens(i, 2) - q2)) _
                ) Then
           
            Conflicts = Conflicts + 1
            End If
             
                       
            Next
'here i insert in the code the number of the conflicts  each queen  has
'I will use it that for moving the queens in the board
           
            Queens(n, 3) = Conflicts
           
   
   
Next

End Sub
------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------

What i want to write is movements of the queens in each stage.
I want to move the Queens that have Queens(n,3)>0.--Queens(n,3)=number of conflicts for the n queen
and to move  more the queens that have Queens(n,3) bigger than the others

and then i will use the simulated annealing algorithm to decide which stage was the best and how to proceed to the next stage.


0
 
xenoulaAuthor Commented:
My code places totaly random the queens in the board.
Maybe it will be much faster to place only one queen in the row. This is an improvement but Now i want just to run the algorithm.
0
 
nayernaguibCommented:
I've been trying different heuristic functions for quite some time (actually a couple of hours). :-)

Here are the results:

1. If you randomly move *all* queens causing conflict during each state transition (whether you will randomly move them, or will move each queen according to the number of conflicts it has got), then the probability of reaching a solution is the same as the probability of reaching a solution while generating the initial state!! The total number of conflicts does *not* converge to zero.
You might keep waiting for days. :-)

2. Trying to move only the most annoying queen gives slightly better results (I tried different next-state generation approaches). The total number of conflicts quickly converges, but then gets stuck at low values. Less than 5% of the runs successfully generated a solution after iterating for only tens or few hundreds of times.

I can post you Visual Basic code that works either way. However, I strongly recommend that you consider other possible heuristic functions.

_______________

  Nayer Naguib
0
 
ozoCommented:
For simulated annealing, the probaility of moving a queen would depend on how much better or worse the conflicts get when it is moved.  
You start at a high temperature which makes lots of different movements possible, and gradually lower the temperature to make moves that make the conflicts worse less and less likely.

For this particular problem, I'd expect simulated annealing to be slower on average than a systematic search.
0
 
xenoulaAuthor Commented:
Ozo you are right for the algorithm. maybe The contraint programming would be better for that type of problem. i dont want to do the fastest algorithm I want just to have good results.


nayernaguib thank you very much . What size space have you tried for the program? I have seen simulated annealing and it is very fast in 8x8  board.Maybe you must have more steps per temeprature. for the 8x8 it usually needs 600-700 moves to find the right. But it doesn't always find a solution.can you post me the solution?
0
 
nayernaguibCommented:
Here's the code. I found the pieces of code that caused my algorithm to get stuck. Now, a solution is found in a few tens or hundreds of iterations:

First, this modified Objective_function() calculates the conflicts for each queen as a side effect. Now you do not need to call find_the_conflicts_for_all_Queen(). This should be more efficient:

_______________________________________

Function Objective_function() As Double
Dim conflicts As Integer, i As Integer, j As Integer
conflicts = 0
For i = 1 To Upper_Of_rows
  Queens(i, 3) = 0
Next
For i = 1 To Upper_Of_rows
    For j = 1 To Upper_Of_rows
        If (i <> j) And ((Queens(i, 1) = Queens(j, 1) _
            Or Queens(i, 2) = Queens(j, 2) _
            Or (Abs(Queens(i, 1) - Queens(j, 1)) = Abs(Queens(i, 2) - Queens(j, 2))))) Then
                conflicts = conflicts + 1
                Queens(i, 3) = Queens(i, 3) + 1
                Queens(j, 3) = Queens(j, 3) + 1
        End If
    Next
Next
For i = 1 To Upper_Of_rows
  Queens(i, 3) = Queens(i, 3) / 2 'as each conflict gets added twice for each queen
Next
Objective_function = conflicts
End Function

_______________________________________

Second, this function randomly moves the most "annoying" queen (that has got most conflicts). The similar() array is filled and used to avoid sticking to only one queen when there are other queens having the maximum number of conflicts. Before using this array, almost all of the algorithm runs got into a deadlock.

_______________________________________

Private Sub MoveMostAnnoyingQueen()
    Dim index As Integer, max As Integer
    Dim oldi As Integer, oldj As Integer
    Dim i As Integer, j As Integer
    Dim newconflicts As Integer
    Dim similarconflicts As Integer
    Dim similar() As Integer
    max = 0
    similarconflicts = 1
    For i = 1 To Upper_Of_rows
      If Queens(i, 3) > max Then
        index = i
        similarconflicts = 1
        max = Queens(i, 3)
      ElseIf Queens(i, 3) = max Then
        similarconflicts = similarconflicts + 1
      End If
    Next
    index = 1
    ReDim similar(similarconflicts)
    For i = 1 To Upper_Of_rows
      If Queens(i, 3) = max Then
        similar(index) = i
        index = index + 1
      End If
    Next
    index = similar(Int(Rnd * similarconflicts) + 1)
    oldi = Queens(index, 1)
    oldj = Queens(index, 2)
    newconflicts = Objective_function
    Do
      i = oldi + Sgn(Int(Rnd * 3) - 1) * (Int(Rnd * max) + 1) 'try different parameters here
      j = oldj + Sgn(Int(Rnd * 3) - 1) * (Int(Rnd * max) + 1) 'here too
    Loop Until IsBetterPosition(oldi, oldj, index, i, j, newconflicts)
End Sub

_______________________________________

Finally, this function tells whether the newly generated position is a better one. After a certain number of tries, the function accepts the new position (also to avoid deadlocks).

_______________________________________

Private Function IsBetterPosition(oldi As Integer, oldj As Integer, index As Integer, i As Integer, j As Integer, oldconflicts)
Dim newconflicts As Integer
If (i < 1) Or (i > Upper_Of_rows) Or (j < 1) Or (j > Upper_Of_rows) Then
  IsBetterPosition = False
ElseIf Array1(i, j) <> 0 Then
  IsBetterPosition = False
Else
  Array1(i, j) = Array1(oldi, oldj)
  Array1(oldi, oldj) = 0
  Queens(index, 1) = i
  Queens(index, 2) = j
  newconflicts = Objective_function
  If newconflicts <= oldconflicts Or NumberOfTries > Upper_Of_rows Then 'also try different boundary values for NumberOfTries
    NumberOfTries = 0
    IsBetterPosition = True
  Else
    NumberOfTries = NumberOfTries + 1
    Array1(oldi, oldj) = Array1(i, j)
    Array1(i, j) = 0
    Queens(index, 1) = oldi
    Queens(index, 2) = oldj
    IsBetterPosition = False
  End If
End If
End Function

_______________________________________

Notes:
* Don't forget to declare NumberOfTries as a global integer variable.
* You can use a global variable to count iterations.
* In your code, Dimen and Upper_Of_rows have the same value, so you can remove one of them and use the other.

_______________

  Nayer Naguib
0
 
nayernaguibCommented:
Hint: Graphically visualizing the progress of the algorith was of great help to me in identifying the deadlocks.

_______________

  Nayer Naguib
0
 
nayernaguibCommented:
Forgot to mention that Objective_function() should be called each time *before* calling MoveMostAnnoyingQueen().
Your initialization code should look like this:

____________________________________

NumberOfTries = 0
iterations = 0
Randomize
Dim s As String
Upper_Of_rows = 8
ReDim Array1(1 To Upper_Of_rows, 1 To Upper_Of_rows) 'you can use only one array instead of both Queens() and Array1()
ReDim Queens(1 To Upper_Of_rows, 1 To 3) 'but this will require doing some modifications to the code
Fill_queens_the_board

____________________________________

And the code that runs the algorithm should look like this:

____________________________________

If Objective_function = 0 Then
  MsgBox "solution found after " & iterations & " iterations"
  Exit Sub
End If
Do
  iterations = iterations + 1
  MoveMostAnnoyingQueen
Loop Until Objective_function = 0
ShowBoard 'if you have some visualization function
MsgBox "solution found after " & iterations & " iterations"

____________________________________

_______________

  Nayer Naguib
0
 
xenoulaAuthor Commented:
Nayer Naguib
Very good fantastic. You are correct about the most annoying queen. if i move every queen random then i will have a dead end.
furthermore your objective function is more compact and efficient.  

I think that you code could be describe as hill climbing because you try to find the best solution but you are right about this kind of problem . I will write the simulated annealing algorithm and post my code.

I will closed this question and open a new one with the same question  to give more points
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

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