genetic sudoku generator, naive try

gistfile1.txt

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 = 400
    
    # cull to this many children after each generation
    childCull = 420
    
    # number of children to create after each generation
    childCount = 400
    

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()