Created
January 1, 2013 10:35
-
-
Save anthony-tresontani/4426452 to your computer and use it in GitHub Desktop.
Sudoku genetic algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from random import choice, shuffle | |
from pygene.gene import BaseGene | |
from pygene.organism import Organism, MendelOrganism | |
from pygene.population import Population | |
def flat_to_square(list_, size=9): | |
return [list_[i:i+size] for i in range(len(list_)/size)] | |
class LineGene(BaseGene): | |
mutProb = 0.001 | |
def __add__(self, other): | |
return choice([self.value, other.value]) | |
def mutate(self): | |
indexes = range(9) | |
shuffle(indexes) | |
x,y = indexes[:2] | |
self.value[x], self.value[y] = self.value[y], self.value[x] | |
def randomValue(self): | |
values = range(1,10) | |
shuffle(values) | |
return values | |
genome = {} | |
for i in range(9): | |
genome[str(i)] = LineGene | |
NB_VAL_LINE = 9 | |
NB_BLOCK = 3 | |
class Sudoku(MendelOrganism): | |
genome = genome | |
mutateOneOnly = True | |
def __repr__(self): | |
sudoku = [self[str(i)] for i in xrange(self.numgenes)] | |
return str(sudoku) | |
def fitness(self): | |
sudoku = [self[str(i)] for i in xrange(self.numgenes)] | |
result = 0 | |
for l in sudoku: | |
line = set(l) | |
result += NB_VAL_LINE - len(line) | |
for i in range(NB_VAL_LINE): | |
column = set(line[i] for line in sudoku) | |
result += NB_VAL_LINE - len(column) | |
for x in range(NB_BLOCK): | |
for y in range(NB_BLOCK): | |
block = set(sudoku[x*NB_BLOCK + xshift][y*NB_BLOCK + yshift] for xshift in range(NB_BLOCK) for yshift in range(NB_BLOCK)) | |
result += NB_VAL_LINE - len(block) | |
return result | |
class SudokuPopulation(Population): | |
# Population species | |
species = Sudoku | |
# start with a population of 10 random organisms | |
initPopulation = 1000 | |
# cull to this many children after each generation | |
childCull = 4000 | |
# number of children to create after each generation | |
childCount = 1000 | |
def main(): | |
# Create initial population | |
ph = SudokuPopulation() | |
# Iterate over generations | |
i = 0 | |
while True: | |
b = ph.best() | |
print "generation %s: %s best=%s average=%s)" % ( | |
i, repr(b), b.get_fitness(), ph.fitness()) | |
if b.get_fitness() <= 0: | |
print "cracked!" | |
break | |
i += 1 | |
ph.gen() | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment