[ Foro de Python ]
HE IMPLEMENTADO UN CODIGO DE UN ALGORITMO GENETICO PARA RESOLVER UN SUDOKU Y NO CONSIGO QUE FUNCIONE BIEN Y LO RESUELVA CORRECTAMNETE. NO SOY PROGRAMADOR. ALGUIEN ME PUEDE AYUDAR?
ESTE ES EL CODIGO:
import numpy as np
import random
import time
# Define the initial Sudoku board (some cells are empty, represented by 0)
initial_board = [
[0, 8, 5, 7, 0, 4, 0, 0, 0],
[2, 1, 0, 6, 8, 0, 3, 0, 0],
[3, 0, 0, 1, 0, 0, 8, 6, 7],
[0, 0, 2, 0, 4, 0, 7, 0, 6],
[0, 0, 3, 0, 6, 0, 0, 5, 2],
[1, 4, 0, 0, 0, 7, 0, 0, 3],
[4, 0, 0, 5, 0, 0, 0, 2, 9],
[0, 3, 0, 0, 1, 0, 6, 0, 0],
[0, 2, 0, 8, 9, 6, 0, 3, 0]
]
# Convert the initial board into a numpy array
initial_board = np.array(initial_board)
# Create an initial population of solutions
def create_population(size):
population = []
for _ in range(size):
board = initial_board.copy() # Use copy to avoid modifying the original
for i in range(9):
for j in range(9):
if board[i, j] == 0: # Fill empty cells
possible_values = set(range(1, 10)) # Numbers 1 to 9
possible_values -= set(board[i, :]) # Remove same numbers in the same row
possible_values -= set(board[:, j]) # Remove same numbers in the same column
block_x, block_y = i // 3, j // 3
block = board[block_x * 3:block_x * 3 + 3, block_y * 3:block_y * 3 + 3]
possible_values -= set(block.flatten()) # Remove same numbers in the same block
if possible_values: # If there are valid options
board[i, j] = random.choice(list(possible_values))
population.append(board)
return population
# Evaluate the fitness of a solution
def fitness(board):
score = 0
# Sum the scores for rows, columns, and 3x3 blocks
for i in range(9):
score += len(set(board[i, :])) # Rows
score += len(set(board[:, i])) # Columns
for block_x in range(3):
for block_y in range(3):
block = board[block_x * 3:block_x * 3 + 3, block_y * 3:block_y * 3 + 3]
score += len(set(block.flatten()))
return score
# Crossover two solutions
def crossover(parent1, parent2):
child = parent1.copy()
for i in range(9):
for j in range(9):
if random.random() < 0.5 and child[i, j] == 0: # Crossover with 50% probability and only for empty cells
child[i, j] = parent2[i, j]
return child
# Mutate a solution
def mutate(board, mutation_rate=0.2): # Increased mutation rate
for i in range(9):
for j in range(9):
if initial_board[i, j] == 0 and random.random() < mutation_rate: # Mutate only empty cells
possible_values = set(range(1, 10)) - set(board[i, :]) - set(board[:, j])
block_x, block_y = i // 3, j // 3
block = board[block_x * 3:block_x * 3 + 3, block_y * 3:block_y * 3 + 3]
possible_values -= set(block.flatten())
if possible_values:
board[i, j] = random.choice(list(possible_values))
return board
# Genetic algorithm
def genetic_algorithm(population_size, generations):
population = create_population(population_size)
for generation in range(generations):
# Evaluate the population
population = sorted(population, key=fitness, reverse=True)
best_score = fitness(population[0])
print(f'Generation {generation}, best score: {best_score}')
# If we have reached the perfect score, stop
if best_score == 243:
print("Solution found!")
break
# Select the best individuals for the next generation
next_generation = population[:population_size // 2]
# Fill the next generation with offspring
while len(next_generation) < population_size:
parent1 = random.choice(next_generation)
parent2 = random.choice(next_generation)
child = crossover(parent1, parent2)
child = mutate(child)
next_generation.append(child)
population = next_generation
return population[0] # Return the best solution
# Run the genetic algorithm and measure time
start_time = time.time()
solution = genetic_algorithm(population_size=200, generations=1000) # Increased population and generations
end_time = time.time()
# Print the solution and execution time
print("Solution found:")
print(solution)
print("Execution time:", end_time - start_time, "seconds")