patternpythonMinor
Solver for a number-game (8-queens applied to Sudoku)
Viewed 0 times
numberqueensappliedgameforsolversudoku
Problem
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.
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
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
Solution
- Review
-
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.-
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.-
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.
-
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.-
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.-
It would make sense for
cpr, cpc, and cpf to have default values.-
There’s no check on the values in the input. For the problem to be solvable, it needs to be the case that
numrcpr, numccpc, and the number of regions times cpf, are all equal.- 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:
- First in row \$x\$, first in column \$y\$, first in region \$r\$.
- Second in row \$x\$, first in column \$y\$, first in region \$r\$.
…
- 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
Code Snippets
puzzle = '''
aabbbccccccc
accccccdddee
accfcfdddgee
afffffddggee
aafffdddggee
afffddddgggg
hffffdiijjjj
hffffiiikkkk
hhhfiiiiiklk
hhhffiilllll
hhhffiilllll
hhhfffilllll
'''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 2from 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.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>>> timeit(lambda:print(next(Alberi(puzzle))), number=1)
aaBbBccccccc
acccccCdddeE
acCfcfdddGee
AfffffDdggee
aafffdddGgEe
AfffDdddgggg
hffffdiiJjJj
hffFfIiikkkk
hhhfiiiiiKlK
hHhffiiLllll
hhhFfIilllll
hHhfffiLllll
0.01015818299856619Context
StackExchange Code Review Q#108513, answer score: 7
Revisions (0)
No revisions yet.