Overview The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. thus, a solution requires that no two queens share the same row, column, or diagonal.

Project Structure

├── model
│ ├── State.py
├── solvers
│ ├── CSP.py
│ ├── Genetic Algorithm.py
│ ├── HillClimbing.py
│ ├── KBeam.py
├── test
│ ├──Sample_Input.txt
├── utils
│ ├──Reader
└── Main.py

Models and Utils

Reader :
Use it to read sample input file to get initalBoard.we can represent a 8-queen sol in a 2 dimension list filled with 0 and then, fill it with 8 ones representing the position of the queen. A better and simpler representation is that a list of length 8. Each index specifies a column of the board. The value of each index is between 0 and 7 representing the the row of a queen in a column.

State:
Take the board as we described in Reader and holding all required info about the board like he cost of this board by using two methods:

Algorithms

• Hill Climbing
  Start : Looping on all cells and compute cost in each one then select the best solution.
  Restart: change the initial state in case of algorithm stucks in local optima .

• K-Beam
  GenerateBoards: generate k random boards.
  selectTheBest: get the best K solutions.
  Addsolutions: add the best solutions of each successor.

• Genetic Algorithm
  InitializeEnvironment: get P random solutions where P is the population size.
  checkGoal: check if the solution with cost equals zero exists in the environment.
  Crossover: make the crossover operation between two chromosomes.
  Mutation : using many approaches for mutation and select one of them randomly.
  updateEnvironment: set the environment to the new chromosomes.

• CSP
  initialDomains: create the valid domain for each variable.
  updateDomains: after assignment of any variable we need to update the domains of neighbours.
  isDanger: if our path may lead to wrong answer.
  updateVisits: to track the visited nodes after each assignment.
  Allvisited: check if all successors of this node is visited or not.
  Choice: choose the assignment that may not lead to the wrong answer.

Sample runs

• Hill Climbing

To start Hill climbing algorithms we need to set parameters hc = HC(initialSate,Dimension,False) #using initial State, Dimension of board,to restart algorithm till solve set True

• K-Beam

To start K-Beam algorithm we need 2 values k = Beam(K,Dimension) #parameters: value of K, Dimension of board (Hint:random start) Start algorithm with K=8 and Dimension = 8

• Genetic Algorithm

To start genetic algorithm ga = GA(500,Dimension,3) #parameters: population size , Dimension of board, crossover (Hint:random start)

Start algorithm with population size =500 and Dimension = 8 and crossover =3

• CSP

To start CSP we just need to pass Dimension csp = Backtracking(Dimension)#parameters: Dimension of board (Hint:random start)

Notes

• Green queen means this queen is not attacking any other queen
• In genetic algorithms it may stuck because mutation doesn’t provide new solution we tried to solve this problem by adding many approaches for mutation and select one randomly. In K-Beam algorithm for K>100 it may lead to a solution.