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.
0 kommentar(er)
