KNIGHT’S TOUR PROBLEM USING GENETIC ALGORITHM

In the Knight's Tour problem, the knight is a piece in chess that usually looks like a horse and moves in an
L-shaped pattern. This means it will first move two squares in one direction and then one square in a
perpendicular direction. There exists multiple algorithms to solve this problem such as Brute Force
(Backtracking), Warnsdorff's Rule, Graph Theory (Hamiltonian Cycle), Neural Networks, Genetic
Algorithms etc.

Problem statement

The project focuses on determining the minimal number of chess knights necessary to attack every square
on an 8x8 chessboard. The approach involves implementing a genetic algorithm to find an optimized
solution to this problem.

Probable approach

The genetic algorithm is employed to evolve a population of potential solutions over several generations.
The following key components are implemented:

Population Initialization:

A population of candidate solutions is generated randomly.

Fitness Function:

The fitness of each solution is evaluated based on the number of knights required to
cover all squares on the chessboard. The fitness function assesses each individual's ability to cover all
squares on the chessboard with minimal knights. It takes into account the number of knights required and
their positioning.

Crossover Operation:

Two parent solutions are selected based on their fitness, and crossover is applied to
create new solutions.

Mutation Operation:

Random mutations are introduced to maintain genetic diversity in the population.

Selection:

Parents for the next generation are selected based on their fitness, with a bias towards individuals
with higher fitness scores.

Results:

The genetic algorithm is executed for a specified number of generations. The best solution, along
with its fitness score, is identified.