A rather naiive puzzle solver for a Furcadia puzzle map, where each tile you step on disappears. One has to walk through each tile before stepping on the final one.

furc-puzzle.py

#!/usr/bin/python

# Syntax: python puzzle.py datafile.txt
#
# SAMPLE DATA FILE CONTENTS:
#
# yR#r####
# #  #   #
# rS#Y#E R
# #  #   #
# yY#r###y
# 
# 
# Glossary:
#   # = Regular tile
#   % = Stable tile (doesn't fall after walking on it)
#   S = Teleporter ring (start)
#   E = Yellow pad (finish)
#   Y = Yellow teleport
#   R = Red teleport
#   y = Yellow gem
#   r = Red gem
#     = (space) River tile, unwalkable
# 
# 
# Directions:
# 
#         NE [9]
#         ||
# [7] NW =##= SE [3]
#         ||
# 	      SW [1]

import sys, copy

DEBUG = False

# Tile Types
TILE_REGULAR         = '#'
TILE_STABLE          = '%'
TILE_RIVER           = ' '
TILE_START           = 'S'
TILE_FINISH          = 'E'
TILE_YELLOW_TELEPORT = 'Y'
TILE_RED_TELEPORT    = 'R'
TILE_YELLOW_GEM      = 'y'
TILE_RED_GEM         = 'r'

# Directions
DIR_NE = 9
DIR_NW = 7
DIR_SW = 1
DIR_SE = 3
DIR_LIST = [DIR_NE, DIR_NW, DIR_SE, DIR_SW]

class Map:
	isLoaded = False
	data = None
	
	height = 0
	width = 0
	gems = 0
	start_coord = (0,0)
	finish_coord = (0,0)
	
	def __init__(self, filename = None):
		if filename:
			self.LoadMap(filename)
	
	def LoadMap(self, filename):
		# Make sure they're not trying to load another one.
		if self.isLoaded:
			raise Exception("Can't load data to an already primed object - make a new one!")
			
		# Open the file.
		fd = open(filename, 'r')
		if not fd:
			raise Exception("Can't load %s" % filename)
		
		# Start reading lines.
		buffer = []
		emptyLines = 0
		self.height	= 0
		self.width = 0
		while True:
			line = fd.readline()
			
			# Check if we've reached End of File.
			if line == '':
				break
			
			line = line.rstrip()

			# If we have more than a single empty line in the file, we're
			# probably at the info section now - ignore it.
			if line == '' and emptyLines >= 1:
				break
			else:
				emptyLines += 1
			
			# Determine max width based on line length.
			self.height += 1
			line_len = len(line)
			if self.width < line_len:
				self.width = line_len
			buffer += [line]
		
		fd.close()
		
		# If they broke out before any sensible data was collected, assume an
		# error.
		if self.width == 0 or self.height == 0:
			raise Exception("Stopped reading data prematurely")
		
		self.data = []
		for i in range(self.height):
			b_len = len(buffer[i])
			
			# Adjust the line and complete it with spaces if too short.
			line = buffer[i]
			if b_len < self.width:
				line += " "*(self.width - b_len)
			
			self.data += [[line[j] for j in range(self.width)]]
		
		# Phew, all done!
		self.isLoaded = True
		
		# Scan the map for special stuff.
		self.ScanMap()
	
	def ScanMap(self):
		for y in range(self.height):
			for x in range(self.width):
				tile = self.GetTileAt(x,y)
				if tile == TILE_START:
					self.start_coord = (x,y)
				elif tile == TILE_FINISH:
					self.finish_coord = (x,y)
				elif tile in [ TILE_YELLOW_GEM, TILE_RED_GEM ]:
					self.gems += 1

	def GetCopy(self):
		return copy.deepcopy(self)
	
	def GetTileAt(self,x,y):
		return self.data[y][x]

	def SetTileAt(self,x,y,t):
		self.data[y][x] = t
	
	def FindTile(self, t, ignore_coords = []):
		results = []
		for y in range(self.height):
			for x in range(self.width):
				if self.data[y][x] == t and (x,y) not in ignore_coords:
					results += [(x,y)]
		return results
	
	def __repr__(self):
		buffer = ""
		for y in range(self.height):
			for x in range(self.width):
				buffer += "["+ self.data[y][x] +"]"
			buffer += "\n"
		return buffer

#--- End of Map class


class Player:
	x = 0
	y = 0
	gems_collected = 0
	movements = []
	map = None
	
	def __init__(self, map, coord = None):
		self.map = map
		if coord != None:
			(self.x, self.y) = coord
		else:
			(self.x, self.y) = map.start_coord
	
	def GetCopy(self):
		return copy.deepcopy(self)
		
	def GetCurrentTile(self):
		return self.map.GetTileAt(self.x, self.y)
	
	def SetCurrentTile(self,newTile):
		return self.map.SetTileAt(self.x, self.y, newTile)
	
	def GetCoord(self,dir = 0):
		if dir == DIR_NE:
			return (self.x, self.y - 1)
			
		elif dir == DIR_NW:
			return (self.x - 1, self.y)
			
		elif dir == DIR_SW:
			return (self.x, self.y + 1)
			
		elif dir == DIR_SE:
			return (self.x + 1, self.y)
			
		else:
			return (self.x, self.y)
	
	def Walk(self,dir):
		coord_new = self.GetCoord(dir)
		
		if coord_new == self.GetCoord():
			raise Exception("Invaid direction or failed walk attempt (source == destination)")
		
		# Drop the tile under us if regular.
		current_tile = self.GetCurrentTile()
		if current_tile in [ TILE_REGULAR, TILE_START, TILE_YELLOW_GEM, TILE_RED_GEM ]:
			if current_tile in [ TILE_YELLOW_GEM, TILE_RED_GEM ]:
				self.gems_collected += 1
				debug("Walk(): Grabbed a gem!")
			self.SetCurrentTile( TILE_RIVER )
		
		# Teleport them if they're on a telepad and there's another one.
		target_tile = self.map.GetTileAt(coord_new[0], coord_new[1])
		if target_tile in [ TILE_YELLOW_TELEPORT, TILE_RED_TELEPORT ]:
			pair = self.map.FindTile( target_tile, [coord_new] )
			if pair != []:
				coord_new = pair[0]
			else:
				print "WARNING: Couldn't find a pair for tile '%s' (%d,%d)" % (current_tile, self.x, self.y)
		
		# Update current coordinates of the player.
		debug("Walk(%s): %s -> %s" % (dir, self.GetCoord(), coord_new))
		(self.x, self.y) = coord_new
		
		# Record the direction we came from.
		self.movements += [dir]
		debug("Walk(%s): Movements = %s" % (dir, self.movements))
	
	def CanWalk(self,dir):
		(x,y) = self.GetCoord(dir)
		
		return (
			x >= 0 and
			y >= 0 and
			x < self.map.width and
			y < self.map.height and
			self.map.GetTileAt(x,y) != TILE_RIVER
		)
	
	def GetWalkOptions(self):
		options = []
		for dir in DIR_LIST:
			if self.CanWalk(dir):
				options += [dir]
		debug( "GetWalkOptions(): %s" % options )
		return options
	
	def HasAllGems(self):
		return (self.gems_collected == self.map.gems);
	
	def IsFinished(self):
		return (self.GetWalkOptions() == [])

	def IsSuccessful(self):
		return (self.HasAllGems() and self.GetCurrentTile() == TILE_FINISH)
	
	def __repr__(self):
		return "[Player (%d,%d)]" % (self.GetCoord())

#--- End of Player class


def nameDirections(dir):
	if dir == DIR_NE:
		return "NE"
	elif dir == DIR_NW:
		return "NW"
	elif dir == DIR_SE:
		return "SE"
	elif dir == DIR_SW:
		return "SW"
	else:
		return dir

def getOpposite(dir):
	if dir == DIR_NE:
		return DIR_SW
	elif dir == DIR_NW:
		return DIR_SE
	elif dir == DIR_SE:
		return DIR_NW
	elif dir == DIR_SW:
		return DIR_NE
	else:
		return dir

def getPrioritizedDirections(src_coord, target_coord, available = 0):
	debug( "getPrioritizedDirections(src_coord,target_coord,available):" )
	debug( "src_coord = %s\ntarget_coord = %s\navailable = %s" % (src_coord, target_coord, available) )

	# This shouldn't be given in the first place.
	if src_coord == target_coord or available == []:
		return available
	
	(sx,sy) = src_coord
	(dx,dy) = target_coord
	result  = []
	
	# If abs(m) equals infinity (DIV by zero possibility)
	if dx == sx:
		if sy > dy:
			result = [ DIR_NE, DIR_NW, DIR_SE, DIR_SW ]
		else:
			result = [ DIR_SW, DIR_NW, DIR_SE, DIR_NE ]
	else:
		m = (dy-sy) / (dx-sx)
		
		if abs(m) <= 1:
			if dx < sx:
				result = [ DIR_NW ]
				if m < 0:
					result += [ DIR_NE, DIR_SW ]
				else:
					result += [ DIR_SW, DIR_NE ]
				result += [ DIR_SE ]
			else:
				result = [ DIR_SE ]
				if m < 0:
					result += [ DIR_SW, DIR_NE ]
				else:
					result += [ DIR_NE, DIR_SW ]
				result += [ DIR_NW ]
		else:
			if dy < sy:
				result = [ DIR_NE ]
				if m < 0:
					result += [ DIR_NW, DIR_SE ]
				else:
					result += [ DIR_SE, DIR_NW ]
				result += [ DIR_SW ]
			else:
				result = [ DIR_SW ]
				if m < 0:
					result += [ DIR_SE, DIR_NW ]
				else:
					result += [ DIR_NW, DIR_SE ]
				result += [ DIR_NE ]
	
	debug( "getPrioritizedDirections(): Unfiltered result %s" % result )
	
	# Filter out what's unavailable and return to caller.
	return filterDirections(result, available)

def filterDirections(actual, available):
	debug( "filterDirections(actual,available):\nactual = %s\navailable = %s" % (actual,available) )
	result = []
	for dir in actual:
		if dir in available:
			result += [dir]
	debug( "filterDirections(): Filtered result %s" % result )
	return result
			
def recurse(player, depth = 0):
	options = player.GetWalkOptions()
	if player.IsFinished() or options == []:
		debug( "recurse(%d): Finished - returning" % depth )
		return player
	
	if player.HasAllGems():
		debug( "recurse(%d):" % depth )
		debug( "GOT ALL GEMS! Here's the map:" )
		temp_map = player.map.GetCopy()
		temp_map.SetTileAt(player.x, player.y, '*')
		debug( temp_map )
		debug( player )
		debug( "Original options: %s" % options )
		options = getPrioritizedDirections( player.GetCoord(), player.map.finish_coord, options )
		debug( "Suggested options: %s" % options )
	
	for dir in options:
		# If we just came from there, ignore it.
		if len(player.movements) > 1 and player.movements[-1] == getOpposite(dir) and player.movements[-2] == dir:
			continue
		
		replica = player.GetCopy()
		debug( "Replica pre-walk:\n%s\n%s" % (replica.map, replica) )
		replica.Walk(dir)
		result = recurse(replica, depth+1)
		if result.IsSuccessful():
			return result
	
	# Out of options and nothing looks good.
	debug( "recurse(%d): Out of options - raising up one level." % depth )
	return player

def debug(msg):
	if DEBUG:
		print msg
	
def main(argv):
	# Load our map to use as an original.
	grid = Map(argv[1])
	player = Player(grid.GetCopy())
	
	player = recurse(player)
	if player.IsSuccessful():
		print "[%d] %s" % (len(player.movements), ", ".join( map( nameDirections, player.movements ) ))
		return 0
	else:
		print "Couldn't determine a path..."
		return 1
	
### INITIALIZATION ###
raise SystemExit( main( sys.argv ) )