This post is a follow-follow-up to this post and its follow-up.
In those two posts we managed to speed-up the solution of an Alberi puzzle, and to create a one-tree-per-region puzzle.
The complete code hereafter can be used to create multi-tree-per-region puzzles.
Using DFS I had little chance to find a valid puzzle, so I had to resort to a more exotic genetic algorithm.
The first class is the general genetic algorithm impementation (well the simplest of implementations):
"""Genetic algorithm simplicistic and generic implementation.
"""
import random
class GeneticAlgorithm(object):
"""Genetic algorithm iteration cycle.
The aim is to find an individual with the lowest fitness value
by evolving a population of such individuals.
Each individual is tested against a target value to evaluate its fitness
For each evolution loop part of the best are kept for the next cycle
(retain parameter for evolve method), part of the individuals are kept
indipendently from their fitness (random_select parameter), then these
individuals are mutated according to a mutation rate (mutate paramter),
the rest of the new population is made up crossing randomly picked
individuals.
"""
def __init__(self, individual, fitness, mutate, crossover):
"""Initializes the evolution functions from the problem factory.
Required argument:
individual -- function to generate a new individual. The function can
take a fixed number of parameters to initialize the individual.
This parameters are to be passed to the population method. The
return argument should be a mutable (see mutate).
fitness -- function to score an individual. An individual and the
target will be passed to the function. The target is set by the
evolve method. The function must return a numeric type.
mutate -- function to mutate in-place an individual. The function will
take a mutable as argument
crossover -- function to create a new individual using the genetic
code of the two individuals passed as argument. The return argument
should be a mutable.
"""
self.individual = individual
self.fitness = fitness
self.mutate_individual = mutate
self.crossover_individuals = crossover
def population(self, count, *args):
"""Create a number of individuals (i.e. a population).
Required argument:
count -- number of individuals to be created
*args -- parameters to be passed to the individual generation function
"""
return [self.individual(*args) for _ in range(count)]
def grade(self, pop, target):
"""Find average fitness for a population.
"""
summed = sum(self.fitness(x, target) for x in pop)
return summed / (len(pop) * 1.0)
def evolve(self, pop, target, retain=0.2, random_select=0.1, mutate=0.2):
"""Genetic algorithm evolution loop.
Required argument:
pop --- count of the elements of the population
target -- target value to obtain
Optional arguments:
retain -- Number of elements whith the lowest fitness to keep at
each iteration
random_select -- Rate of selection of elements whithout fitness
filtering
mutate -- Rate of mutation of elements
"""
graded = [(self.fitness(x, target), x) for x in pop]
graded = [x[1] for x in sorted(graded)]
retain_length = int(len(graded) * retain)
parents = graded[:retain_length]
# randomly add other individuals to
# promote genetic diversity
for individual in graded[retain_length:]:
if random_select > random.random():
parents.append(individual)
# mutate some individuals
for individual in parents:
if mutate > random.random():
self.mutate_individual(individual)
# crossover parents to create children
parents_length = len(parents)
desired_length = len(pop) - parents_length
children = []
while len(children) < desired_length:
male = random.randint(0, parents_length-1)
female = random.randint(0, parents_length-1)
if male != female:
male = parents[male]
female = parents[female]
child = self.crossover_individuals(male, female)
children.append(child)
parents.extend(children)
return parents
The class __init__ takes as argument the functions needed to generate an individual, evaluate its fitness against a target, mutate (in place) an individual and crossover two individual to make a third one.
The methods exposed are population, which creates the initial individuals to be evolved, grade, used to evaluate the global fitness of a population, and evolve, the core of the algorithm, that grows-up the population.
The functions I gave to the GeneticAlgorithm class are created by the following class:
"""Fill the empty cells of an Alberi puzzle using a genetic algorithm
"""
from AlberiCover import Alberi
from GeneticAlgorithm import GeneticAlgorithm
import random
class AlberiGeneticFactory(object):
"""Creates the functions needed for the evolution of the GA
"""
def __init__(self, m, n, per_row=2, per_column=2, per_region=2):
"""Initializes the factory parameters.
Required argument:
n -- Number of rows
m -- Number of columns
Optional arguments:
per_row -- Number of trees per row. (Default: 2.)
per_column -- Number of trees per column. (Default: 2.)
per_region -- Number of trees per region. (Default: 2.)
"""
self.m = m
self.n = n
self.size = size = m * n
self.per_row = per_row
self.per_column = per_column
self.per_region = per_region
neighbour = []
for idx in range(size):
row, col = divmod(idx, m)
neighbour.append(
[endr * n + col for endr in range(row - 1, row + 2)
if 0 <= endr < m and endr != row] +
[row * n + endc for endc in range(col - 1, col + 2)
if 0 <= endc < n and endc != col]
)
self.neighbour = neighbour
def individual_function(self):
"""Returns the function to create an Alberi puzzle.
"""
REGIONLESS = Alberi.REGIONLESS
ORL = ord(REGIONLESS)
neighbour = self.neighbour
def individual(puzzle):
""" Take a puzzle and makes a single mutation to it.
The mutation is made on a whitespace, labeling it with the letter
of a neighbouring field.
Required argument:
puzzle -- The puzzle to mutate, in the form of a string of n*m
letters indicating the regions. The whitespace ' ' can be
used as a placeholder for a cell with no region assigned.
"""
neighbour_field = [
set(puzzle[idx] for idx in lst if puzzle[idx] != REGIONLESS)
for lst in neighbour]
options = filter(lambda item: len(item[1])>0, enumerate(neighbour_field))
random.shuffle(options)
mypuzzle = bytearray(puzzle)
for option, vals in options:
if mypuzzle[option] != ORL:
continue
mypuzzle[option] = random.sample(vals, 1)[0]
break
return mypuzzle
return individual
def fitness_function(self):
"""Returns the function to evaluate the fitness an Alberi puzzle.
"""
m = self.m
n = self.n
size = self.size
per_row = self.per_row
per_column = self.per_column
per_region = self.per_region
REGIONLESS = Alberi.REGIONLESS
memo_fitness={}
def fitness(individual, target):
""" Take a partial puzzle and scores it.
The score is equal to the count of empty cells if the puzzle has
but one solution. The score defaults to size if the puzzle has
more than one solution.
The result is memoized, so it can speed up the scoring in case
of duplicate individuals.
Required argument:
individual -- The puzzle to score, in the form of a string of n*m
letters indicating the regions. The whitespace ' ' can be
used as a placeholder for a cell with no region assigned.
target -- unused. Here for compatibility with the GA
"""
puzzle = str(individual)
out = memo_fitness.get(puzzle)
if out:
return out
print(puzzle)
try:
asolver = Alberi(puzzle, m, n, per_row, per_column, per_region)
sols = [x for _, x in zip(xrange(2), asolver)]
out = puzzle.count(REGIONLESS) if len(sols) == 1 else size
except ValueError:
out = size
memo_fitness[puzzle] = out
return out
return fitness
def mutate_function(self):
"""Returns the function to mutate an Alberi puzzle.
"""
m = self.m
n = self.n
size = self.size
per_row = self.per_row
per_column = self.per_column
per_region = self.per_region
neighbour = self.neighbour
ORL = ord(Alberi.REGIONLESS)
def mutate_individual(individual):
""" Take a puzzle and makes a single mutation to it.
The mutation is made in-place.
If the mutation is made on a whitespace, this labels it with
the letter of a neighbouring field.
If the mutation is made on a labeled cell, this verifies that
the remaining cells still form a singly-connected region.
Required argument:
individual -- The puzzle to mutate, in the form of a string of n*m
letters indicating the regions. The whitespace ' ' can be
used as a placeholder for a cell with no region assigned.
"""
neighbour_field = [
set(individual[idx] for idx in lst if individual[idx] != ORL)
for lst in neighbour]
options = filter(
lambda item: len(item[1]) > 0,
enumerate(neighbour_field))
random.shuffle(options)
for option, vals in options:
if individual[option] == ORL:
individual[option] = random.sample(vals, 1)[0]
break
vals.difference_update([individual[option]])
if len(vals) == 0:
continue
# Tests if removing the element option from the region with
# its letter leaves a simply connected region. First make
# the region array with all the indexes of the cells with the
# letter at the index option (but without option), then do a
# BFS algorithm to assign a value (weight) to each cell (in
# this case is the minimum Manhattan distance from the first
# cell in the array). If every cell has been labeled with a
# value than the region is simply connected
region = [idx for idx, v in enumerate(individual)
if v == individual[option] and idx != option]
if len(region)==0:
continue
home = region.pop()
weights = [size+1] * len(region)
curlist = [home]
curval = 0
while len(curlist) > 0:
newlist = []
newval = curval + 1
for list_idx in curlist:
for cell in neighbour[list_idx]:
try:
idx = region.index(cell)
if weights[idx] > newval:
weights[idx] = newval
newlist.append(cell)
except:
pass
curlist = newlist
curval = newval
if all(w <= size for w in weights):
individual[option] = random.sample(vals, 1)[0]
else:
continue
break
return mutate_individual
def crossover_function(self):
"""Returns the function to crossover two puzzles.
"""
def crossover_individuals(male, female):
""" Returns a new puzzle made crossing the puzzles given as input.
The result is simply the first half of the male input joined to
the last half of the female input.
Required argument:
male, female -- The puzzles to crossover, in the form of a
string of n*m letters indicating the regions. The whitespace
' ' can be used as a placeholder for a cell with no region
assigned.
"""
half = len(male) / 2
child = male[:half] + female[half:]
return child
return crossover_individuals
The individuals are created from a starting puzzle by modifying one of the REGIONLESS cells. The fitness of each individual is the count of REGIONLESS cells, if the puzzle has one solution, else the size of the puzzle. The mutation is made by changing a cell to one of its neighbours' label (a check is made to control that the regions are always completely connected). The crossover simply shuffles the first half of a puzzle with the remaining of the other (this is dangerous because no check is made on the validity of the new puzzle).
The main solver class is about the same of the one in the last post. I just added a random parameter to the constructor to easily create random puzzles.
"""Solver for an Alberi puzzle using exact cover
"""
from collections import Iterator
from itertools import product
from ExactCoverExt import ExactCover
class Alberi(Iterator):
"""An iterator that yields the solutions to an Alberi problem.
>>> puzzle = '''
... aabbbccccccc
... accccccdddee
... accfcfdddgee
... afffffddggee
... aafffdddggee
... afffddddgggg
... hffffdiijjjj
... hffffiiikkkk
... hhhfiiiiiklk
... hhhffiilllll
... hhhffiilllll
... hhhfffilllll
... '''
>>> asolver = Alberi(*Alberi.multiline_to_solver_params(puzzle))
>>> print(asolver.decode_solution(next(asolver)))
>>> quit()
aaBbBccccccc
acccccCdddeE
acCfcfdddGee
AfffffDdggee
aafffdddGgEe
AfffDdddgggg
hffffdiiJjJj
hffFfIiikkkk
hhhfiiiiiKlK
hHhffiiLllll
hhhFfIilllll
hHhfffiLllll
"""
REGIONLESS = ' '
VOID = '.'
def __init__(self, puzzle, m, n, per_row=2, per_column=2, per_region=2, random=False):
"""Construct an Alberi instance.
Required argument:
puzzle -- The puzzle to solve, in the form of a string of n*m
letters indicating the regions. The whitespace ' ' can be used
as a placeholder for a cell with no region assigned. The
period '.' can be used to force an empty cell in the solution.
n -- Number of rows
m -- Number of columns
Optional arguments:
per_row -- Number of trees per row. (Default: 2.)
per_column -- Number of trees per column. (Default: 2.)
per_region -- Number of trees per region. (Default: 2.)
random -- True to make a random scheme
"""
self.m = m
self.n = n
self.puzzle = puzzle
REGIONLESS = Alberi.REGIONLESS
VOID = Alberi.VOID
regions = set(self.puzzle).difference(REGIONLESS + VOID)
trees = m * per_column
if trees != n * per_row or (
trees != len(regions) * per_region and len(regions) > 0):
raise ValueError("Bad puzzle instance. '" + puzzle + "'")
def constraints():
for x, y in product(range(m), range(n)):
cell_at_xy = self.puzzle[self.rc2idx(y, x)]
if cell_at_xy != VOID:
yield (y, x), [
('row', y), ('column', x)
] + ([('region', cell_at_xy)]
if cell_at_xy != REGIONLESS else []
) + [
('neighbour', p, q)
for p, q in product(range(x, x+2), range(y, y+2))
if 0 <= p < m and 0 <= q < n
]
def counts():
for x in range(m):
yield ('column', x), per_column
for y in range(n):
yield ('row', y), per_row
for r in regions:
yield ('region', r), per_region
self.solver = ExactCover(dict(constraints()),
counts=dict(counts()),
satisfy=dict(counts()),
random=random)
@staticmethod
def multiline_to_solver_params(puzzle):
"""Construct the set of parameters to call the Alberi constructor.
Required argument:
puzzle -- The puzzle to solve, in the form of a string of n
words, each word consisting of m letters indicating the
regions.
Returns:
puzzle -- A single line representetion of the input
m -- Number of columns
n -- Number of rows
"""
puzzle = puzzle.split()
m = len(puzzle[0])
n = len(puzzle)
puzzle = ''.join(puzzle)
return (puzzle, m, n)
def rc2idx(self, row, col):
"""Return the index of the cell at (row, col)."""
return row * self.m + col
def decode_solution(self, solution):
"""Decode an Alberi solution and return it as a string."""
grid = [
list(self.puzzle[(r*self.m):((r+1)*self.m)])
for r in xrange(self.n)
]
for y, x in solution:
grid[y][x] = grid[y][x].upper()
return '\n'.join(''.join(row) for row in grid)
def solution_to_string(self, solution):
"""Build a single line string for an Alberi solution."""
CELL_OCCUPIED = '*'
CELL_EMPTY = '|'
out = bytearray(CELL_EMPTY * (self.m * self.n))
for y, x in solution:
out[self.rc2idx(y, x)] = CELL_OCCUPIED
return str(out)
def render_board(self, puzzle=None, solution=None):
"""Draw a board for the Alberi problem.
Optional arguments:
puzzle -- If defined overrides self.puzzle (without changing it).
solution -- If defined the 'trees' are drawn inside the board.
"""
CELL_OCCUPIED = '*'
CELL_EMPTY = ' '
m = self.m
n = self.n
if puzzle is None:
puzzle = self.puzzle
lines = [
puzzle[(r * m):((r + 1) * m)]
for r in xrange(n)
]
hdiff = [
[
'|' if p[0] != p[1] else ' '
for p in zip(line[:-1], line[1:])
] + ['|']
for line in lines
]
vdiff = [
[
'---' if lines[r][c] != lines[r+1][c] else ' '
for c in xrange(m)
]
for r in xrange(n-1)
]
vdiff.append(['---' for c in xrange(m)])
if solution is not None:
grid = [
list(CELL_EMPTY * self.m)
for r in xrange(self.n)
]
for y, x in solution:
grid[y][x] = CELL_OCCUPIED
lines = [''.join(row) for row in grid]
out = '+' + '---+' * m
for r in xrange(n):
out += '\n|' + ''.join([
' {0} {1}'.format(q[0], q[1])
for q in zip(lines[r], hdiff[r])
])
out += '\n+' + ''.join([
'{0}+'.format(q)
for q in vdiff[r]
])
return out
def __next__(self):
return next(self.solver)
next = __next__ # for compatibility with Python 2
The AlberiMaker module is where the pieces are glued toghether.
"""Find an Alberi puzzle using a genetic algorithm
"""
from AlberiCover import Alberi
from random import sample
from string import ascii_letters
from collections import defaultdict
from GeneticAlgorithm import GeneticAlgorithm
from AlberiGenetic import AlberiGeneticFactory
from itertools import islice, combinations
def one_per_region_creator(m, n, per_row, per_column, origsol):
"""Creates a single solution Alberi scheme growing regions around the
trees positioned in the coordinates at origsol.
Required argument:
n -- Number of rows
m -- Number of columns
per_row -- Number of trees per row.
per_column -- Number of trees per column.
origsol -- Coordinates of the trees.
"""
size = m * n
REGIONLESS = Alberi.REGIONLESS
ORL = ord(REGIONLESS)
OVOID = ord(Alberi.VOID)
# Assigns a letter to each tree in the original solution
puzzle = bytearray(REGIONLESS * size)
asolver = Alberi(str(puzzle), m, n, per_row, per_column, per_region=1)
for coords, letter in zip(origsol, ascii_letters):
y, x = coords
puzzle[asolver.rc2idx(y, x)] = letter
# Just a debug output to verify that the solution did not change
print(str(puzzle))
asolver = Alberi(str(puzzle), m, n, per_row, per_column, per_region=1)
print(asolver.solution_to_string(next(asolver)))
# An array of neighbour's positions, to speed up calculations
neighbour = []
for idx in range(size):
row, col = divmod(idx, m)
neighbour.append(
[endr * n + col for endr in range(row - 1, row + 2)
if 0 <= endr < m and endr != row] +
[row * n + endc for endc in range(col - 1, col + 2)
if 0 <= endc < n and endc != col]
)
def recurse(puzzle):
"""Backtracking function. Assigns a letter to an empty cell,
neighbouring a cell with a letter assigned, and verify that the
new scheme has only one solution
"""
# Makes a set of neighbours for each empty cell in the puzzle
neighbour_field = [
set(puzzle[idx] for idx in lst
if puzzle[idx] != ORL and puzzle[idx] != OVOID)
for lst in neighbour]
# Sort the list of the neighbours placing first the cells with few
# neighbouring fields and then removes the cells without neighbours
best_list = sorted(enumerate(neighbour_field), key=lambda j: len(j[1]))
best_list = filter(lambda item: len(item[1]) > 0, best_list)
mypuzzle = puzzle[:]
for item in best_list:
best = item[0]
if mypuzzle[best] != ORL:
continue
vals = item[1]
for v in vals:
mypuzzle[best] = v
asolver = Alberi(
str(mypuzzle), m, n, per_row, per_column, per_region=1
)
sols = list(islice(asolver, None, 2))
if len(sols) == 1:
print(str(mypuzzle))
if mypuzzle.count(REGIONLESS) == 0:
yield mypuzzle
else:
for rec_puzzle in recurse(mypuzzle):
yield rec_puzzle
mypuzzle[best] = REGIONLESS
for scheme in recurse(puzzle):
print(asolver.render_board(puzzle=str(scheme)))
yield scheme
def region_factory(m, n, per_row, per_column, per_region, scheme):
"""Joins two or more regions of a one-tree-per-region scheme, and
returns a scheme with per_region trees per region.
The returned scheme usually have more than one solution.
Required argument:
n -- Number of rows
m -- Number of columns
per_row -- Number of trees per row.
per_column -- Number of trees per column.
per_region -- Number of trees per region.
scheme -- Initial scheme. Must be a one-tree-per-region scheme.
"""
if per_region == 1:
yield scheme
return
region_count = m * per_row / per_region
size = m * n
# A dictionary with the region identifier as key and a set of neighbouring
# regions' identifiers as value
neighbour_region = defaultdict(set)
for idx, v in enumerate(scheme):
row, col = divmod(idx, m)
for endr in range(row - 1, row + 2):
if 0 <= endr < m and endr != row:
p = scheme[endr * n + col]
if p == v or p == ord(Alberi.VOID):
continue
neighbour_region[v].add(p)
for endc in range(col - 1, col + 2):
if 0 <= endc < n and endc != col:
p = scheme[row * n + endc]
if p == v:
continue
neighbour_region[v].add(p)
def validate_connectivity(myneighbour):
"""Tests if the graph described in myneighbour is completely connected.
First make the region array with all the indexes of the cells
uncovered. Then do a BFS algorithm to assign a value (weight) to
each cell (in this case is the minimum Manhattan distance from the
first cell in the array). If every cell has been labeled with a
value than the graph is completely connected
"""
region = myneighbour.keys()
if len(region)==0:
return True
home = region[0]
weights = [size+1] * len(region)
weights[region.index(home)] = 0
curlist = [home]
curval = 0
while len(curlist) > 0:
newlist = []
newval = curval + 1
for key in curlist:
for item in myneighbour[key]:
try:
idx = region.index(item)
if weights[idx] > newval:
weights[idx] = newval
newlist.append(item)
except ValueError:
pass
curlist = newlist
curval = newval
if any(item>size for item in weights):
return False
return True
def region_select_recurse(neighbour_region, selection, depth):
"""Depth first search for the groups of regions.
Selects one of the remaining items in the list of neighbours of the
last item selected.
"""
neighbour_idx = [
k for k, q in neighbour_region.iteritems()
if len(q.intersection(selection))>0 and not k in selection]
myneighbour = {
k: q
for k, q in neighbour_region.iteritems()
if k != selection[-1]
}
best_list = sorted(neighbour_idx, key=lambda j: len(myneighbour[j].difference(selection)))
for v in best_list:
if depth == 1:
yield selection + (v,)
return
if len(myneighbour[v]) == 0:
continue
for p in region_select_recurse(myneighbour, selection + (v,), depth - 1):
yield p
def super_region_recurse(neighbour_region, super_regions):
"""Backtracking function. For each region take some element in the
set of neighbouring regions and mark these items as a super-region
"""
best_list = sorted(
neighbour_region,
key=lambda j: len(neighbour_region[j]))
for v in best_list:
no_group = True
if len(neighbour_region[v]) == 0:
return
for p in region_select_recurse(neighbour_region, (v,), per_region - 1):
no_group = False
myneighbour = {
k: q.difference(p)
for k, q in neighbour_region.iteritems() if k != v and k not in p
}
if not validate_connectivity(myneighbour):
continue
mysuper_regions = super_regions + [p]
if len(mysuper_regions) == region_count:
yield mysuper_regions
else:
for out in super_region_recurse(myneighbour, mysuper_regions):
yield out
if no_group:
return
for super_region in super_region_recurse(neighbour_region, []):
translator = bytearray(256)
for c, l in zip(super_region, ascii_letters):
for v in c:
translator[v] = l
translator[ord(Alberi.VOID)] = Alberi.VOID
scheme2 = scheme.translate(translator)
print(str(scheme2))
yield scheme2
def reduce_scheme(m, n, per_row, per_column, per_region, scheme3, origsol):
"""Blanks as much cell as is possible in a region keeping the trees
in origsol connected by a strip of cells.
The returned scheme usually have more than one solution.
Required argument:
n -- Number of rows
m -- Number of columns
per_row -- Number of trees per row.
per_column -- Number of trees per column.
per_region -- Number of trees per region.
scheme3 -- Initial scheme. Must be a one-tree-per-region scheme.
origsol -- Positions of the trees.
"""
if per_region == 1:
for idx in range(len(scheme3)):
if divmod(idx, m) not in origsol:
scheme3[idx] = Alberi.REGIONLESS
return
size = m * n
for letter in set(scheme3):
region = [divmod(idx, m) for idx, value in enumerate(scheme3) if value == letter]
pivots = set(region).intersection(origsol)
# Uses Dijkstra algorithm to find the best path between the cells.
# home is the first of the trees, weights is a list of the distances
# from home, origin is the previous cell in the best path. curlist
# holds the array of the cells to test in the next iteration.
home = pivots.pop()
weights = [size+1] * len(region)
origin = [None] * len(region)
weights[region.index(home)] = 0
curlist = [home]
curval = 0
while any(weights[region.index(pivot)] > size for pivot in pivots):
newlist = []
newval = curval + 1
for r, c in curlist:
for cell in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
try:
idx = region.index(cell)
if weights[idx] > newval:
weights[idx] = newval
origin[idx] = (r, c)
newlist.append(cell)
except ValueError:
pass
curlist = newlist
curval = newval
path = set()
for pivot in pivots:
path.add(pivot)
while origin[region.index(pivot)]:
pivot = origin[region.index(pivot)]
path.add(pivot)
for idx, l in enumerate(scheme3):
if l == letter:
cell = divmod(idx, m)
if cell in path:
continue
scheme3[idx] = Alberi.REGIONLESS
def make_it(m, n, per_row, per_column, per_region):
"""Creates a single solution Alberi scheme.
This function find the solution using the following sub-steps:
* Create a solution vector with the desired trees per row and column.
* Create a single-tree-per-region puzzle around these solutions.
* Group the regions of this puzzle to have super-regions with enough
trees per region.
* Leave only a strip of cells joining the solution cells to ensure having
a single solution puzzle. The remaining cells become REGIONLESS.
* Evolve this scheme decreasing the number of REGIONLESS cells while
mantaining a single solution for the result.
* When the scheme has no more REGIONLESS cells, return it.
Required argument:
n -- Number of rows
m -- Number of columns
per_row -- Number of trees per row.
per_column -- Number of trees per column.
per_region -- Number of trees per region.
"""
size = m * n
alberiGeneticFactory = AlberiGeneticFactory(
m, n,
per_row, per_column, per_region)
alberiGenetic = GeneticAlgorithm(
alberiGeneticFactory.individual_function(),
alberiGeneticFactory.fitness_function(),
alberiGeneticFactory.mutate_function(),
alberiGeneticFactory.crossover_function())
target = 0
p_count = 40
asolver = Alberi('a' * size, m, n, per_row, per_column, m * per_row, True)
origsol = next(asolver)
one_per_region = one_per_region_creator(m, n, per_row, per_column, origsol)
for scheme in one_per_region:
for scheme3 in region_factory(m, n, per_row, per_column, per_region, scheme):
str_scheme = str(scheme3)
print(asolver.render_board(puzzle=str_scheme, solution=origsol))
reduce_scheme(m, n, per_row, per_column, per_region, scheme3, origsol)
print(str(scheme3))
lst = [idx for idx, cell in enumerate(scheme3) if cell != ord(Alberi.REGIONLESS)]
print(asolver.render_board(puzzle=str_scheme, solution=[divmod(idx, m) for idx in lst]))
p = alberiGenetic.population(p_count, str(scheme3))
fitness_history = [alberiGenetic.grade(p, target),]
while alberiGenetic.fitness(p[0], target) > 0:
p = alberiGenetic.evolve(p, target)
population_grade = alberiGenetic.grade(p, target)
fitness_history.append(population_grade)
print('{0} {1} {2}'.format(str(p[0]), p[0].count(' '), population_grade))
if population_grade == size:
break
else:
return str(p[0])
if __name__ == '__main__':
m = n = 9
per_row = 2
per_column = 2
per_region = 2
asolver = Alberi('a' * (m * n), m, n, per_row, per_column, m * per_row)
puzzle = make_it(m, n, per_row, per_column, per_region)
print(asolver.render_board(puzzle=puzzle))
In this module two iterators are defined: one_per_region and region_factory.
The first one takes the solutions of a regionless puzzle and grow regions around those cells, keeping a single solution for the puzzle.
The second one takes the regions from the former and take groups of regions to make super-regions that will accomodate more than a tree.
This step is needed only to group solutions, in fact, in the reduce_scheme function, we keep only a strip of cells connecting the solutions of the original scheme.
Now we (should) have a single-solution-multi-tree-per-region puzzle, with many holes inside.
Here it cames the genetic algorithm: we feed this puzzle as the seed for the individuals and let the population evolve.
Everything I described is implemented in the make_it function, that takes only the carachteristics of the puzzle and (hopefully) outputs a complete puzzle.
Everything is fine you say? Well, the time for a 12 by 12 scheme like the one in the first post is about 24 hours. The number of puzzles tested to find it is not so large: in one of the tests I measured 6935 tentatives (after memoization of the fitness), so the bottleneck is still the puzzle solver. Maybe a change can be made to the ExactCover to solve more than one puzzle at the same time, maybe accepting a topology change after a solution is found... but this would be a really hard task.
Other problems are
- sometimes, the creation of the starting solution vector is too long (maybe the random parameter is not so good for
ExactCover); - sometimes the
region_factoryrecursion seem to get into a neverending loop (we need some euristic for the task).
Any suggestions are very welcome... squeeze your brains and let me know!!
PS. I must credit Will Larson for his genetic algorithm implementation. Sorry for the delay but I lost the source link.
