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.
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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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.
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
'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
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.
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.
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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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?
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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
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
ASKER