Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
N Queen problem
The classic N Queen problem was originally called the eight Queens puzzle and has its roots in chess. The task is to place eight queens on the board, and no two of them are a threat to each other. In other words, no two queens can be in the same row, column, or diagonal. In a nutshell, the N Queen problem uses an N×N board and N (where N>3) queens. For the original eight queens case, there are 92 solutions, eliminating the symmetric solution, there are 12 unique solutions. Using permutations, there are 4,426,165,368 possible ways to place 8 queens on an 8×8 board. However, if you create a candidate solution by ensuring that you don’t put two queens on the same row or column, the number of possible combinations is reduced to 8! = 403208! = 403208! = 40320.
Of solution of the
To solve the n-queen problem, use the following prerequisites: each row contains exactly one queen, and no two queens share the same column. This means that candidate solutions can be represented as an ordered list of integers or an index list, with each index representing the number of columns occupied by one of the queens in the current row. For example, in the four Queens problem on a 4×4 board, there is the following index list: (3, 2, 0, 1) represents (the index counts from 0) :
- In the first row, the queen is placed in the fourth column.
- In the second row, the queen is placed in the third column.
- In the third row, the queen is placed in the first column.
- In the fourth row, the queen is placed in the second column.
The following figure depicts the above indexes:
Indexes (1, 3, 0, 2) can be used to represent the following figure:
The only possible violation of the constraint among the candidate solutions represented in this way is the shared diagonal between a pair of queens. For example, in the first candidate solution:
This means that when evaluating solutions represented in this way, you only need to look up and calculate the shared diagonals between the positions they represent.
Representation of the problem
To encapsulate the N-Queens problem, create a Python class called NQueensProblem. Initialize the class with the required problem size and provide the following public methods:
- GetViolationsCount (Positions) : Counts the number of times a given solution violates a constraint
- PlotBoard (Positions) : Draws queens on the board based on a given solution
Pawn pictures
Import the necessary libraries
import numpy as np
import matplotlib as mpl
from matplotlib import pyplot as plt
class NQueensProblem:
""N Queen problem definition ""
def __init__(self,numOfQueens) :
self.numOfQueens = numOfQueens
def __len__(self) :
""" :return: the number of queens """
return self.numOfQueens
def getViolationsCount(self,positions) :
Since each row of the input contains a unique column index, it is impossible for a row or column to violate a constraint. Only the diagonal requires counting the number of violations. "" "
if len(positions) ! = self.numOfQueens:raise ValueError("size of positions list should be equal to ", self.numOfQueens)
violations = 0
# Walk through each pair of queens and calculate if they are on the same diagonal:
for i in range(len(positions)):
for j in range(i + 1.len(positions)):
#first queen in pair
column1 = i
row1 = positions[i]
#second queen in pair
column2 = j
row2 = positions[j]
if abs(column1 - column2) == abs(row1 - row2):
violations += 1
return violations
def plotBoard(self,positions) :
""" Draws the position of the queen on the board based on the given solution. """
if len(positions) ! = self.numOfQueens:raise ValueError("size of positions list must be equal to ",self.numOfQueens)
fig,ax = plt.subplots()
# board definition:
board = np.zeros((self.numOfQueens,self.numOfQueens))
# alternate checkerboard colors
board[::2.1: :2] = 1
board[1: :2. : :2] = 1
# draw checkerboard
ax.imshow(board,interpolation='none',cmap=mpl.colors.ListedColormap(['#ffc794'.'#4c2f27']))
# Read the chess picture and scale it
queenThumbnail = plt.imread("queen-thumbnail.png")
thumbnailSpread = 0.70 * np.array([-1.1, -1.1) /2
# Chess drawing
for i,j in enumerate(positions):
# Place the pieces on the board
ax.imshow(queenThumbnail,extent=[j,j,i,i]+thumbnailSpread)
# Coordinate axis Settings
ax.set(xticks=list(range(self.numOfQueens)),yticks=list(range(self.numOfQueens)))
ax.axis('image')
return plt
Copy the codeGenetic algorithm to solve N queen problem
Constant and genetic operator definitions
- Import the required libraries
from deap import base
from deap import creator
from deap import tools
from deap import algorithms
import random
import array
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
Copy the code- Constants defined
# 16 queen
NUM_OF_QUEENS = 16
# Number of individuals in a population
POPULATION_SIZE = 300
# Maximum generation
MAX_GENERATIONS = 100
# Crossover probability
P_CROSSOVER = 0.9
# Mutation probability
P_MUTATION = 0.1
Copy the code- First create an instance of the NQueensProblem class with the size of the problem to be solved:
nQueens = NQueensProblem(NUM_OF_QUEENS)
Copy the code- Since the goal is to minimize the number of violations (with an expected value of 0), the minimum applicability policy is defined:
creator.create("FitnessMin",base.Fitness,weights=(-1.0)),Copy the code- Defining individual classes
creator.create("Individual",array.array,typecode='i',fitness=creator.FitnessMin)
Copy the code- Since the solution is represented by an ordered list of integers, each representing the queen’s column position, the following definition is used to create the initial population:
toolbox = base.Toolbox()
toolbox.register("randomOrder",random.sample,range(len(nQueens)),len(nQueens))
toolbox.register("individualCreator",tools.initIterate,creator.Individual,toolbox.randomOrder)
toolbox.register("populationCreator",tools.initRepeat,list,toolbox.individualCreator)
Copy the code- Set the fitness function to count the number of violations caused by the queen’s placement on the board:
def getViolationCount(individual) :
return nQueens.getViolationsCount(individual),
toolbox.register("evaluate",getViolationCount)
Copy the code- Defining genetic operator
toolbox.register("select",tools.selTournament,tournsize=2)
toolbox.register("mate",tools.cxUniformPartialyMatched,indpb=2.0/len(nQueens))
toolbox.register("mutate",tools.mutShuffleIndexes,indpb=1.0/len(nQueens))
Copy the codeUse elitist tactics
The use of the HallOfFame can be used to preserve the best individuals that have ever existed in an evolutionary population without losing them due to selection, crossover, or variation. The HallOfFame class is implemented in the tools module. Use the Halloffame object for elitism. Individuals contained in the Halloffame object are injected directly into the next generation and are not affected by genetic operators of selection, crossover, and mutation
# Number of Hall of Famers
HALL_OF_FAME_SIZE = 30
def eaSimpleWithElitism(population,
toolbox,
cxpb,
mutpb,
ngen,
stats=None,
halloffame=None,
verbose=__debug__) :
"" Use Halloffame to implement the elite mechanic. Individuals contained in the Hall of Fame mic are injected directly into the next generation and are not affected by genetic operators of selection, crossover and mutation. "" "! [20210102211924929.png](https://p1-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/7ee61b0b0bb747499b5b3f8fe003abe1~tplv-k3u1fbpfcp-watermark.image? ) logbook = tools.Logbook()# Used to monitor algorithm performance, and statistics
logbook.header = ['gen'.'nevals'] + (stats.fields if stats else [])
# Calculate individual fitness
invalid_ind = [ind for ind in population if not ind.fitness.valid]
fitnesses = toolbox.map(toolbox.evaluate,invalid_ind)
for ind,fit in zip(invalid_ind,fitnesses):
ind.fitness.values = fit
if halloffame is None:
raise ValueError("halloffame parameter must not be empty!")
# Update Hall of Fame members
halloffame.update(population)
hof_size = len(halloffame.items) if halloffame.items else 0
record = stats.compile(population) if stats else {}
logbook.record(gen=0,nevals=len(invalid_ind),**record)
if verbose:
print(logbook.stream)
# Start the genetic process
for gen in range(1,ngen + 1) :# Number of selected individuals = number of individuals in the population - Number of Hall of Famers
offspring = toolbox.select(population,len(population) - hof_size)
# Population renewal to the next generation
offspring = algorithms.varAnd(offspring,toolbox,cxpb,mutpb)
# Calculate individual fitness
invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = toolbox.map(toolbox.evaluate,invalid_ind)
for ind,fit in zip(invalid_ind,fitnesses):
ind.fitness.values = fit
# Add hall of Famers to the current generation
offspring.extend(halloffame.items)
# Update the Hall of Fame
halloffame.update(offspring)
Use current instead to swap populations
population[:] = offspring
Append current statistics to the log
record = stats.compile(population) if stats else {}
logbook.record(gen=gen,nevals=len(invalid_ind),**record)
if verbose:
print(logbook.stream)
return population,logbook
Copy the codeGenetic process
Use the main function to complete the genetic flow
def main() :
Create an initial population
population = toolbox.populationCreator(n=POPULATION_SIZE)
Register statistics to listen on
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min",np.min)
stats.register("avg",np.mean)
# instance alias person hall object
hof = tools.HallOfFame(HALL_OF_FAME_SIZE)
Run the genetic algorithm
population,logbook = eaSimpleWithElitism(population,
toolbox,
cxpb=P_CROSSOVER,
mutpb=P_MUTATION,
ngen=MAX_GENERATIONS,
stats=stats,
halloffame=hof,
verbose=True)
# Print Hall of Famer
print("- Best solutions are:")
for i in range(HALL_OF_FAME_SIZE):
print(i,":",hof.items[i].fitness.values[0]."- >",hof.items[i])
# Draw statistical results
minFitnessValues,meanFitnessValues = logbook.select("min"."avg")
plt.figure(1)
sns.set_style("whitegrid")
plt.plot(minFitnessValues,color='red')
plt.plot(meanFitnessValues,color='green')
plt.xlabel('Generation')
plt.ylabel('Min / Average Fitness')
plt.title('Min and Average fitness over Generations')
# Draw the best solution
sns.set_style("whitegrid", {'axes.grid' : False})
nQueens.plotBoard(hof.items[0])
# Draw result display
plt.show()
Copy the codeThe results of
run
if __name__ == "__main__":
main()
Copy the codeA printout of the Hall of Famers can be seen:
- Best solutions are:
0 : 0.0 -> Individual('i'[12.9.3.1.13.11.5.14.0.6.10.7.2.15.8.4])
1 : 0.0 -> Individual('i'[10.12.1.9.2.6.8.15.11.0.14.7.4.13.3.5])
2 : 0.0 -> Individual('i'[10.12.1.9.2.6.8.14.11.0.15.7.4.13.3.5])
3 : 0.0 -> Individual('i'[1.12.10.7.2.0.5.14.11.6.15.13.4.9.3.8])...29 : 1.0 -> Individual('i'[9.14.4.10.12.0.5.1.11.15.2.7.8.13.3.6])
Copy the codeDraw the best solution:
Minimum fitness and average fitness changes:
