Here are some limitations, to name but a few: GA are pretty cool things to work with but you need to keep in mind that it is not totally magic (only a little bit). Until a solution is found or the maximum number of generations is reached Recombine the solutions to produce n new solutionsĪpply the mutation operator to the solutions Randomly select two solutions from the population Rank the solutions, and retain only the percentage specified by selection rate Or, saying it with pseudo-code ( source): Then the cycle begins again with this new population which is then evaluated to serve as parents to the next.Finally, a dose of randomness is integrated by mutating a certain part of the new population generated.To avoid eugenics, a certain part of the population (including the bad solutions) is even selected to be parents.select best elements to become the “parents” of new solutions “children” who will have elements of the solution “father” and the solution “mother”.build a population of potential solutions of the problem and evaluate them according to a scoring method.The most important elements in this sentence are: “process of natural selection”, “evolutionary algorithms”, “bio-inspired operators” and “mutation, crossover and selection”.Īs you may now have understood, Genetic Algorithms are inspired by the Natural selection, Darwin’s theory of evolution, according to which the natural elimination of the least able individuals in the “struggle for life” allows the species to improve from generation to generation. Genetic algorithmsĪre commonly used to generate high-quality solutions to optimization and search problems by relying on bio-inspired operators such as mutation, crossover and selection.” 7 Credit: Harshil Gudka - Unsplash “a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Let’s start with the wikipedia definition: Credit: Hans-Peter Gauster - Unsplash What is a genetic algorithm? Principle Here is why we can try another approach by using a genetic algorithm. That is, the time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows” 6. Note: “if a solution to an NP-complete problem can be verified quickly, there is no known way to find a solution quickly. With greater size, it is not so easy and even for some 9x9 puzzles, sometimes it is difficult to solve them ‘just with logic’ and you need to bet on some answers to move on. Solving NxN Sudoku puzzles is known to be NP-complete. Pencil mark can help to fill some cells but it might stop because at some point there is no more cell with single value to safely assign. Using backtracking works fine for small grid sizes but becomes computationally unaffordable for larger grid sizes. For easy puzzles, this solution is sufficient to solve them. Then we start again until there is no more cell with unique value to assign. Some cells will have only one possible value so it is safe to assign this Pencil mark approach consists in filling all cells with possible values (i.e a value is which not already present in same row/column/grid) 5. If one of its advantages it to guarantee a solution will be found, a major drawback is that solving time may be slow due to the solutions tree sequential exploration. Principle is to fill empty cells with a value that satisfies the constraints, moving forward to the next cell when it works, moving backward when there is a constraint violation. That would take ages to run.īacktracking is also a kind of brute force search. Of course basic brute force is not an option: for a 9x9 grid puzzle, “number of essentially different solutions, when symmetries such as rotation, reflection, permutation, and relabelling are taken into account, was shown to be just 5,472,730,538“ 4. With a 9x9 puzzle, you should be able to solve the sudoku with another approach than deploying a genetic algorithm: Backtracking 1 2, Operations Research (as it is a Constraint Satisfaction Problem 3), Pencil Mark.Īnd I am pretty sure that a lof of others exists if you have time for a little googling session. Solving sudokus with computer: a lot of approaches are available

Objective was also to improve my personal skills in Python but perhaps sometimes my choices/approaches are not so 'pythonic', sorry about that.I could have used some libs such as pyevolve but the goal was more to understand how Genetic Algorithms works, what I am doing and why I am doing it.This project is only for personal challenge and educational purpose, no other pretention than those ones.

Algorithms for solving sudoku puzzles