#!/usr/bin/python
#
# miSudoku.py - a sudoku resolver using genetic algorithm
#
## Copyright (C) 2007 Luciano Bello 
##
## 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 2 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, write to the Free Software
## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
##

import random
import Numeric
import numpy

global sudoku
global crossover_algorithms
aptitudMedia=99

def funcion_de_aptitud (candidato):
#A mayor valor, menos favorable
    valor_de_aptitud=0
#Completar el sudoku con el candidato
    resuelto=""
    for x in range(0,len(sudoku)):
       if sudoku[x] == '.':
         resuelto = resuelto + candidato[0]
         candidato=candidato[1:]
       else:
         resuelto = resuelto + sudoku[x]  
    matrix = Numeric.reshape(list(resuelto), (9,9))
#Contar las repeticiones en cada fila/columna 
    for x in range(0,9):
        valor_de_aptitud += 9-len(uniq(matrix[x]))
        column=list()
        for y in range(0,81,9):
		    column.append(resuelto[y+x])
        valor_de_aptitud += 9-len(uniq(column))
#Contar las repeticiones en cada region 
    for x in range(0,9,3):
         for y in range(0,9,3):
              region=list()
              region.append(matrix[x][y])
              region.append(matrix[x][y+1])
              region.append(matrix[x][y+2])
              region.append(matrix[x+1][y])
              region.append(matrix[x+1][y+1])
              region.append(matrix[x+1][y+2])
              region.append(matrix[x+2][y])
              region.append(matrix[x+2][y+1])
              region.append(matrix[x+2][y+2])
              valor_de_aptitud += 9-len(uniq(region))
    return(valor_de_aptitud) 

def uniq(list) :
   """
   Hermosa funcion, robada de algun lugar de la web
   """
   return [ u for u in list if u not in locals()['_[1]'] ]

def evalSolutions(solutions):
    """
    Ordena la poblacion del mas favorable al menos favorable
    """
    global aptitudMedia
    ranking=[]
    ret=[]
    for x in range(0,len(solutions)):
       ranking.append([funcion_de_aptitud (solutions[x]),x])
    random.shuffle(ranking) #para que hermanos no se cruzen entre si generando a los padres
    ranking.sort()
    sum=0
    for x in ranking:
       ret.append(solutions[x[1]])
       sum += x[0]
    aptitudMedia=sum/len(ranking)
    return (ret)

def genPopulation(population):
  solution=[]
  exs = len(sudoku)-len(sudoku.replace(".",""))
#  print exs

  for y in range (0,population):
    x=""
    for i in range(0,exs):
      x=x+str(random.choice(range(1,10)))
    solution.append(x)
  return(solution)

def mutarIndividuo(individuo):
        """
        Agarro un valor al azar y lo modifico por un valor al azar	
        """
	#Elijo algun caracter al azar
	gen=random.choice(range(0,len(individuo)))
	mutation=str(random.choice(range(1,9)))
	mutante=individuo[:gen]+mutation+individuo[gen+1:]
	return (mutante)

def restar(a,b):
	"""
	resta vectores elemento a elemento. Deben ser del mismo largo. En modulo 9 +1
	"""
	ret=''
        for x in range(0,len(a)): 
	    ret += str(abs(int(a[x])-int(b[x]))%9+1)
	return(ret)

def sumar(a,b):
	"""
	suma vectores elemento a elemento. Deben ser del mismo largo. En modulo 9 +1
	"""
	ret=''
        for x in range(0,len(a)): 
	    ret += str((int(a[x])+int(b[x]))%9+1)
	return(ret)

def multiplicar(a,b):
	"""
	multiplica vectores elemento a elemento. Deben ser del mismo largo. En modulo 9 +1
	"""
	ret=''
        for x in range(0,len(a)):
	    ret += str((int(a[x])*int(b[x]))%9+1)
	return(ret)

def cruzar(madre,padre):
	algoritmo=random.choice(crossover_algorithms)
	if algoritmo == 'simple' or algoritmo == 1:
	  return (cruzamiento_simple(madre,padre))
	elif algoritmo == 'binomial puro' or algoritmo == 2:
	  return(cruzamiento_binomial_puro(madre,padre))
	elif algoritmo == 'binomial impuro' or algoritmo == 3:
	  return(cruzamiento_binomial(madre,padre))
	elif algoritmo == 'multipunto' or algoritmo == 4:
	  return(cruzamiento_multipunto(madre,padre))
	elif algoritmo == 'operar' or algoritmo == 5:
	  return(cruzamiento_operar(madre,padre))
	print "algoritmo no encontrado ->",algoritmo

def cruzamiento_simple(madre,padre):
	"""
	Una parte de la madre, otra del padre. Corta al azar.
	"""
	y=random.randrange(len(madre))
	child1 = madre[:y]+padre[y:]
	child2 = padre[:y]+madre[y:]
	return child1,child2

def cruzamiento_binomial_puro(madre,padre):
	"""
	No tiene en cuenta los genotipos. Usa algos genes del padre y otros de la madre al azar y en orden.
	"""
	child1=''
	child2=''
	for y in range(0,len(madre)):
	    if random.randint(0,1) == 0 :
		 child1 += madre[y]
		 child2 += padre[y]
	    else:
		 child1 += padre[y]
		 child2 += madre[y]
	return child1,child2

def cruzamiento_multipunto(madre,padre):
	"""
	Corta teniendo en cuenta los 'genotipos' (filas del sudoku). Toma madre o padre alternado.
	"""
	child1=''
	child2=''
	base=0
	for y in range(0,81,9):
	    exs = 9-len(sudoku[y:y+9].replace(".",""))
	    if random.randint(0,1) == 0 :
		 child1 += madre[base:base+exs]
		 child2 += padre[base:base+exs]
	    else:
		 child1 += padre[base:base+exs]
		 child2 += madre[base:base+exs]
            base += exs
	return child1,child2

def cruzamiento_binomial(madre,padre):
	"""
	Corta teniendo en cuenta los 'genotipos' (filas del sudoku). 
	Toma madre o padre al azar.
	"""
	child1=''
	child2=''
	base=0
	for y in range(0,81,9):
	    exs = 9-len(sudoku[y:y+9].replace(".",""))
	    if y%2 == 0 :
		 child1 += madre[base:base+exs]
		 child2 += padre[base:base+exs]
	    else:
		 child1 += padre[base:base+exs]
		 child2 += madre[base:base+exs]
            base += exs
	return child1,child2

def cruzamiento_operar(madre,padre):
	"""
	Cruzamiento que opera matematicamente sobre el padre y la 
	madre para obtener los hijos. Un intento por tener variedad.	
	"""
	child1=''
	child2=''
	base=0
	for y in range(0,81,9):
	    exs = 9-len(sudoku[y:y+9].replace(".",""))
            x=random.randint(0,1)
            if x==0:
                 child1 += restar(madre[base:base+exs],padre[base:base+exs])
                 child2 += restar(padre[base:base+exs],madre[base:base+exs])
            elif x==1:
                 child1 += sumar(madre[base:base+exs],padre[base:base+exs])
                 child2 += multiplicar(madre[base:base+exs],padre[base:base+exs])
            base += exs
	return child1,child2

def cruzamiento(paterns):
    """
     madre ->  paterns[x]
     padre ->  paterns[x+1]
    """
    children=[]
    for x in range(0,len(paterns)-1,2):
       children.extend(cruzar(paterns[x],paterns[x+1]))
    return(children)

def mejoresDeLaMedia(candidates,aptitudMedia):
    """
    Cuantos estan por arriba de la media?
    """
    ret=0
    for x in candidates:
       if funcion_de_aptitud(x) > aptitudMedia:
           ret +=1
    return(ret)

def media(conjunto):
    """
    La aptitud media de un conjunto 
    """
    ret=0
    for x in conjunto:
       ret += funcion_de_aptitud(x)
    return(ret/len(conjunto))

execfile("sudoku.conf")

sudoku = sudoku.replace("\n","")
sudoku = sudoku.replace(" ","")
print "# el problema:",
print sudoku

candidates = genPopulation(population)

candidates=evalSolutions(candidates)
vuelta=0
print "#vuelta","poblacionUnica","mejoresDeLaMedia","aptitudMedia","elMejor","elPeor","el20%mejor"

# Descomentar esta linea si lo que se busca es una solucion y comentar la siguiente
# while funcion_de_aptitud(candidates[0]) > 1:
while vuelta<300 :
   newpoblation=candidates[:selected_paterns]
   newpoblation.extend(cruzamiento(candidates[:selected_paterns]))
   newpoblation.extend(candidates[selected_paterns:-selected_paterns])
   if (random.randint(0, mutation)==0):
	mutante=random.randrange(2*selected_paterns,len(newpoblation)+1)-1
	candidates[mutante]=mutarIndividuo(newpoblation[mutante])
#	print "Mutacion! ->", mutante
   candidates=evalSolutions(newpoblation)
   vuelta +=1
   print vuelta,len(uniq(candidates)),mejoresDeLaMedia(candidates,aptitudMedia),aptitudMedia,funcion_de_aptitud(candidates[0]),funcion_de_aptitud(candidates[-1]),media(candidates[:int(len(candidates)*0.2)])

# Here is the winner
#print candidates[0] 
candidato=candidates[0]
resuelto=""
for x in range(0,len(sudoku)):
       if sudoku[x] == '.':
         resuelto = resuelto + candidato[0]
         candidato=candidato[1:]
       else:
         resuelto = resuelto + sudoku[x]
print Numeric.reshape(list(resuelto), (9,9))