12
\$\begingroup\$

Since I while ago I've been addicted to a number-game that you can think of as a binary Sudoku. The game is called (in Italian) Alberi (trees) and I haven't found any equivalent when searching the internet.

example

The purpose of the game is to find where the trees are placed. The rules (that may vary with the puzzle) are that you must have 2 trees for each row, 2 for each column and 2 for each colored field.
In addition a tree cannot be placed in the 8 cells surrounding another tree.

You can think of it as a particular 8-queens game, where you have towers and each tower can see only one other tower.

The magazine that used to publish those schemes isn't issued any more, so I'm trying to make a generator for these puzzles.

First of all I needed a solver. This is what I have so far:

CELL_UNKNOWN=63
CELL_OCCUPIED=42
CELL_EMPTY=124

class AlberiSolver(object):

    def __init__(self, numr, numc, strfields, cpr, cpc, cpf):
        self.numr=numr
        self.numc=numc
        self.rows=[[c+r*numc for c in range(numc)] for r in range(numr)]
        self.cols=[[c+r*numc for r in range(numr)] for c in range(numc)]
        strfidx=set(strfields).difference('.').difference([46])
        self.fields=[[r for r,v in enumerate(strfields) if v==c]
                                                              for c in strfidx]
        self.surround=[self.get_surround(numr,numc,p)
                                                     for p in range(numr*numc)]
        self.cpr=cpr
        self.cpc=cpc
        self.cpf=cpf
        self.solu=bytearray(numr*numc)
        for p,v in enumerate(strfields):
            if v=='.':
                self.solu[p]=CELL_EMPTY
            else:
                self.solu[p]=CELL_UNKNOWN

    @staticmethod
    def check_groups_and_cover_cells(groups, group_mask, maxels, pos, mysol):
        for group, gm in zip(groups, group_mask):
            if gm==1:
                continue
            if pos in group:
                count=sum(1 for q in group if mysol[q]==CELL_OCCUPIED)
                unkn=sum(1 for q in group if mysol[q]==CELL_UNKNOWN)
                if count>maxels or (count+unkn)<maxels:
                    return False
                if count==maxels:
                    for q in group:
                        if mysol[q]==CELL_UNKNOWN:
                            mysol[q]=CELL_EMPTY
                return True

    @staticmethod
    def check_groups(groups, group_mask, maxels, mysol):
        for idx, group in enumerate(groups):
            if group_mask[idx]==1:
                continue
            count=sum(1 for q in group if mysol[q]==CELL_OCCUPIED)
            unkn=sum(1 for q in group if mysol[q]==CELL_UNKNOWN)
            if (count+unkn)<maxels:
                return False
            if (count==maxels) and (unkn==0):
                group_mask[idx]=1
        return True

    @staticmethod
    def check_surround_and_cover_cells(surrounding, solu):
        for q in surrounding:
            if solu[q]==CELL_OCCUPIED:
                return False
            if solu[q]==CELL_UNKNOWN:
                solu[q]=CELL_EMPTY
        return True

    @staticmethod
    def get_surround(numr, numc, p):
        q=[]
        cy, cx=divmod(p, numc)
        for dx in range(-1,2):
            for dy in range(-1,2):
                if dx!=0 or dy!=0:
                    x=dx+cx; y=dy+cy
                    if 0<=x<numc and 0<=y<numr:
                        q.append(y*numc+x)
        return q

    def recurse(self, solu, row_mask, col_mask, field_mask):
        if all(s!=CELL_UNKNOWN for s in solu):
            for row in self.rows:
                count=sum(1 for q in row if solu[q]==CELL_OCCUPIED)
                if count!=self.cpr:
                    return
            for col in self.cols:
                count=sum(1 for q in col if solu[q]==CELL_OCCUPIED)
                if count!=self.cpc:
                    return
            for field in self.fields:
                count=sum(1 for q in field if solu[q]==CELL_OCCUPIED)
                if count!=self.cpf:
                    return
            yield solu
        for p,v in enumerate(solu):
            if v==CELL_UNKNOWN:
                mysol=solu[:]
                myrm=row_mask[:]
                mycm=col_mask[:]
                myfm=field_mask[:]
                if not self.check_groups(self.rows, myrm, self.cpr, mysol):
                    break
                if not self.check_groups(self.cols, mycm, self.cpc, mysol):
                    break
                if not self.check_groups(self.fields, myfm, self.cpf, mysol):
                    break
                mysol[p]=CELL_OCCUPIED
                if not self.check_surround_and_cover_cells(
                                                      self.surround[p], mysol):
                    solu[p]=CELL_EMPTY
                    continue
                if not self.check_groups_and_cover_cells(
                                          self.rows, myrm, self.cpr, p, mysol):
                    solu[p]=CELL_EMPTY
                    continue
                if not self.check_groups_and_cover_cells(
                                          self.cols, mycm, self.cpc, p, mysol):
                    solu[p]=CELL_EMPTY
                    continue
                if not self.check_groups_and_cover_cells(
                                        self.fields, myfm, self.cpf, p, mysol):
                    solu[p]=CELL_EMPTY
                    continue
                for sol in self.recurse(mysol, myrm, mycm, myfm):
                    yield sol
                solu[p]=CELL_EMPTY
        return

    def solve(self):
        solu=self.solu[:]
        row_mask=[0 for g in self.rows]
        col_mask=[0 for g in self.cols]
        field_mask=[0 for g in self.fields]
        for s in self.recurse(solu,row_mask,col_mask,field_mask):
            yield s

if __name__=='__main__':
    strfields='aabbbcccccccaccccccdddeeaccfcfdddgeeafffffddggeeaafffdddggeeafffddddgggghffffdiijjjjhffffiiikkkkhhhfiiiiiklkhhhffiilllllhhhffiilllllhhhfffilllll'
    alberiSolver=AlberiSolver(12,12,strfields,2,2,2)
    print strfields
    for sol in alberiSolver.solve():
        print sol

The code is not commented but it should be easy to understand:

  1. In strfields we have a representation of the board where, for each field we have a different letter.
  2. With strfields we create a solver with 12 rows, 12 columns, 2 trees per row, 2 trees per column, 2 trees per field.
  3. The constructor makes some array of indexes in the solution, representing the rows, the columns and the fields.
  4. The solver is a recursive backtracing algorithm in which each cell is tested for the tree.
  5. If we consume all the cells and the rules are respected, we find a solution.

The output is:

C:\code\Alberi>python AlberiTest.py
aabbbcccccccaccccccdddeeaccfcfdddgeeafffffddggeeaafffdddggeeafffddddgggghffffdiijjjjhffffiiikkkkhhhfiiiiiklkhhhffiilllllhhhffiilllllhhhfffilllll
||*|*|||||||||||||*||||*||*||||||*||*|||||*|||||||||||||*|*|*|||*|||||||||||||||*|*||||*|*|||||||||||||||*|*|*|||||*|||||||*|*|||||||*|||||*||||

...after 7 seconds.

My worry is that, using it in the game creation loop, I'll have to wait for days to have a new scheme. So what I'm looking for is a way to speed-up this algorithm so that it can solve a scheme in few milliseconds. I was also looking into coverage algorithms (dancing links), but I didn't find a way to represent this problem for the Knuth algorithm.

If you want some more schemes, you can find them here.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! This is fascinating! Hopefully I can help with a review. Do you happen to have any examples with their solution? It'd be even easier to follow the rules that way. \$\endgroup\$ – SuperBiasedMan Oct 23 '15 at 14:50
  • \$\begingroup\$ I'm pretty sure that my Minesweeper Analysis code is written flexible enough to be able to solve these puzzles. I'd recommend that you check out my approach. \$\endgroup\$ – Simon Forsberg Oct 28 '15 at 11:08
7
\$\begingroup\$

1. Review

  1. There are no docstrings. What does your AlberiSolver class do? How should I construct an instance? What arguments do I pass? The text from your post would be a good start for a docstring.

  2. The code does not work in Python 3 because of the use of the print function. It would be easy to make it portable by writing print(strfields) and so on.

  3. The input and output are hard to read. It’s often a good idea to format data so that it can be read and checked by humans. If some other form is more convenient for processing, let the computer do the work: rote transformations like this are the kind of thing that computers are good at.

    I would suggest taking input as whitespace-separated words, so that your example puzzle would be represented by the string:

    puzzle = '''
    aabbbccccccc
    accccccdddee
    accfcfdddgee
    afffffddggee
    aafffdddggee
    afffddddgggg
    hffffdiijjjj
    hffffiiikkkk
    hhhfiiiiiklk
    hhhffiilllll
    hhhffiilllll
    hhhfffilllll
    '''
    

    For output, Holroy’s suggestion of using capital letters for the trees is a good idea: this makes it straightforward to check that the region constraints are being met.

  4. The constructor takes arguments numr and numc but if the input were formatted as described above, then it would be possible to compute these values from the input, saving the caller having to specify them.

  5. The arguments cpr, cpc, cpf are obscurely named. Does ‘cpr’ mean ‘choices per row’ or ‘choices per region’? What does ‘cpf’ mean? Names of arguments are parts of a class’s public interface, so they need to be clear.

  6. It would make sense for cpr, cpc, and cpf to have default values.

  7. There’s no check on the values in the input. For the problem to be solvable, it needs to be the case that numr*cpr, numc*cpc, and the number of regions times cpf, are all equal.

2. Representing as an exact cover instance

You wrote:

I was also looking into coverage algorithms (dancing links), but I didn’t find a way to represent this problem for the Knuth algorithm [that is, Algorithm X — GDR].

There are ‘gadgets’ (which I’ll describe below) that you can use to represent Alberi puzzles as exact cover instances. Unfortunately, gadgets tend to result in ‘blow-up’: the problem becomes several times bigger because many exact cover constraints are needed to represent one constraint in the Alberi problem, and so solutions take many times longer to find.

Recall that an exact cover problem consists of a collection of ‘choices’ each of which satisfies a set of ‘constraints’. The goal is to pick a subset of choices so that each constraint is satisfied exactly once.

In an Alberi puzzle, we need to have two trees in each row. We can represent this by pairs of constraints: ‘first tree in row \$y\$’ and ‘second tree in row \$y\$’. Similarly, we need to have two trees in each column and each region, so we need more pairs of constraints. The consequence of this is that the placement of a tree at \$x, y\$ (which is in region \$r\$) has to be represented by eight choices, each of which satisfies three constraints:

  1. First in row \$x\$, first in column \$y\$, first in region \$r\$.
  2. Second in row \$x\$, first in column \$y\$, first in region \$r\$.

  1. Second in row \$x\$, second in column \$y\$, second in region \$r\$.

The next problem is that trees are not allowed to be neighbours. We represent this by adding a constraint \$N(x,y)\$ for each grid cell \$x,y\$, with the meaning ‘there is at most one tree in this cell or the cells to the north, west and north-west’. Then the placement of a tree at \$x, y\$ satisfies (up to) four constraints: \$N(x,y)\$, \$N(x+1,y)\$, \$N(x,y+1)\$, \$N(x+1,y+1)\$. (Some of these might be off the grid and so not needed.) Two trees can’t be adjacent because they would both satisfy at least one constraint:

This gadget prevents trees being adjacent, but it creates a problem: an exact cover solution has to satisfy all the constraints. The \$2n\$ trees satisfy \$8n\$ of the neighbour contraints. But what about the remaining neighbour constraints? We’ll have to introduce additional choices to use up any remaining neighbour constraints: for each constraint \$N(x, y)\$ we’ll add an (otherwise meaningless) choice that satisies it.

So, if using the exact cover solver from here, we can represent the problem like this:

from collections import Iterator
from itertools import product

class Alberi(Iterator):
    """An iterator that yields the solutions to an Alberi problem.

    >>> puzzle = ' '.join('abcd'[i] * 4 for i in range(4))
    >>> solutions = Alberi(puzzle, per_row=1, per_column=1, per_region=1)
    >>> print(sorted(solutions)[0])
    aAaa
    bbbB
    Cccc
    ddDd

    """
    def __init__(self, puzzle, 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
            words, each word consisting of m letters indicating the
            regions.

        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.puzzle = puzzle.split()
        self.m = m = len(self.puzzle[0])
        self.n = n = len(self.puzzle)
        regions = set.union(*map(set, self.puzzle))
        trees = m * per_column
        if trees != n * per_row or trees != len(regions) * per_region:
            raise ValueError("Bad puzzle instance.")
        def constraints():
            for x, y, i, j, k in product(range(m), range(n),
                                         range(per_row),
                                         range(per_column),
                                         range(per_region)):
                # Plant a tree at x, y that's the ith tree in its row,
                # the jth tree in its column and the kth tree in its
                # region.
                yield ('tree', x, y, i, j, k), [
                    ('row', i, y),
                    ('column', j, x),
                    ('region', k, self.puzzle[y][x]),
                ] + [
                    ('neighbour', p, q)
                    for p, q in product(range(x, x+2), range(y, y+2))
                    if 0 <= p < m and 0 <= q < n
                ]
            for x, y in product(range(m), range(n)):
                # Dummy choices to satisfy any leftover neighbour
                # constraints.
                yield ('dummy', x, y), [('neighbour', x, y)]
        self.solver = ExactCover(dict(constraints()))

    def _decode_solution(self, solution):
        """Decode an Alberi solution and return it as a string."""
        grid = list(map(list, self.puzzle))
        for choice in solution:
            if choice[0] == 'tree':
                _, x, y, _, _, _ = choice
                grid[y][x] = grid[y][x].upper()
        return '\n'.join(''.join(row) for row in grid)

    def __next__(self):
        return self._decode_solution(next(self.solver))

    next = __next__             # for compatibility with Python 2

But this solver is disastrously slow. It takes many minutes to solve your example puzzle.

3. Modifying the exact cover solver

However, all is not lost: it is relatively straightforward to modify an exact cover solver so that it requires some constraints to be satisfied multiple times (the row, column and region constraints) and doesn’t require some constraints to be satisfied at all (the neighbour constraints).

Here’s the revised solver:

from collections import Counter, Iterator, defaultdict
from random import shuffle

class ExactCover(Iterator):
    """An iterator that yields solutions to an EXACT COVER problem.

    An EXACT COVER problem consists of a set of "choices". Each choice
    satisfies one or more "constraints". Choices and constraints may
    be represented by any hashable Python objects, with the proviso
    that all choices must be distinct, as must all constraints.

    A solution is a list of choices such that each constraint is
    satisfied by exactly one of the choices in the solution.

    Required argument:
    constraints -- A map from each choice to an iterable of
        constraints satisfied by that choice.

    Optional arguments:
    initial -- An iterable of choices that must appear in every
        solution. (Default: no choices.)
    random -- Generate solutions in random order? (Default: False.)
    counts -- Map from constraint to the number of times that
        constraint must be satisfied. (By default all constraints must
        be satisfied exactly once.)
    satify -- Iterable of contraints that must be satisfied. (Default:
        all constraints.)

    For example:

        >>> data = dict(A = [1, 4, 7],
        ...             B = [1, 4],
        ...             C = [4, 5, 7],
        ...             D = [3, 5, 6],
        ...             E = [2, 3, 6, 7],
        ...             F = [2, 7])
        >>> sorted(next(ExactCover(data)))
        ['B', 'D', 'F']

    By passing a counts dictionary you can require that some
    constraints are satisfied multiple times. In this example we
    require that constraint 7 is satisfied exactly twice:

        >>> sorted(next(ExactCover(data, counts={7: 2})))
        ['A', 'D', 'F']

    If only some constraints must be satisfied, these can be specified
    by the satisfy argument:

        >>> sorted(map(sorted, ExactCover(data, satisfy=[1, 2, 3, 4, 6, 7])))
        [['B', 'D', 'F'], ['B', 'E']]

    """
    # This implements Donald Knuth's "Algorithm X"
    # http://lanl.arxiv.org/pdf/cs/0011047.pdf

    def __init__(self, constraints, initial=(), random=False, counts=None,
                 satisfy=None):
        self.random = random
        self.constraints = constraints

        # A map from constraint to the set of choices that satisfy
        # that constraint.
        self.choices = defaultdict(set)
        for i in self.constraints:
            for j in self.constraints[i]:
                self.choices[j].add(i)

        # The multi-sets of constraints that must/may be satisfied
        # (and currently are not).
        self.must_satisfy = Counter()
        self.may_satisfy = Counter()
        if satisfy:
            self.must_satisfy.update(satisfy)
            self.may_satisfy.update(i for i in self.choices.keys()
                                    if i not in self.must_satisfy)
            if counts is not None:
                for k, v in counts.items():
                    if k in self.must_satisfy:
                        self.must_satisfy[k] = v
                    else:
                        self.may_satisfy[k] = v
        else:
            # All constraints must be satisfied.
            self.must_satisfy.update(self.choices.keys())
            if counts is not None:
                for k, v in counts.items():
                    self.must_satisfy[k] = v

        # Dictionary mapping constraint to the multiset it belongs to.
        self.multiset = dict()
        self.multiset.update((i, self.must_satisfy) for i in self.must_satisfy)
        self.multiset.update((i, self.may_satisfy) for i in self.may_satisfy)

        # The partial solution currently under consideration,
        # implemented as a stack of choices.
        self.solution = []

        # Make all the initial choices.
        try:
            for i in initial:
                self._choose(i)
            self.it = self._solve()
        except KeyError:
            # Initial choices were contradictory, so there are no solutions.
            self.it = iter(())

    def __next__(self):
        return next(self.it)

    next = __next__             # for compatibility with Python 2

    def _solve(self, best=None, last=None):
        if not self.must_satisfy:
            # No remaining constraints need to be satisfied.
            yield list(self.solution)
            return

        if best in self.must_satisfy:
            # Only consider choices that are "later" than the last choice (in
            # the arbitrary order induced by the id function). This avoids
            # transpostions by enforcing an order on the choices for each
            # constraint.
            choices = [i for i in self.choices[best] if id(i) > id(last)]
        else:
            # Find the constraint with the fewest remaining choices.
            best = min(self.must_satisfy, key=lambda j:len(self.choices[j]))
            choices = list(self.choices[best])
        if self.random:
            shuffle(choices)

        # Try each choice in turn and recurse.
        for i in choices:
            self._choose(i)
            for solution in self._solve(best, i):
                yield solution
            self._unchoose(i)

    def _choose(self, i):
        """Make choice i; mark constraints satisfied; and remove any
        choices that clash with it.

        """
        self.solution.append(i)
        for j in self.constraints[i]:
            multiset = self.multiset[j]
            multiset[j] -= 1
            if not multiset[j]:
                del multiset[j]
                for k in self.choices[j]:
                    for l in self.constraints[k]:
                        if l != j:
                            self.choices[l].remove(k)

    def _unchoose(self, i):
        """Unmake the most recent choice; restore constraints and choices."""
        assert i == self.solution.pop()
        for j in self.constraints[i]:
            multiset = self.multiset[j]            
            if j not in multiset:
                for k in self.choices[j]:
                    for l in self.constraints[k]:
                        if l != j:
                            self.choices[l].add(k)
            multiset[j] += 1

And here’s the corresponding solver:

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
    ... '''
    >>> print(next(Alberi(puzzle)))
    aaBbBccccccc
    acccccCdddeE
    acCfcfdddGee
    AfffffDdggee
    aafffdddGgEe
    AfffDdddgggg
    hffffdiiJjJj
    hffFfIiikkkk
    hhhfiiiiiKlK
    hHhffiiLllll
    hhhFfIilllll
    hHhfffiLllll

    """
    def __init__(self, puzzle, 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
            words, each word consisting of m letters indicating the
            regions.

        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.puzzle = puzzle.split()
        self.m = m = len(self.puzzle[0])
        self.n = n = len(self.puzzle)
        regions = set.union(*map(set, self.puzzle))
        trees = m * per_column
        if trees != n * per_row or trees != len(regions) * per_region:
            raise ValueError("Bad puzzle instance.")
        def constraints():
            for x, y in product(range(m), range(n)):
                yield (x, y), [
                    ('row', y), ('column', x), ('region', self.puzzle[y][x]),
                ] + [
                    ('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), 2
            for y in range(n):
                yield ('row', y), 2
            for r in regions:
                yield ('region', r), 2
        self.solver = ExactCover(dict(constraints()),
                                 counts=dict(counts()),
                                 satisfy=dict(counts()))

    def _decode_solution(self, solution):
        """Decode an Alberi solution and return it as a string."""
        grid = list(map(list, self.puzzle))
        for x, y in solution:
            grid[y][x] = grid[y][x].upper()
        return '\n'.join(''.join(row) for row in grid)

    def __next__(self):
        return self._decode_solution(next(self.solver))

    next = __next__             # for compatibility with Python 2

This is much faster:

>>> timeit(lambda:print(next(Alberi(puzzle))), number=1)
aaBbBccccccc
acccccCdddeE
acCfcfdddGee
AfffffDdggee
aafffdddGgEe
AfffDdddgggg
hffffdiiJjJj
hffFfIiikkkk
hhhfiiiiiKlK
hHhffiiLllll
hhhFfIilllll
hHhfffiLllll
0.01015818299856619
\$\endgroup\$
  • \$\begingroup\$ This is an amazing answer. I never imagined how easily the DLX algorithm could be extended. Your ExactCover code goes directly to my codebase. Now it's time to start the creator! \$\endgroup\$ – N74 Oct 28 '15 at 11:52
  • \$\begingroup\$ You're welcome. But note that the ExactCover solver doesn't use the "Dancing Links" technique. Dancing Links is a technique for implementing Algorithm X that represents the sets of choices and constraints using doubly-linked lists. But Python has a native set representation, so we can just implement Algorithm X directly on sets. \$\endgroup\$ – Gareth Rees Oct 28 '15 at 14:21
3
\$\begingroup\$

Before attempting to refactor your code it needs to be understandable, and one major issue is poor naming of the variables. This makes the code almost unreadable, as we don't get any hint as to what the variables are supposed to hold.

This combined with zero to none comments regarding what the different methods actually are supposed to do makes it really hard to give you good suggestion as to how to improve your code.

So for starters, I would go over all the variable and function names, and make them clearer and let them indicate what they are actually used for. Add docstrings to define what they return if not given by function name.

Function names like check_something aren't good, as they give no indication as to what happens when it has checked something, or if the function has some side effects like changing the current solution. Try to aim for something more like is_valid_solution, with a description of what is a valid solution, or has_no_surrounding_occupied_cells.

A suggestion could also to be to add a __str__ function which prints the current solution, where you could split the lines at the current row length and use lowercase characters for the unoccupied fields, and uppercase character for a tree placed in that field. For the first few lines of your current output example:

aaBbBccccccc
acccccCdddeE
acCfcfdddGee
AfffffDdggee
aafffdddGgEe
AfffDdddgggg

PS! I would strongly suggest that you refactor your code with better names, and then post it as a new question. Then you could make an edit to this question, and state that it has been replaced by the new question. Do not edit the code of this question.

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

Using cProfile I find that 2.7 s (79 %) out of the total 3.5 s is spent in check_groups. I also noted that timeit times the total at 2.17.

@staticmethod
def check_groups(groups, group_mask, maxels, mysol):
    for idx, group in enumerate(groups):
        if group_mask[idx]==1:
            continue
        count=sum(1 for q in group if mysol[q]==CELL_OCCUPIED)
        unkn=sum(1 for q in group if mysol[q]==CELL_UNKNOWN)
        if (count+unkn)<maxels:
            return False
        if (count==maxels) and (unkn==0):
            group_mask[idx]=1
    return True

Using sum and a generator expression is elegant, but you are iterating twice over the same thing. Using a for loop instead improves the timeit result to 1.41 s:

        count = unkn = 0
        for q in group:
            status = mysol[q]
            if status==CELL_UNKNOWN:
                unkn += 1
            elif status==CELL_OCCUPIED:
                count += 1

(I suppose the CELL_UNKNOWN case is more common so it should be tested first.)

Now, looking at the two if statements after the loop, I see that if unkn > 0 and (count+ukn) >= maxels, no action is taken. It should be a good idea to abort the loop as soon as unkn grows too large. And yes, I'm down to 1.06 s on timeit:

        count = unkn = 0
        for q in group:
            status = mysol[q]
            if status==CELL_UNKNOWN:
                unkn += 1
                if (count + unkn) >= maxels:
                    break
            elif status==CELL_OCCUPIED:
                count += 1
        else:
            if (count+unkn)<maxels:
                return False
            if (count==maxels) and (unkn==0):
                group_mask[idx]=1

I would also change the variables to reduce calculations, but the savings are minimal over the previous version:

@staticmethod
def check_groups(groups, group_mask, maxels, mysol):
    for idx, group in enumerate(groups):
        if group_mask[idx]==1:
            continue
        occupied = nonempty = 0
        for q in group:
            status = mysol[q]
            if status==CELL_UNKNOWN:
                nonempty += 1
                if nonempty >= maxels:
                    break
            elif status==CELL_OCCUPIED:
                occupied += 1
                nonempty += 1
        else:
            if nonempty < maxels:
                return False
            if occupied == maxels == nonempty:
                group_mask[idx]=1
    return True

Even after the changes, check_groups remains the main bottleneck, taking 45 % of the time according to cProfile. Consider changing to a data structure that keeps track of the counts directly.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your suggestions. For the record, I had a significative improvement also using count=[mysol[q] for q in group].count(CELL_OCCUPIED). \$\endgroup\$ – N74 Oct 28 '15 at 11:56
2
\$\begingroup\$

In your post you say:

The magazine that used to publish those schemes isn't issued any more, so I'm trying to make a generator for these puzzles.

First of all I needed a solver. ...

And then you proceed to give us the code example, and state that you want to make your program more efficient by a factor of a thousand (from 7 seconds to a few microseconds). That is not easy to accomplish...

Alternate solution for generator

Here is a suggestion to revert the process, in order for you to generate Alberi puzzles. It is not coded, but it shouldn't be that hard to actually code (I think...):

  • Get your rules for the new board, i.e. 2 trees pr field, 2 trees pr row, 2 trees pr column
  • Distribute the trees into an empty board according to row and column rules, this typically gives you a given number of trees for a given board size
  • Try to assign one tree to each field, and then starting growing the fields more or less randomly from neighbouring squares by repeating the following:
    • For a random field find a neighbouring square which either has a tree or is empty
    • If this square has a tree, and the field you're expanding hasn't gotten enough trees, add it to the field and mark that field with enough_trees
    • If the square is empty, add it to the field
    • If no available square is found, the restart the entire procedure
    • When all fields has enough trees, check if there still are empty cells and assign them to any neighbouring field
    • Finally, solve this field using your current solver and verify that you'll get the same solution (if not, mark it for manual correction as it might be a board with multiple solutions)

Not quite sure if this covers all edge cases, or if you need to assign trees to field based on some location closeness or similar. But I think it is worth a try to go from this direction, as you can't brute force all variations of fields and then test using your solver if it is playable.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your answer. My strategy to find a new board will be quite similar to yours. Keep connected for the next post. \$\endgroup\$ – N74 Oct 28 '15 at 12:00

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.