stlukey/Sudoku-EA.py

## Sudoku-EA.py
#!/usr/bin/env python2
"""
Sudoku solving Evolutionary Algorithm.

Usage: pypy Sudoku-AI.py <sudoku-file> <population-size>

Please make sure you execute using PyPy 2.7
"""

from __future__ import print_function
from operator import itemgetter
import random
import copy

random.seed(5)

# Parameters
DEFAULT_POPULATION_SIZE = 1000
MUTATION_RATE = 0.3

# Range is set to a variable to alternate between range and xrange.
# (for switching python versions)
r = xrange

# range(len(x)) helper.
rl = lambda l: r(len(l))

# Unknown squares are 'X'.
X = None

def print_sudoku(s):
    """Print a sudoku."""
    for i in rl(s):
        for j in rl(s[0]):
            # Use '0' to represent unknowns.
            v = s[i][j] if s[i][j] != X else 0
            print(v, end=',')
            if j + 1 == len(s[0]):
                print()
                if (i % 3) == 2:
                    print()
            elif (j % 3) == 2:
                print(' ', end='')

# Calculate uniqueness value.
uniqueness = lambda values: len(set(values))

# Get coordinates of flipped rows to squares grid.
get_pos = lambda row, column: (
    3*(row//3) + (column//3),
    3*(row%3) + (column%3)
)

# Flip grid rows to columns.
flip_rows_columns = lambda grid: map(list, zip(*grid))

def flip_rows_squares(grid):
    """Flip rows to squares."""
    flipped = [[0 for _ in range(9)] for _ in range(9)]
    for i in range(9):
        for j in range(9):
            x, y = get_pos(i, j)
            flipped[x][y] = grid[i][j]
    return flipped

def create_chromosome(sudoku):
    """Create an individual solution."""
    content, numbers = copy.deepcopy(sudoku), set(r(1, 10))
    for i in r(9):
        unknown = numbers ^ set(filter(None, sudoku[i]))
        for j in r(9):
            if content[i][j] is X:
                new = random.sample(unknown, 1)[0]
                unknown.remove(new)
                content[i][j] = new

    return content

# Evaluation function. Uses uniqueness of rows, columns and squares.
evaluate = lambda chromosome: sum([
    uniqueness(chromosome[i]) +
    uniqueness(flip_rows_columns(chromosome)[i]) +
    uniqueness(flip_rows_squares(chromosome)[i])
    for i in r(9)
])

# Choose best rows from parents.
crossover_best = lambda a, b: list(
    a[i] if uniqueness(a[i]) > uniqueness(b[i]) else
    b[i] for i in r(9)
)

def recombine(*parents):
    """Recombination operator."""
    # First child is best squares.
    yield flip_rows_squares(crossover_best(*map(flip_rows_squares, parents)))
    # Second child is best rows or columns.
    yield crossover_best(*parents) if random.random() >= 0.5 else\
          flip_rows_columns(crossover_best(*map(flip_rows_columns, parents)))

def mutate(chromosome, fixed_points):
    """Mutation operator."""
    choice = random.randrange(3)

    # Swap on row.
    if choice == 0:
        new = chromosome
        index = random.randrange(9)
        row = new[index]
        a = random.randrange(9)
        while (index, a) in fixed_points:
            a = random.randrange(9)
        b = random.randrange(9)
        while (index, b) in fixed_points or a == b:
            b = random.randrange(9)
        new[index][a], new[index][b] = new[index][b], new[index][a]

    # Swap on column.
    if choice == 1:
        new = chromosome
        index = random.randrange(9)
        a = random.randrange(9)
        while (index, a) in fixed_points:
            a = random.randrange(9)
        b = random.randrange(9)
        while (index, b) in fixed_points or a == b:
            b = random.randrange(9)
        new[a][index], new[b][index] = new[b][index], new[a][index]

    # Swap on square.
    if choice == 2:
        squares = flip_rows_squares(chromosome)
        indexes = range(9)
        random.shuffle(indexes)
        for i in indexes:
            a, b = None, None

            other_indexes = range(9)
            random.shuffle(other_indexes)
            for j in other_indexes:
                if get_pos(i, j) not in fixed_points:
                    a = j
                    break

            if a is None:
                continue

            random.shuffle(other_indexes)
            for j in other_indexes:
                if get_pos(i, j) not in fixed_points and a != b:
                    b = j
                    break

            if b is None:
                continue

            squares[i][a], squares[i][b] = squares[i][b], squares[i][a]
            break
        squares = squares
        return flip_rows_squares(squares)

    return new

def fixed_points(sudoku):
    """Generator for coordinates of fixed points."""
    for i in rl(sudoku):
        for j in rl(sudoku[i]):
            if sudoku[i][j] != X:
                yield (i, j)

def from_char(c):
    """Convert char to int, if numerical otherwise None."""
    try:
        return int(c)
    except ValueError:
        return X

def from_file(filename):
    """Opens file, and returns the sudoku grid.
    (auto closes using with statement)"""
    with open(filename) as f:
        return [
            map(from_char, l.replace('!', ''))
            for l in f.readlines()
            if not l.startswith('-')
        ]

MAX_FITNESS = 9 * 9 * 3

# Convert chromosome into hashable format (and back again) for use in sets.
make_hashable = lambda chromosome: tuple(map(tuple, chromosome))
make_unhashable = lambda chromosome: list(map(list, chromosome))

def select(pop, k=3):
    """Turnament selection"""
    l = random.sample(pop, k)
    return max(l, key=itemgetter(0))[1]

def evolve(sudoko, population_size=DEFAULT_POPULATION_SIZE):
    """The main evolutionary algorithm."""
    # Grab the fixed points.
    fixed = tuple(fixed_points(sudoko))

    # Initialise unique and random population.
    population = []
    while len(population) != population_size:
        ch = create_chromosome(sudoko)
        if ch not in population:
            population.append(ch)

    # Evaluate population.
    # Converts `population` to -> [(fitness, chromosome)...]
    population = sorted(
        zip(map(evaluate, population), population),
        key=itemgetter(0),
        reverse=True
    )

    # Store the best chromosomes found.
    best_set = {make_hashable(population[0][1])}
    best_set_all_time = {make_hashable(population[0][1])}
    passes = 0
    max_ = population[0][0]

    while population[0][0] < MAX_FITNESS:
        # Select parents.
        mating_pool = [
            c for f, c in population
            for _ in r(int(population[-1][0] * 1.5) - f)
        ]

        # Recombine parents.
        new_chromosomes = []
        for i in r(len(population) // 2):
            a, b = select(population), select(population) #random.choice(mating_pool), random.choice(mating_pool)
            map(new_chromosomes.append, recombine(a, b))

        # Select.
        # Keep previous best.
        new = new_chromosomes + [population[0][1]]

        super_mutation = (population_size > 500 and passes == 300) or\
            (population_size <= 500 and passes >= 1000 and population_size >= 100)

        # Aggressive and none aggressive super mutations.
        if super_mutation or (population_size < 100 and passes == 3000):
            new = map(
                make_unhashable,
                random.sample(
                    best_set,
                    (population_size
                        if len(best_set) > population_size
                            else len(best_set)
                    )
                )
            )

        # Mutate.
        for i in rl(new):
            if random.random() > MUTATION_RATE:
                new[i] = mutate(new[i], fixed)

        # Evaluate
        fitness = map(evaluate, new)
        best = max(fitness)
        best_set.add(make_hashable(new[fitness.index(best)]))
        if best > max_:
            print("%.3f %%" % ((100.0 / MAX_FITNESS) * best))
            max_ = best
            best_set_all_time.add(make_hashable(new[fitness.index(best)]))
            passes = 0
        else:
            passes += 1

        population = sorted(
            zip(fitness, new),
            key=itemgetter(0),
            reverse=True
        )

    print_sudoku(population[0][1])


# If file is executed grab arguments and run evolve.
if __name__ == "__main__":
    import sys
    population = DEFAULT_POPULATION_SIZE
    if len(sys.argv) == 1:
        print(__doc__)
        exit(1)
    puzzle = from_file(sys.argv[1])
    if len(sys.argv) > 2:
        population = int(sys.argv[2])
    evolve(puzzle, population)
	#!/usr/bin/env python2
	"""
	Sudoku solving Evolutionary Algorithm.

	Usage: pypy Sudoku-AI.py <sudoku-file> <population-size>

	Please make sure you execute using PyPy 2.7
	"""

	from __future__ import print_function
	from operator import itemgetter
	import random
	import copy

	random.seed(5)

	# Parameters
	DEFAULT_POPULATION_SIZE = 1000
	MUTATION_RATE = 0.3

	# Range is set to a variable to alternate between range and xrange.
	# (for switching python versions)
	r = xrange

	# range(len(x)) helper.
	rl = lambda l: r(len(l))

	# Unknown squares are 'X'.
	X = None

	def print_sudoku(s):
	"""Print a sudoku."""
	for i in rl(s):
	for j in rl(s[0]):
	# Use '0' to represent unknowns.
	v = s[i][j] if s[i][j] != X else 0
	print(v, end=',')
	if j + 1 == len(s[0]):
	print()
	if (i % 3) == 2:
	print()
	elif (j % 3) == 2:
	print(' ', end='')

	# Calculate uniqueness value.
	uniqueness = lambda values: len(set(values))

	# Get coordinates of flipped rows to squares grid.
	get_pos = lambda row, column: (
	3*(row//3) + (column//3),
	3*(row%3) + (column%3)
	)

	# Flip grid rows to columns.
	flip_rows_columns = lambda grid: map(list, zip(*grid))

	def flip_rows_squares(grid):
	"""Flip rows to squares."""
	flipped = [[0 for _ in range(9)] for _ in range(9)]
	for i in range(9):
	for j in range(9):
	x, y = get_pos(i, j)
	flipped[x][y] = grid[i][j]
	return flipped

	def create_chromosome(sudoku):
	"""Create an individual solution."""
	content, numbers = copy.deepcopy(sudoku), set(r(1, 10))
	for i in r(9):
	unknown = numbers ^ set(filter(None, sudoku[i]))
	for j in r(9):
	if content[i][j] is X:
	new = random.sample(unknown, 1)[0]
	unknown.remove(new)
	content[i][j] = new

	return content

	# Evaluation function. Uses uniqueness of rows, columns and squares.
	evaluate = lambda chromosome: sum([
	uniqueness(chromosome[i]) +
	uniqueness(flip_rows_columns(chromosome)[i]) +
	uniqueness(flip_rows_squares(chromosome)[i])
	for i in r(9)
	])

	# Choose best rows from parents.
	crossover_best = lambda a, b: list(
	a[i] if uniqueness(a[i]) > uniqueness(b[i]) else
	b[i] for i in r(9)
	)

	def recombine(*parents):
	"""Recombination operator."""
	# First child is best squares.
	yield flip_rows_squares(crossover_best(*map(flip_rows_squares, parents)))
	# Second child is best rows or columns.
	yield crossover_best(*parents) if random.random() >= 0.5 else\
	flip_rows_columns(crossover_best(*map(flip_rows_columns, parents)))

	def mutate(chromosome, fixed_points):
	"""Mutation operator."""
	choice = random.randrange(3)

	# Swap on row.
	if choice == 0:
	new = chromosome
	index = random.randrange(9)
	row = new[index]
	a = random.randrange(9)
	while (index, a) in fixed_points:
	a = random.randrange(9)
	b = random.randrange(9)
	while (index, b) in fixed_points or a == b:
	b = random.randrange(9)
	new[index][a], new[index][b] = new[index][b], new[index][a]

	# Swap on column.
	if choice == 1:
	new = chromosome
	index = random.randrange(9)
	a = random.randrange(9)
	while (index, a) in fixed_points:
	a = random.randrange(9)
	b = random.randrange(9)
	while (index, b) in fixed_points or a == b:
	b = random.randrange(9)
	new[a][index], new[b][index] = new[b][index], new[a][index]

	# Swap on square.
	if choice == 2:
	squares = flip_rows_squares(chromosome)
	indexes = range(9)
	random.shuffle(indexes)
	for i in indexes:
	a, b = None, None

	other_indexes = range(9)
	random.shuffle(other_indexes)
	for j in other_indexes:
	if get_pos(i, j) not in fixed_points:
	a = j
	break

	if a is None:
	continue

	random.shuffle(other_indexes)
	for j in other_indexes:
	if get_pos(i, j) not in fixed_points and a != b:
	b = j
	break

	if b is None:
	continue

	squares[i][a], squares[i][b] = squares[i][b], squares[i][a]
	break
	squares = squares
	return flip_rows_squares(squares)

	return new

	def fixed_points(sudoku):
	"""Generator for coordinates of fixed points."""
	for i in rl(sudoku):
	for j in rl(sudoku[i]):
	if sudoku[i][j] != X:
	yield (i, j)

	def from_char(c):
	"""Convert char to int, if numerical otherwise None."""
	try:
	return int(c)
	except ValueError:
	return X

	def from_file(filename):
	"""Opens file, and returns the sudoku grid.
	(auto closes using with statement)"""
	with open(filename) as f:
	return [
	map(from_char, l.replace('!', ''))
	for l in f.readlines()
	if not l.startswith('-')
	]

	MAX_FITNESS = 9 * 9 * 3

	# Convert chromosome into hashable format (and back again) for use in sets.
	make_hashable = lambda chromosome: tuple(map(tuple, chromosome))
	make_unhashable = lambda chromosome: list(map(list, chromosome))

	def select(pop, k=3):
	"""Turnament selection"""
	l = random.sample(pop, k)
	return max(l, key=itemgetter(0))[1]

	def evolve(sudoko, population_size=DEFAULT_POPULATION_SIZE):
	"""The main evolutionary algorithm."""
	# Grab the fixed points.
	fixed = tuple(fixed_points(sudoko))

	# Initialise unique and random population.
	population = []
	while len(population) != population_size:
	ch = create_chromosome(sudoko)
	if ch not in population:
	population.append(ch)

	# Evaluate population.
	# Converts `population` to -> [(fitness, chromosome)...]
	population = sorted(
	zip(map(evaluate, population), population),
	key=itemgetter(0),
	reverse=True
	)

	# Store the best chromosomes found.
	best_set = {make_hashable(population[0][1])}
	best_set_all_time = {make_hashable(population[0][1])}
	passes = 0
	max_ = population[0][0]

	while population[0][0] < MAX_FITNESS:
	# Select parents.
	mating_pool = [
	c for f, c in population
	for _ in r(int(population[-1][0] * 1.5) - f)
	]

	# Recombine parents.
	new_chromosomes = []
	for i in r(len(population) // 2):
	a, b = select(population), select(population) #random.choice(mating_pool), random.choice(mating_pool)
	map(new_chromosomes.append, recombine(a, b))

	# Select.
	# Keep previous best.
	new = new_chromosomes + [population[0][1]]

	super_mutation = (population_size > 500 and passes == 300) or\
	(population_size <= 500 and passes >= 1000 and population_size >= 100)

	# Aggressive and none aggressive super mutations.
	if super_mutation or (population_size < 100 and passes == 3000):
	new = map(
	make_unhashable,
	random.sample(
	best_set,
	(population_size
	if len(best_set) > population_size
	else len(best_set)
	)
	)
	)

	# Mutate.
	for i in rl(new):
	if random.random() > MUTATION_RATE:
	new[i] = mutate(new[i], fixed)

	# Evaluate
	fitness = map(evaluate, new)
	best = max(fitness)
	best_set.add(make_hashable(new[fitness.index(best)]))
	if best > max_:
	print("%.3f %%" % ((100.0 / MAX_FITNESS) * best))
	max_ = best
	best_set_all_time.add(make_hashable(new[fitness.index(best)]))
	passes = 0
	else:
	passes += 1

	population = sorted(
	zip(fitness, new),
	key=itemgetter(0),
	reverse=True
	)

	print_sudoku(population[0][1])


	# If file is executed grab arguments and run evolve.
	if __name__ == "__main__":
	import sys
	population = DEFAULT_POPULATION_SIZE
	if len(sys.argv) == 1:
	print(__doc__)
	exit(1)
	puzzle = from_file(sys.argv[1])
	if len(sys.argv) > 2:
	population = int(sys.argv[2])
	evolve(puzzle, population)