# Alberi puzzle creator - follow-up

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):
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!

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.

• 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. – N74 Nov 3 '15 at 16:57
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')


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

sols = list(islice(asolver, None, 2))


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

puzzle[choice(diff)] = ord(VOID)


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


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.