5
\$\begingroup\$

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_factory recursion 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.

\$\endgroup\$
2
\$\begingroup\$

Your code looks good, well organised and well documented.

Here are a few details that you could probably improve (I haven't read the whole code).

float division

I assume summed / (len(pop) * 1.0) is just a hacky way to get a float division. Float division is the default behavior in Python 3 (you use // for integer division).

Thus, a probably clearer way to have what you want is to use : from __future__ import division .

Sort with key

The following code is quite confusing :

    graded = [(self.fitness(x, target), x) for x in pop]
    graded = [x[1] for x in sorted(graded)]

I guess you are trying to get elements from pop sorted by their fitness by constructing tuples, sorting them and then retrieving the initial element from the tuple.

Good new, the sorted function has a parameter key to do exactly this.

graded = sorted(pop, key=lambda e: fitness(e, target))

(This is not tested)

Try except pass

This piece of code

                        try:
                            whatever
                        except:
                            pass

gave me shivers.

You should (almost) always specify the type of Exception you are trying to catch. Also, there is usually no good reason to pass on exception catching. More about this : Why is “except: pass” a bad programming practice?, The Most Diabolical Python Antipattern .

Consistent documentation

Your function docstrings use both imperative mode ("do something") and declarative mode ("does something").

As a side-note, PEP 257 suggests :

The docstring is a phrase ending in a period. It prescribes the function or method's effect as a command ("Do this", "Return that"), not as a description; e.g. don't write "Returns the pathname ...".

(And I think that pep257 tries to detect this).

Looping over a grid

    self.m = m
    self.n = n
    self.size = size = m * n

    for idx in range(size):
        row, col = divmod(idx, m)
        ...

Seems a bit unnatural. You know the two dimensions of a grid and you want to iterate over all cells. The natural (yet verbose) way to do so is probably to have 2 nested loops but you are using some mathematical trick in order to have a simple loop.

You might like to know that itertools offers a solution to this exact problem : itertools.product.

It works like this :

>>> n, m = 2, 3
>>> [divmod(i, m) for i in range(n*m)]
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)]
>>> list(itertools.product(range(n), range(m)))
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)]
\$\endgroup\$
  • \$\begingroup\$ Thank you for your valuable help. About the try/except, do your complains refer to the one in mutate_individual, or do you also think the except ValueError are a bad habit? \$\endgroup\$ – N74 Dec 21 '15 at 16:25
  • 1
    \$\begingroup\$ I was thinking about with no exception type provided. \$\endgroup\$ – Josay Dec 21 '15 at 16:26
  • \$\begingroup\$ OK, I agree with you... You managed to spot the only one I missed while reviewing the code. \$\endgroup\$ – N74 Dec 21 '15 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.