Solving Euler squares

Question

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.

• 200_success: Welcome to Code Review! I'm not sure what you mean by "not looking to improve the algorithm". Answers may suggest improvements to any aspect of the code, including the algorithm, organization, and style.
• Elias Zamaria: For one thing, you need to space things out IMO. See python.org/dev/peps/pep-0008.
• zondo: Would you mind giving example input and output?
• Shinja: @200_success: My apologies, of course any suggestions for improvement are welcome. I figured it may be useful to point out what I feel like I'm struggling with in particular in this example. I did not mean to come across as rejecting potential answers.
• Shinja: @Elias Zamaria: Thank you, I had read the style guide and somehow the "use blank lines spuriously" had gotten stuck, leading me to remove many of the blank lines that were present in my original code. I guess I overdid it. (the 2nd blank line missing before def grid_to_string happened when copying the code to here)

Answer 1

I'll go for the styling of your code. Firstly, python uses docstrings. There are one line docstrings and multiple lines docstring.

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

would be

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.
 """

Using two docstrings is not the conventions, and isn't as esthetically pleasing. Right?

---

The white spaces. A block comment

#Solve the grid, starting on second line

starts with a white space

# Solve the grid, starting on second line

and a comma

{'height':h,'colors':colors}
...
 return _solve_step(grid,[1,-1])

is always followed by a white space

{'height':h, 'colors':colors}
...
 return _solve_step(grid, [1, -1])

---

Using annotation which states what the in parameters are, and what is returned:

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.
 """

becomes something in line with:

def solve_puzzle(height_grid: [[]], colors: [str]=None) -> [] or None:
 """
 height_grid: n by n list indicating the heights of the base colors: 
 names of the n colors, range(1,n+1) by default.
 """

---

You are allowed 80characters per line, so the styling of this function would be

def solve_puzzle(height_grid: [[]], colors: [str]=None) -> [] or None:
 """
 height_grid: n by n list indicating the heights of the base colors:
 names of the n colors, range(1,n+1) by default.
 """
 n = len(height_grid)
 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 height_grid]
 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][height_grid[0].index(height_grid[k][l])]['colors']
 )]
 # Solve the grid, starting on second line
 return _solve_step(grid, [1, -1])

• Shinja: Thank you very much for the style help, this is very helpful! I wasn't aware of the way to denote what the parameters are inline.