How can I enhance my jigsaw puzzle solver function?
First - some minor comments regarding your code:


you are saying that all pieces of equal size, then it doesn't make sense to do rows,cols=candidate.dim() in a loop
I never worked with Matrix class, but I assume that [0:rows,0:1] is the same as [:-1, :1], so you don't have to carry rows and cols everywhere
instead of "./im"+str(i+1)+".bitmap" - you can do "./im{0}.bitmap".format(i + 1). IMO it is more readable
add more spaces to the code to make it more readable, at least around all operators. For example: n = n1+n2+sep => n = n1 + n2 + sep
instead of checking is this line throws an exception Matrix.load("./im1.bitmap"), you can just check if file exists with os.path.isfile
please don't do from images import * from modules, because now I don't know what came from images. Please consider from images import Matrix or something else.


Second, I feel like it would be possible to solve this problem with object graph rather than with indexes and temporary lists. E.g wrap a bitmap piece into an object an have it reference it's neighbours (left, right, top, bottom), once you have a complete graph - just draw it.

This is my version of the code. Please don't consider it to be a solution(I may swapped cols/rows accidentally etc), this is just an overall idea. I didn't even run this code , but I believe it is possible to use something like this.

Also this piece of code assumes that puzzle is ideal - so there is always exactly one solution and all pieces should be used.

import os.path
import itertools


# helpers to construct file names
def bitmap_file_name(index):
    return "./im{0}.bitmap".format(i + 1)


def puzzle_file_name(index):
    return "./puzzle/im{0}.bmp".format(i + 1)


# helpers to cut a piece of bitmap
def left_stripe(bitmap):
    return bitmap[:1, 0:-1]


def right_stripe(bitmap):
    return bitmap[-1:, 0:-1]


def bottom_stripe(bitmap):
    return bitmap[:-1, -1:]


def top_stripe(bitmap):
    return bitmap[:-1, :1]


class Piece(object):
    """
    Wrapper around bitmap piece, has references to it's neighbours
    """
    def __init__(self, bitmap):
        self.left = None
        self.right = None
        self.top = None
        self.bottom = None
        self.bitmap = bitmap

def reconstruct_image(m):
   images_range = range(m**2)

   # check if we already converted bmps to bitmaps
   if not os.path.isfile(bitmap_file_name(0)):
        for i in images_range:
            image2bitmap(puzzle_file_name(i))

    bitmaps_gen = (Matrix.load(bitmap_name(i)) for i in images_range)
    # list of `Piece` elements, all neighbours are `Nones`
    pieces = [Piece(x) for x in bitmaps_gen]

    # try all pairs of these pieces (it will twice over each pair A, B and B, A)
    for piece1, piece2 in itertools.permutations(pieces, 2):
        # compare edges of elements, but only if these edges are not taken
        if not piece1.left and not piece2.right and left_stripe(piece1.bitmap) == right_stripe(piece2.bitmap):
            piece1.left = piece2
            piece2.right = piece1
        elif not piece1.top and not piece2.bottom and top_stripe(piece1.bitmap) == bottom_stripe(piece2.bitmap):
            piece1.top = piece2
            piece2.bottom = piece1

    # assuming that our puzzle is always solvable
    # so now we have full graph, and there is one element that doesn't have top and left neighbours
    top_left = next(p for p in pieces if not p.left and not p.top)

    piece_width, piece_height = top_left.dim()

    # init result matrix
    result_matrix = Matrix(piece_width * m, piece_height * m)

    first_line_elem = top_left
    current_elem = first_line_elem
    # let's fill new matrix line by line, we could choose BFS or something else. but line by line seem to be more logical
    for row in xrange(m):
        for column in xrange(m):
            left_x = column * piece_width
            left_y = row * piece_height
            result_matrix[left_x : left_y, left_x + piece_width : left_y + piece_height] = current_elem.bitmap

            # choose next piece
            if current_elem.right:
                current_elem = current_elem.right
            elif first_line_elem.bottom:
                current_elem = first_line_elem.bottom
                first_line_elem = current_elem

    return result_matrix