Link to home
Start Free TrialLog in
Avatar of xenoula
xenoula

asked on

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.

https://www.experts-exchange.com/questions/21810242/N-queens-algorithm-solved-with-simulated-annealing-algorithm.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.

SOLUTION
Avatar of nayernaguib
nayernaguib
Flag of Egypt image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of xenoula
xenoula

ASKER

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.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of xenoula

ASKER

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.


Avatar of xenoula

ASKER

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.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Avatar of ozo
ozo
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of xenoula

ASKER

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?
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of xenoula

ASKER

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