A novel multistage genetic algorithm approach for solving Sudoku puzzle

Haradhan Chel, Deepak Mylavarapu, Deepak Sharma

2016 · 11 citations · 9 references

Concepts

Abstract

Sudoku is a NP complete combinatorial number placement puzzle which has been solved using various algorithms including evolutionary algorithms. In this paper, we propose a multistage genetic algorithm (GA) for solving Sudoku. In this algorithm, the group table concept has been incorporated. This work progresses with a couple of cycles. In every cycle GA works for finding better solution. The each elements of the best solution in any particular cycle undergo through a multidirectional crosscheck validation process and finally selected subject to a probability. After each cycle, group table is updated depending on the chosen elements of the best solution in the previous cycle. This algorithm also comprises of new population generation, fitness assignment with more penalization, crossover and mutation operators etc. The results show that multistage GA is competitive with good successful rate for solving various Sudoku puzzles.

References

9