A Python project for optimizing the 8 Queens Puzzle using the Genetic Algorithm implemented in PyGAD.

Overview

8QueensGenetic

A Python project for optimizing the 8 Queens Puzzle using the Genetic Algorithm implemented in PyGAD.

The project uses the Kivy cross-platform Python framework for building the GUI of the 8 queens puzzle. The GUI helps to visualize the solutions reached while the genetic algorithm (GA) is optimizing the problem to find the best solution.

For implementing the genetic algorithm, the PyGAD library is used. Check its documentation here: https://pygad.readthedocs.io

IMPORTANT If you are coming for the code of the tutorial 8 Queen Puzzle Optimization Using a Genetic Algorithm in Python, then it has been moved to the TutorialProject directory on 17 June 2020.

PyGAD Installation

To install PyGAD, simply use pip to download and install the library from PyPI (Python Package Index). The library lives a PyPI at this page https://pypi.org/project/pygad.

For Windows, issue the following command:

pip install pygad

For Linux and Mac, replace pip by use pip3 because the library only supports Python 3.

pip3 install pygad

PyGAD is developed in Python 3.7.3 and depends on NumPy for creating and manipulating arrays and Matplotlib for creating figures. The exact NumPy version used in developing PyGAD is 1.16.4. For Matplotlib, the version is 3.1.0.

Project GUI

The project comes with a GUI built in Kivy, a cross-platform Python framework for building natural user interfaces. Before using the project, install Kivy:

pip install kivy

Because the project is built using Python 3, use pip3 instead of pip for Mac/Linux:

pip3 install kivy

Check this Stackoverflow answer to install other libraries that are essential to run Kivy: https://stackoverflow.com/a/44220712

The main file for this project is called main.py which holds the code for building the GUI and instantiating PyGAD for running the genetic algorithm.

After running the main.py file successfully, the window will appear as given in the figure below. The GUI uses a GridLayout for creating an 8x8 grid. This grid represents the board of the 8 queen puzzle.

main

The objective of the GA is to find the best locations for the 8 queens so that no queen is attacking another horizontally, vertically, or diagonally. This project assumes that no 2 queens are in the same row. As a result, we are sure that no 2 queens will attack each other horizontally. This leaves us to the 2 other types of attacks (vertically and diagonally).

The bottom part of the window has 3 Button widgets and 1 Label widget. From left to right, the description of the 3 Button widgets is as follows:

  • The Initial Population button creates the initial population of the GA.
  • The Show Best Solution button shows the best solution in the last generation the GA stopped at.
  • The Start GA button starts the GA iterations/generations.

The Label widget just prints some informational messages to the user. For example, it prints the fitness value of the best solution when the user presses the Show Best Solution button.

Steps to Use the Project

Follow these steps to use the project:

  1. Run the main.py file.
  2. Press the Initial Population Button.
  3. Press the Start GA Button.

After pressing the Start GA button, the GA uses the initial population and evolves its solutions until reaching the best possible solution.

Behind the scenes, some important stuff was built that includes building the Kivy GUI, instantiating PyGAD, preparing the the fitness function, preparing the callback function, and more. For more information, please check the tutorial titled 8 Queen Puzzle Optimization Using a Genetic Algorithm in Python.

6 Attacks

After running the main.py file and pressing the Initial Population button, the next figure shows one possible initial population in which 6 out of 8 queens are attacking each other.

1  6 attacks

In the Label, the fitness value is calculated as 1.0/number of attacks. In this case, the fitness value is equal to 1.0/6.0 which is 0.1667.

The next figures shows how the GA evolves the solutions until reaching the best solution in which 0 attacks exists.

5 Attacks

2  5 attacks

4 Attacks

3  4 attacks

3 Attacks

4  3 attacks

2 Attacks

5  2 attacks

1 Attack

6  1 attack

0 Attacks (Optimal Solution)

7  0 attack

IMPORTANT

It is very important to note that the GA does not guarantee reaching the optimal solution each time it works. You can make changes in the number of solutions per population, the number of generations, or the number of mutations. Other than doing that, the initial population might also be another factor for not reaching the optimal solution for a given trial.

For More Information

There are different resources that can be used to get started with the building CNN and its Python implementation.

Tutorial: 8 Queen Puzzle Optimization Using a Genetic Algorithm in Python

In 1 May 2019, I wrote a tutorial discussing this project. The tutorial is titled 8 Queen Puzzle Optimization Using a Genetic Algorithm in Python which is published at Heartbeat. Check it at these links:

Tutorial Cover Image

Book: Practical Computer Vision Applications Using Deep Learning with CNNs

You can also check my book cited as Ahmed Fawzy Gad 'Practical Computer Vision Applications Using Deep Learning with CNNs'. Dec. 2018, Apress, 978-1-4842-4167-7 which discusses neural networks, convolutional neural networks, deep learning, genetic algorithm, and more.

Find the book at these links:

Fig04

Citing PyGAD - Bibtex Formatted Citation

If you used PyGAD, please consider adding a citation to the following paper about PyGAD:

@misc{gad2021pygad,
      title={PyGAD: An Intuitive Genetic Algorithm Python Library}, 
      author={Ahmed Fawzy Gad},
      year={2021},
      eprint={2106.06158},
      archivePrefix={arXiv},
      primaryClass={cs.NE}
}

Contact Us

Owner
Ahmed Gad
Ph.D. Student at uOttawa // Machine Learning Researcher & Technical Author https://amazon.com/author/ahmedgad
Ahmed Gad
This project is an implementation of a simple K-means algorithm

Simple-Kmeans-Clustering-Algorithm Abstract K-means is a centroid-based algorithm, or a distance-based algorithm, where we calculate the distances to

Saman Khamesian 7 Aug 09, 2022
Algorithmic virtual trading using the neostox platform

Documentation Neostox doesnt have an API Support, so this is a little selenium code to automate strategies How to use Clone this repository and then m

Abhishek Mittal 3 Jul 20, 2022
Policy Gradient Algorithms (One Step Actor Critic & PPO) from scratch using Numpy

Policy Gradient Algorithms From Scratch (NumPy) This repository showcases two policy gradient algorithms (One Step Actor Critic and Proximal Policy Op

1 Jan 17, 2022
HashDB is a community-sourced library of hashing algorithms used in malware.

HashDB HashDB is a community-sourced library of hashing algorithms used in malware. How To Use HashDB HashDB can be used as a stand alone hashing libr

OALabs 216 Jan 06, 2023
My own Unicode compression algorithm

Zee Code ZCode is a custom compression algorithm I originally developed for a competition held for the Spring 2019 Datastructures and Algorithms cours

Vahid Zehtab 2 Oct 20, 2021
An open source algorithm and dataset for finding poop in pictures.

The shitspotter module is where I will be work on the "shitspotter" poop-detection algorithm and dataset. The primary goal of this work is to allow for the creation of a phone app that finds where yo

Jon Crall 29 Nov 29, 2022
Algorithms implemented in Python

Python Algorithms Library Laurent Luce Description The purpose of this library is to help you with common algorithms like: A* path finding. String Mat

Laurent Luce 264 Dec 06, 2022
Genius Square puzzle solver in Python

Genius Square puzzle solver in Python

James 3 Dec 15, 2022
Optimal skincare partition finder using graph theory

Pigment The problem of partitioning up a skincare regime into parts such that each part does not interfere with itself is equivalent to the minimal cl

Jason Nguyen 1 Nov 22, 2021
Programming Foundations Algorithms With Python

Programming-Foundations-Algorithms Algorithms purpose to solve a specific proplem with a sequential sets of steps for instance : if you need to add di

omar nafea 1 Nov 01, 2021
zoofs is a Python library for performing feature selection using an variety of nature inspired wrapper algorithms. The algorithms range from swarm-intelligence to physics based to Evolutionary. It's easy to use ,flexible and powerful tool to reduce your feature size.

zoofs is a Python library for performing feature selection using a variety of nature-inspired wrapper algorithms. The algorithms range from swarm-intelligence to physics-based to Evolutionary. It's e

Jaswinder Singh 168 Dec 30, 2022
Given a list of tickers, this algorithm generates a recommended portfolio for high-risk investors.

RiskyPortfolioGenerator Given a list of tickers, this algorithm generates a recommended portfolio for high-risk investors. Working in a group, we crea

Victoria Zhao 2 Jan 13, 2022
A collection of Python Scripts made for fun, while exploring Python 🐍

JFF-Python-Scripts A collection of Python Scripts made for fun, while exploring Python 🐍 Inspiration 💡 Many of the programs in this repository are i

Pushkar Patel 16 Oct 07, 2022
Exact algorithm for computing two-sided statistical tolerance intervals under a normal distribution assumption using Python.

norm-tol-int Exact algorithm for computing two-sided statistical tolerance intervals under a normal distribution assumption using Python. Methods The

Jed Ludlow 1 Jan 06, 2022
Xor encryption and decryption algorithm

Folosire: Pentru encriptare: python encrypt.py parola fișier pentru criptare fișier encriptat(de tip binar) Pentru decriptare: python decrypt.p

2 Dec 05, 2021
A lightweight, object-oriented finite state machine implementation in Python with many extensions

transitions A lightweight, object-oriented state machine implementation in Python with many extensions. Compatible with Python 2.7+ and 3.0+. Installa

4.7k Jan 01, 2023
An NUS timetable generator which uses a genetic algorithm to optimise timetables to suit the needs of NUS students.

A timetable optimiser for NUS which uses an evolutionary algorithm to "breed" a timetable suited to your needs.

Nicholas Lee 3 Jan 09, 2022
Parameterising Simulated Annealing for the Travelling Salesman Problem

Parameterising Simulated Annealing for the Travelling Salesman Problem Abstract The Travelling Salesman Problem is a well known NP-Hard problem. Given

Gary Sun 55 Jun 15, 2022
Evol is clear dsl for composable evolutionary algorithms that optimised for joy.

Evol is clear dsl for composable evolutionary algorithms that optimised for joy. Installation We currently support python3.6 and python3.7 and you can

GoDataDriven 178 Dec 27, 2022
A calculator to test numbers against the collatz conjecture

The Collatz Calculator This is an algorithm custom built by Kyle Dickey, used to test numbers against the simple rules of the Collatz Conjecture. Get

Kyle Dickey 2 Jun 14, 2022