This project aims to the development of an open-source experimental prototype for solving and generating Sudoku puzzles by using only the strength of Genetic Algorithms. This is not a general purpose GA framework but a specific GA implementation for solving and generating Sudoku puzzles. The mechanics of the GA are based on the theoretical scientific paper “Solving and Rating Sudoku Puzzles with Genetic Algorithms” of Timo Mantere and Janne Koljonen. From the first moment, I liked the paper. So, I implemented it in Python. Also, I have add some variations to the algorithm in order to be more efficient. This project can be used in order to solve or generate new NxN Sudoku puzzles with N sub-boxes (e.g. 4×4, 9×9, etc).
The Genetic Algorithm implements the following features:
- Constraint Satisfaction Fitness Function (Linear combination of partial costs)
- Used for solving and generating NxN Sudoku puzzles with N sub-boxes
- Object-Oriented Encoded Genotypes
- Genotypes of multiples genes
- GA terminates when a solution is found
- Elitism by cloning of the best individual
- Tournament & Rank selection methods for the natural selection
- Generational replacement of parents and children
- One-point Crossover / Uniform Genes Crossover / Uniform Alleles Crossover
- Use of all the possible offsprings after a crossover genetic operator is applied
- Reset Gene Mutation / N-Swap Genes Mutation
For more information you can get the project itself :
`nature-inspired-sudoku-solver‘
Follows an example for generating a new 4×4 Sudoku puzzle :
#! /usr/bin/env python
# Generating a new solved 4x4 Sudoku puzzle.
#
# Copyright (C) 2013 Efstathios Chatzikyriakidis <stathis.chatzikyriakidis@gmail.com>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
try:
from SudokuSolver import SudokuGA
except (ImportError) as error:
import sys, os
sys.exit('{0}: {1}.'.format(os.path.basename(__file__), error))
parameters = {
'populationSize': 300,
'mutationProbability': 0.012,
'tournamentSize': 5,
'candidateGenotype': [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
}
ga = SudokuGA(parameters)
solution = ga.evolution()
print solution
Follows an example for solving an existing 9×9 Sudoku puzzle :
#! /usr/bin/env python
# Solving a 9x9 Sudoku puzzle (36 numbers missing).
#
# Copyright (C) 2013 Efstathios Chatzikyriakidis <stathis.chatzikyriakidis@gmail.com>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
try:
from SudokuSolver import SudokuGA
except (ImportError) as error:
import sys, os
sys.exit('{0}: {1}.'.format(os.path.basename(__file__), error))
parameters = {
'populationSize': 1000,
'mutationProbability': 0.012,
'tournamentSize': 8,
'candidateGenotype': [[2, 0, 0, 8, 0, 4, 0, 7, 1],
[5, 8, 9, 0, 0, 1, 0, 0, 3],
[0, 1, 7, 3, 6, 0, 0, 2, 0],
[0, 6, 0, 0, 2, 3, 1, 9, 0],
[0, 2, 5, 9, 0, 0, 7, 0, 8],
[7, 0, 3, 0, 8, 1, 6, 0, 0],
[6, 0, 0, 5, 4, 0, 0, 1, 2],
[3, 9, 0, 0, 1, 0, 4, 5, 0],
[0, 5, 4, 0, 3, 6, 0, 0, 8]]
}
ga = SudokuGA(parameters)
solution = ga.evolution()
print solution
NOTE: For those who want to play further with the Genetic Algorithm take account that the “candidateGenotype” parameter has a specific structure (Is not like WYSIWYG). The Sudoku puzzle is not structured the way we see it in the examples. To see how we structure a Sudoku puzzle before we pass it to the “SudokuGA” object you should take a look to the paper of Timo Mantere and Janne Koljonen.
Efstathios Chatzikyriakidis 