Python: Solve "n-to-n" Maze

I'm trying to write a script in python to solve a kind of maze with multiple starting points and multiple ending points. The correct path is obtained following straight lines from

Solution 1:

Here is the solution that I came up with. I don't think it would be too hard to break, but it works on the test set. Also, I used pygame alongside PIL to watch the output path render as the algorithm worked. (Tkinter would not work for me, so I just went with pygame.)

import sys

import math
from PIL import Image
#from pygame import *
import pygame, pygame.gfxdraw

# Float range utility - grabbed off Stackoverflow 
def xfrange(start, stop, step):
    while start < stop:
        yield start
        start += step

# Test a pixel for validity - fully white is valid if coordinate is within the image bounds
def testLocation(im, x, y) :
    # Make sure the X position is valid
    if (x < 0) or (x >= im.size[0]):
        return False

    # Make sure the Y position is valid
    if (y < 0) or (y >= im.size[1]):
        return False

    if im.getpixel((x, y)) == (255, 255, 255) :
        return True;

    return False;

# Get the next point in the path - this is brute force.  It looks for the longest
# path possible by extending a line from the current point in all directions
# (except the angle it came from - so it doesn't retrace its route) and then
# follows the longest straight line.
def getNextPoint(im, x, y, angle) :
   strengthMap = []

   # Sweep across the whole circle
   # Note: the original step of '1' did not provide enough angular resolution
   # for solving this problem.  Change this back to one and solve for the violet
   # path and it will end up following the blue path.  For thinner or longer paths,
   # this resolution might have to be even finer.
   # Also, -120:120 is not a general case range - it is a slight optimization to
   # solve this maze.  A more general solution would be +/- 175'ish - the point is
   # to prevent the "best solution" to be the last position (i.e. back tracking).
   # This should happen when the angle = angle + 180
   for i in xfrange(angle - 120.0, angle + 120.0, 0.25) :
      # Choosing a better starting value for this would be a great optimization
      distance = 2

      # Find the longest possible line at this angle
      while True :
         nextX = int(x + distance * math.cos(math.radians(i)))
         nextY = int(y + distance * math.sin(math.radians(i)))

         if testLocation(im, nextX, nextY) :
         distance = distance + 1
      else :
         # This distance failed so the previous distance was the valid one
         distance = distance - 1
         break

      # append the angle and distance to the strengthMap
      strengthMap.append((i, distance))

   # Sort the strengthMap based on the distances in descending order
   sortedMap = sorted(strengthMap, key=lambda entry: entry[1], reverse=True)

   # Choose the first point in the sorted map
   nextX = int(x + sortedMap[0][1] * math.cos(math.radians(sortedMap[0][0])))
   nextY = int(y + sortedMap[0][1] * math.sin(math.radians(sortedMap[0][0])))

   return int(nextX), int(nextY), sortedMap[0][0]

## Init Environment
path = 'c:\\maze problem\\';
maze_input = "maze_1.png";

paths=[(114,110,(255,0,255)),#Path1
       (114,178,(255,0,0)),#Path2
       (114,250,(0,255,0)),#Path3
       (114,321,(0,0,255)),#Path4
    ]

defaultAngle = 0

pathToSolve = 3

pygame.init() 

image_file = Image.open(path + maze_input) # open color image
im = image_file.convert('L');
im = im.point(lambda x : 0 if x < 1 else 255, '1') # the image wasn't cleanly black and white, so do a simple threshold
im = im.convert('RGB');

# Working Globals
posX = paths[pathToSolve][0]
posY = paths[pathToSolve][1]
color = (255, 255, 255)
angle = defaultAngle

#create the screen
window = pygame.display.set_mode((640, 480))

# Load the image for rendering to the screen - this is NOT the one used for processing
maze = pygame.image.load(path + maze_input)
imagerect = maze.get_rect()

window.blit(maze, imagerect)

# Iteration counter in case the solution doesn't work
count = 0

processing = True
while processing:
   # Process events to look for exit
   for event in pygame.event.get(): 
      if event.type == pygame.QUIT: 
          sys.exit(0) 

   # Get the next point in the path
   nextPosX, nextPosY, angle = getNextPoint(im, posX, posY, angle)

   pygame.gfxdraw.line(window, posX, posY, nextPosX, nextPosY, color)
   posX = nextPosX
   posY = nextPosY

   #draw it to the screen
   pygame.display.flip() 

   count = count + 1
   if count > 20 or posX > 550:
      processing = False

Here is an example solution: