4
\$\begingroup\$

This is a follow-up to this question.

Using his ExactCover class, I slightly modified Garth Rees' Alberi class to cope with regionless schemes and forced void cells:

"""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

    """
    WHITESPACE = ' '
    PERIOD = '.'

    def __init__(self, puzzle, m, n, per_row=2, per_column=2, per_region=2):
        """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.)

        """
        self.m = m
        self.n = n
        self.puzzle = puzzle
        WHITESPACE = Alberi.WHITESPACE
        PERIOD = Alberi.PERIOD
        WP = WHITESPACE+PERIOD

        regions = set(self.puzzle).difference(WP)
        trees = m * per_column
        if trees != n * per_row or (
                trees != len(regions) * per_region and len(regions) > 0):
            raise ValueError("Bad puzzle instance.")
        def constraints():
            for x, y in product(range(m), range(n)):
                if self.puzzle[self.rc2idx(y, x)] != PERIOD:
                    yield (y, x), [
                        ('row', y), ('column', x)
                    ] + ([('region', self.puzzle[self.rc2idx(y, x)])]
                        if self.puzzle[self.rc2idx(y, x)] not in WP 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()))

    @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, r, c):
        return r * self.m + c

    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_UNKNOWN = '?'
        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

I also made a nicer output method (render_board) to have a 2D rendering of the board. This is a 16X16 3 trees per row and per column and 1 tree per region puzzle:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| L   L   L   L | G   G   G | y | z   z   z   z   z | K   K   K |
+   +   +   +---+   +   +   +   +---+   +   +   +---+   +   +   +
| L   L   L | h | G   G   G | y   y | z   z   z | w | K   K   K |
+---+   +---+   +---+   +---+   +   +   +   +   +   +---+---+---+
| m | L | h   h   h | G | y   y   y | z   z   z | w   w | P | l |
+   +---+   +   +   +---+---+---+---+   +   +---+---+---+   +---+
| m   m | h   h   h   h | b | k   k | z   z | j | P   P   P   P |
+   +---+---+   +   +   +---+---+---+---+---+---+   +   +   +---+
| m | T   T | h   h   h   h | c   c | v   v | P   P   P   P | R |
+   +   +   +   +   +   +---+   +---+---+   +---+   +   +---+   +
| m | T   T | h   h   h | c   c | n   n | v   v | P   P | R   R |
+   +---+---+---+   +---+   +---+   +---+   +---+---+---+   +   +
| m | M | i   i | h | d | c | n   n | C | v | N   N   N | R   R |
+---+   +   +   +   +   +---+---+---+   +---+---+---+---+   +   +
| M   M | i   i | h | d   d   d | C   C   C | u   u | R   R   R |
+   +---+---+   +---+   +   +---+---+---+---+---+---+---+   +   +
| M | S   S | i | e | d   d | E   E | s   s   s | O   O | R   R |
+   +---+   +   +   +---+---+   +---+   +   +---+---+   +---+   +
| M | q | S | i | e   e   e | E | s   s   s | t | r | O | p | R |
+   +   +---+---+   +   +   +---+   +   +   +---+   +---+   +---+
| M | q   q | g | e   e   e   e | s   s   s | r   r | p   p   p |
+---+   +---+---+---+---+   +   +---+   +   +   +   +---+   +---+
| V | q | U   U | f   f | e   e | o | s   s | r   r   r | p | Q |
+   +---+   +   +---+   +---+---+   +---+---+   +   +   +---+   +
| V | U   U   U | F | f   f | D | o   o | r   r   r   r   r | Q |
+   +---+   +   +   +---+---+   +---+---+---+---+---+   +---+   +
| V | I | U   U | F | a   a | D | B | A   A | x   x | r | Q   Q |
+   +   +   +   +---+   +   +---+   +---+---+   +   +---+---+   +
| V | I | U   U | H | a   a   a | B   B | x   x   x   x | J | Q |
+---+   +---+---+   +---+   +   +---+   +   +   +   +   +---+   +
| I   I   I   I | H   H | a   a   a | B | x   x   x   x   x | Q |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

At the moment the creator part comes in two steps. starting_grid creates a scheme with forced empy cells but with no regions which has only one solution:

def starting_grid(m, n, per_row, per_column, fraction=0.5):
    """Creates a regionless Alberi scheme with a single 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.

    Optional arguments:
    fraction -- Fraction of void cells for the first iteration
    """
    size = m * n

    WHITESPACE = Alberi.WHITESPACE
    PERIOD = Alberi.PERIOD

    n_of_sols = 0
    while n_of_sols <> 1:
        if n_of_sols == 0:
            n_of_void = int(size * fraction)
            puzzle = ''.join(sample(
                PERIOD * n_of_void +
                WHITESPACE * (size - n_of_void), size
            ))
        asolver = Alberi(puzzle, m, n, per_row, per_column, per_region=1)
        print(puzzle)
        sols = [x for _, x in zip(xrange(2), asolver)]
        n_of_sols = len(sols)
        if n_of_sols > 1:
            diff = [idx
                for idx, s in enumerate(zip(
                    asolver.solution_to_string(sols[0]),
                    asolver.solution_to_string(sols[1])
                ))
                if s[0] != s[1]
            ]
            new_void = sample(diff, 1)[0]
            puzzle = puzzle[:new_void] + PERIOD + puzzle[new_void+1:]

    print(asolver.solution_to_string(sols[0]))
    return sols[0]

The second step assigns a letter to each tree in the solution from starting_grid and grow fields around these letters:

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
    WHITESPACE = Alberi.WHITESPACE
    PERIOD = Alberi.PERIOD
    OWS = ord(WHITESPACE)

    # Assigns a letter to each tree in the original solution
    puzzle = bytearray(WHITESPACE * 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 xrange(size):
        neighbour.append([])
        row, col = divmod(idx, n)
        for endr in range(row - 1, row + 2):
            if 0 <= endr < m and endr != row:
                neighbour[idx].append(endr * n + col)
        for endc in range(col - 1, col + 2):
            if 0 <= endc < n and endc != col:
                neighbour[idx].append(row * n + endc)

    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] != OWS)
            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] != OWS:
                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 = [x for _, x in zip(xrange(2), asolver)]
                l = len(sols)
                if l == 1:
                    print str(mypuzzle)
                    if mypuzzle.count(WHITESPACE) == 0:
                        yield mypuzzle
                    else:
                        for rec_puzzle in recurse(mypuzzle):
                            yield rec_puzzle
            mypuzzle[best] = WHITESPACE

    scheme = next(recurse(puzzle))
    print asolver.render_board(puzzle=str(scheme))
    return scheme

I am quite satisfied of how these functions work. But any comment/suggestion is welcome to improve their style/performances.

What I intended to do was to join these fields to have multi-tree regions, but I managed to have only puzzles with more than 10 solutions (only in one run I had a puzzle with four solutions, but I didn't manage, by hand, to reduce the number of solutions). I'm still trying to find a way to generate multi-tree-per-region puzzles.


EDIT

Dear friends, today I put on my young Frankenstein hat an, with a genetic algorithm...

It could work!! (cit.)

This is the first Alberi puzzle with 2 trees per region:

+---+---+---+---+---+---+---+---+---+---+---+---+
| h   h   h | i | k   k   k   k | e   e   e   e |
+   +---+---+   +---+---+---+   +---+   +   +   +
| h | j   j | i   i   i   i | k   k | e   e   e |
+   +---+   +---+---+   +---+---+---+   +   +   +
| h   h | j   j | f | i | e   e   e   e   e   e |
+   +   +---+---+   +---+   +---+---+   +---+   +
| h   h   h | f   f | e   e | d   d | e | d | e |
+---+---+   +   +---+---+---+   +   +---+   +   +
| f   f | h | f | d   d   d   d   d   d   d | e |
+   +   +---+   +---+---+---+   +---+   +   +---+
| f   f   f   f   f   f   f | d | f | d   d   d |
+   +---+   +   +---+---+   +---+   +   +   +---+
| f | b | f   f | b   b | f   f   f | d   d | a |
+   +   +---+---+---+   +---+---+---+   +---+   +
| f | b | g   g   g | b | l   l   l | d | a   a |
+---+   +   +---+---+   +   +---+---+   +---+   +
| b   b | g | b   b   b | l | b | d   d | c | a |
+   +   +   +   +   +   +---+   +---+---+   +   +
| b   b | g | b   b   b   b   b   b | c   c | a |
+   +   +---+   +---+---+   +   +---+   +---+   +
| b   b   b   b | a   a | b   b | c   c | a   a |
+   +   +   +---+   +   +---+---+---+---+   +   +
| b   b   b | a   a   a   a   a   a   a   a   a |
+---+---+---+---+---+---+---+---+---+---+---+---+

More details to come, next week!

\$\endgroup\$
3
\$\begingroup\$

I wonder why starting_grid returns only the solution and not the puzzle. I think the locations of the forced empty cells would be useful: you could first grow regions into the whitespace, without checking uniqueness of solution at this stage. The forced cells maintain uniqueness until you start joining them into regions.

Alternatively, if you don't need starting_grid to return the puzzle, you could take advantage of the random parameter of the solver and return a random solution.

\$\endgroup\$
  • \$\begingroup\$ You hit a good point... right now I was trying to use the empty cells to join the trees. I didn't realize that filling the whitespace can be done without checking. \$\endgroup\$ – N74 Nov 3 '15 at 16:57
2
\$\begingroup\$
  1. The following features are not portable to Python 3: the operator <>, the print statement, the mixing of strings and bytes, and the xrange function.

  2. sample is not defined anywhere. Presumably there is a missing import:

    from random import sample
    
  3. It's kind of pointless having something named after its value, like

    PERIOD = '.'
    

    If you wanted to change this to a comma, you'd be faced with a choice between:

    PERIOD = ','
    

    which is absurd, and:

    COMMA = ','
    

    which requires all occurrences of PERIOD in the rest of the code to be changed. It would be better to name it after its purpose, for example:

    VOID = '.'
    
  4. For similar reasons, I'd call WHITESPACE something like EMPTY or REGIONLESS and WP something like NONREGION.

  5. CELL_UNKNOWN is not used anywhere.

  6. Constants like PERIOD and CELL_OCCUPIED and so on should be global variables. This would save you from having inconsistent copies in different places.

  7. Adding special cases for regionless puzzles in the Alberi solver leads to complex code.

    An alternative approach is to leave the solver alone and modify the caller. For example, instead of:

    puzzle = bytearray(WHITESPACE * size)
    asolver = Alberi(str(puzzle), m, n, per_row, per_column, per_region=1)
    

    pass a single region containing all the trees:

    puzzle = bytearray(b'a' * size)
    asolver = Alberi(puzzle, m, n, per_row, per_column, per_region=n*per_row)
    
  8. In constraints the value self.puzzle[self.rc2idx(y, x)] is computed three times. It could be cached in a local variable.

  9. The name rc2idx is hard to understand. Presumably it means "row and column to index", so something like cell_index would be good. A docstring would help too.

  10. Since you sample the whole array, it would be clearer to use random.shuffle:

    >>> a = bytearray(b'abcdef')
    >>> shuffle(a)
    >>> a
    bytearray(b'cdfeba')
    
  11. Instead of:

    sols = [x for _, x in zip(xrange(2), asolver)]
    

    use itertools.islice:

    sols = list(islice(asolver, None, 2))
    
  12. Instead of:

    new_void = sample(diff, 1)[0]
    puzzle = puzzle[:new_void] + VOID + puzzle[new_void+1:]
    

    use random.choice:

    puzzle[choice(diff)] = ord(VOID)
    
  13. Instead of:

    diff = [idx
        for idx, s in enumerate(zip(
            asolver.solution_to_string(sols[0]),
            asolver.solution_to_string(sols[1])
        ))
        if s[0] != s[1]
    ]
    

    write:

    diff = [i for i, (s0, s1)
            in enumerate(zip(*map(asolver.solution_to_string, sols)))
            if s0 != s1]
    
  14. As Janne says in his answer, the code only uses starting_grid to produce a random regionless configuration. (It immediately forgets the forced-void cells.) In which case, why not use the random keyword argument to the ExactCover solver? Then it would be possible to generate a random starting grid like this:

    next(Alberi(b'a' * (m * n), m, n, per_row, per_column,
                per_region=n*per_row, random=True))
    
\$\endgroup\$
0
\$\begingroup\$

First some notes on your starting_grid. Instead of using n_of_ to mean number of, count would be more intuitive. solution_count is much clearer to read.

You could save a bit of time at the end by temporarily assigning sols[0] so you can pass it both to the solution function and then return it.

solution = sols[0]
print(asolver.solution_to_string(solution)
return solution

In one_per_region_creator, instead of your two loops to append to neighbour[idx] you could use list comprehensions and add them to neighbour.

    row, col = divmod(idx, n)
    neighbour[idx] += [endr * n + col for endr in range(row - 1, row + 2)
                       if 0 <= endr < m and endr != row]
    neighbour[idx] += [row * n + endc for endc in range(col - 1, col + 2)
                       if 0 <= endc < n and endc != col]

In recurse you story len(sols) just to use it once, instead test if len(sols) == 1 directly.

\$\endgroup\$

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.