Home > Machine Learning, Projects > A Nature Inspired Sudoku Solver.

A Nature Inspired Sudoku Solver.

December 25, 2013 Leave a comment Go to comments

This machine learning 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:

  1. Constraint Satisfaction Fitness Function (Linear combination of partial costs with some penalties)
  2. Used for solving and generating NxN Sudoku puzzles with N sub-boxes
  3. Object-Oriented Encoded Genotypes
  4. Genotypes of multiples genes
  5. GA terminates when a solution is found
  6. Elitism by cloning of the best individual
  7. Tournament & Rank selection methods for the natural selection
  8. Generational replacement of parents and children
  9. One-point Crossover / Uniform Genes Crossover / Uniform Alleles Crossover
  10. Use of all the possible offsprings after a crossover genetic operator is applied
  11. 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 <contact@efxa.org>
#
#    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 <contact@efxa.org>
#
#    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.

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: