Sudoku Genetic Algorithm Solver

Introduction

This is a project to use Genetic Algorithm to solve the Sudoku problem.

Several Concepts:

1. Population
2. Chromosome (also called Individual)
3. Gene

You can check this reference.

Steps for Genetic Algorithm

1. Generate initial population with random gene in each indiviual chromosome.
2. Define the fitness function for Sudoku, which I used the valid solution count as the fitness value.
3. To generate the next generation, you need do crossover, mutation. In my solution, I picked top 10 solutions and randomly pick 2 of them as parents, then crossover the last row, at last, to swap random 2 values for the mutation.
4. Once generated a new generation, then loop above steps, until you have complete solution.

Places that you can tune.

1. Crossover method, like swap with last several columns/rows, or alternatively take parentss' gene.
2. Crossover count, like the percentage of chromosome for the crossover.
3. Mutation method, like I provided, randomly change one field with a random word, or you can randomly swap 2 fields.
4. Mutation count, like how many fields need to be mutated.
5. Population Size.
6. Parent Selection method, like top 10, or top 20.

Genetic algorithm, doesn't guarantee you will generate the final result within certain generations, it largely depends on your crossover and mutation method, it's has certain randomness there, but from the result, it shows if you choose good parents, the next generation mostly will getting better and better.

How to run

go mod tidy
go run -v ./...

Result:

0th generation:
Matrix:  [R O D W W D O R R O W W W O R D] Valid Solution:  6
1th generation:
Matrix:  [R O D W W D O R R O W D W O R D] Valid Solution:  7
2th generation:
Matrix:  [R O D W W D O R R O W D D W R O] Valid Solution:  10
3th generation:
Matrix:  [R O D W W D O R R O W D D W R O] Valid Solution:  10
4th generation:
Matrix:  [R O D W W D O R R O W D D W R O] Valid Solution:  10
5th generation:
Matrix:  [R O D W W D O R R O W D D W R O] Valid Solution:  10
6th generation:
Result:
[R O D W]
[W D O R]
[O R W D]
[D W R O]
Total Valid Solutions:  12

Pseudocode

START
Generate the initial population
REPEAT
  Compute fitness for all individual
  Selection for parents
  Crossover for next generation
  Mutation each individual of the next generation
UNTIL population has converged
STOP

Findings

• After crossover several generations, all the individuals is going to be the same, so the mutation becomes to be important.

References

• https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3#:~:text=A%20genetic%20algorithm%20is%20a,offspring%20of%20the%20next%20generation.
• https://www.researchgate.net/publication/224180108_Solving_Sudoku_with_genetic_operations_that_preserve_building_blocks
• https://github.com/ctjacobs/sudoku-genetic-algorithm/blob/master/sudoku.py