rollingblock.py

board = """  fffff
  fffffffff
  fffffffff
  fffffffff
  fffffffff
fffffffffff
fffffff
fffffff
fffffff
"""

start = (0,5,2,1,3)
finish = None

tiles = set()
fragile = set()

for l, line in enumerate(board.splitlines()):
	for c, char in enumerate(line):
		if char == 'x':
			tiles.add((c,l))
		elif char == 'f':
			fragile.add((c,l))

fragile = frozenset(fragile)

def go_east(pos):
	return (pos[0] + pos[2], pos[1], pos[4], pos[3], pos[2])

def go_west(pos):
	return (pos[0] - pos[4], pos[1], pos[4], pos[3], pos[2])

def go_south(pos):
	return (pos[0], pos[1] + pos[3], pos[2], pos[4], pos[3])

def go_north(pos):
	return (pos[0], pos[1] - pos[4], pos[2], pos[4], pos[3])

def is_legal(pos,fragile,tiles):
	for x in range(pos[0], pos[0] + pos[2]):
		for y in range(pos[1], pos[1] + pos[3]):
			if (x, y) not in tiles and (x, y) not in fragile:
				return False
	return True

def delete_fragile(pos,fragile):
	coverage = frozenset((x,y) for x in range(pos[0], pos[0] + pos[2]) for y in range(pos[1], pos[1] + pos[3]))
	return fragile - coverage

def is_solved(pos,fragile,finish):
	return not fragile and (finish is None or pos == finish)

directions = [
	('n', go_north),
	('s', go_south),
	('e', go_east),
	('w', go_west)
]

fragile = delete_fragile(start, fragile)

itinerary = [(start, fragile)]


known_paths = {(start, fragile): ''}

while itinerary:
	pos, fragile = itinerary.pop(0)
	path = known_paths[pos, fragile]
	for d, move in directions:
		new_pos = move(pos)
		new_fragile = delete_fragile(new_pos, fragile)
		if is_legal(new_pos,fragile,tiles) and (new_pos, new_fragile) not in known_paths:
			known_paths[(new_pos, new_fragile)] = path + d
			itinerary.append((new_pos, new_fragile))
#			print(path + d)

for (pos, fragile), path in known_paths.items():
	if is_solved(pos,fragile,finish):
		print(path, len(known_paths))