This is a template method for the hill climbing algorithm. It doesn't guarantee that it will return the optimal solution. If the probability of success for a given initial random configuration is p the number of repetitions of the Hill Climbing algorithm should be at least 1/p. Note: generate_configuration() is not implemented yet but is quite easy to understand what it does.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | ```
def eight_queens():
"""
The famous 8Queens problem!
"""
repetitions = 100
best_val = min_val
best_conf = None
for i in range(repetitions):
A = generate_configuration()
b_A = hill_climbing(A)
v_b_A = value(b_A)
if value(b_A)< best_val:
best_val = v_b_A
best_conf=b_A
return best_conf
def sons(A):
"""
The sons of the configuration A for an 8Queen problem
is obtained reducing properly the space of the solutions.
In particular, the son is obtained changing the row index of
one of the queen. In total we have seven possible movement
among the column, therefore the number of sons will be 7x8=56.
"""
tmp_A = list(A)
N = len(A)
for i in range(N):
for r in range(7):
tmp_A = list(tmp_A)
q = tmp_A.pop(i)
tmp_A.insert(i, ((q[0]+1)%7, q[1]) )
yield tmp_A
raise StopIteration
def value(A):
"""
The heuristic for the 8Queen problem is this:
h(A) = number of attack that the queens have between each
other.
The data structure representation for the chessboard
will be a list of tuples each of them representing the
coordinates of a the position of a queen.
Complexity: O(N^2)
"""
N = len(A)
h=0
for i in range(N-1):
for j in range(i+1, N):
q1 = A[i]
q2 = A[j]
if q1[0] == q2[0]:
h+=1
elif q1[1] == q2[1]:
h+=1
elif q1[0]+q1[1] == q2[0]+q2[1]:
h+=1
elif q1[0]-q1[1] == q2[0]-q2[1]:
h+=1
return h
def hill_climbing(A):
"""
A represents a configuration of the problem.
It has to be passed as argument of the function sons(A)
ans value(A) that determines, respectively, the next
configuration starting from A where Hill Climbing Algorithm
needs to restart to evaluate and the heuristic function h.
This function represents a template method.
"""
best_val = sys.sizemax
best_conf = None
for conf in sons(A):
val = value(conf)
if best_val > val:
best_conf = conf
best_val = val
if best_conf > value(A):
return A
return hill_climbing(best_conf)
``` |

Hi,

thanks for the code! Helped me a lot.

I have one question: Not sure, but shouldn't the '<' sign in line 86 be relaced with a '>'? Because you have found a configuration that is better than the initial configuration A, so you want to go on using hill-climbing instead of returning the initial configuration. Also, you mixed up the variable names a bit in the end I think, but that just as a side note.

Thanks Robo! You are right, I did some mistakes there. Changed the recipe.

I am happy that this recipe helped you ;)

Line 7 references a value called "min_val", but it is never defined. And i have no clue what "generate_configuration()" is supposed to do.

Hi,

You are right. Indeed the purpose of this recipe is just to show the template function hill_climbing(A) which it can be applied for any kind of problem like the 8 Queen.

As mentioned from the recipe description the min_val variable and generate_configuration function depends on the way you define the data structure (array of list, matrix, etc) which is beyond the purpose of this recipe since I do not want to make a recipe sounds like a bible :)

Feel free to place a link of your solution here as additional reference.

Thanks

Hi - What is generate_configuration supposed to do? Create a list / array and randomly insert values? My generate_configuration generates a 2D array of 8 elements, for the row and col of each queen. Should it be random?