These couple of functions solve (or attempt to solve) an arbitrary Euler square. In this case I will refer to it as the colored tower puzzle and explain it that way:
Given an n by n grid of tower bases of different heights (0 to n-1) which each base height occurring once in each row and column as well as n sets of n towers of heights 1 to n and of n different colors, the goal is to place the towers in such a way that the result forms a nice cube (i.e. height n towers have to go onto height 0 bases, height n-1 towers on height 1 bases etc) such that each color occurs in each row and column exactly once (see here for an example)
The code does this by a very simple algorithm:
- fill the first row (by symmetry which color goes where is irrelevant here)
- recursively try all the options by picking a possible color for a location and moving onto the next until either the puzzle is solved or all possibilities have been tried, at which point we try the next possible color for this location
"""Solve the colored tower puzzle."""
"""
The colored tower puzzle is given by an n by n grid of heights 0 to n-1.
The goal is to take n sets of different colors of n towers of height 1 to n
and place them on the grid such that a cube of height n emerges with no color
being repeated in any row or column.
solvepuzzle: Solve the puzzle for a given grid.
printgrid: Print towergrids in a more readable form.
"""
import itertools
import copy
def _solve_step(grid,prev):
"""Perform one solution step and recurse, return solved grid or None"""
#Move to next element, grid is solved if index gets out of bounds
n=len(grid)
if prev[1]<n-1:
now=copy.deepcopy(prev)
now[1]+=1
elif prev[0]<n-1:
now=copy.deepcopy(prev)
now[0]+=1
now[1]=0
else:
return grid
#Try all colors for current element, eliminate options and recurse to next
for c in grid[now[0]][now[1]]['colors']:
newgrid=copy.deepcopy(grid)
newgrid[now[0]][now[1]]['colors']=c
for k in range(now[1]+1,n):
newgrid[now[0]][k]['colors']=[col
for col in newgrid[now[0]][k]['colors'] if not col==c]
for k in range(now[0]+1,n):
newgrid[k][now[1]]['colors']=[col
for col in newgrid[k][now[1]]['colors'] if not col==c]
for k,l in itertools.product(range(now[0]+1,n),range(n)):
if newgrid[k][l]['height']==grid[now[0]][now[1]]['height']:
newgrid[k][l]['colors']=[col
for col in newgrid[k][l]['colors'] if not col==c]
newgrid=_solve_step(newgrid,now)
if newgrid is not None:
return newgrid
return None
def grid_to_string(grid,file=None):
"""Return stringform of towergrid and print it to a file."""
out='\n'.join([' '.join([''.join(str(el['colors']))+str(el['height'])
for el in row]) for row in grid])
if file is not None:
file.write(out+'\n\n')
return out
def solve_puzzle(heightgrid,colors=None):
"""Return solved grid or None """
"""
heightgrid: n by n list indicating the heights of the base
colors: names of the n colors, range(1,n+1) by default
"""
n=len(heightgrid)
if colors is None:
colors=range(1,n+1)
#set grid with first line filled and only valid options in the rest
grid=[[{'height':h,'colors':colors} for h in row] for row in heightgrid]
grid[0]=[{'height':grid[0][k]['height'],'colors':colors[k]}
for k in range(n)]
for k,l in itertools.product(range(1,n),range(n)):
grid[k][l]['colors']=[col for col in grid[k][l]['colors']
if not (col==grid[0][l]['colors'] or
col==grid[0][heightgrid[0].index(heightgrid[k][l])]['colors'])]
#Solve the grid, starting on second line
return _solve_step(grid,[1,-1])
Example input and output:
Input
grid=solve_puzzle([[0,1,2],[1,2,0],[2,0,1]],colors=['r','b','g'])
print(grid_to_string(grid))
Output
r0 b1 g2
g1 r2 b0
b2 g0 r1
Input
grid=solve_puzzle([[0,1],[1,0]],colors=['r','b'])
print(grid)
Output
None
I am specifically looking for feedback on my general coding style for small programs such as this one and especially on my use of python. I usually can get the code to work, but feel that there are better methods to accomplish the task, making the code clearer or faster. Examples where I feel uncertain that I picked the right option include the way I delete elements here (I had some trouble with del), my iterating through for-loops and even the fact that I used a dictionary where a list would do the job just fine.
