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 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:
- In
strfieldswe have a representation of the board where, for each field we have a different letter. - With strfields we create a solver with 12 rows, 12 columns, 2 trees per row, 2 trees per column, 2 trees per field.
- The constructor makes some array of indexes in the solution, representing the rows, the columns and the fields.
- The solver is a recursive backtracing algorithm in which each cell is tested for the tree.
- 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.
