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.
