How can I enhance my jigsaw puzzle solver function? I'm working on writing code which gets several pieces of an image, and reconstructs them to one whole picture.  The images are represented by matrices, and two pieces should be "glued" if the right column of one matrix is the same as the left column in the other one.

from images import *

def reconstruct_image(m):
    try:
        Matrix.load("./im1.bitmap")
    except:
        for i in range(m**2):  #first run only - turn .bmp to .bitmap
            image2bitmap("./puzzle/im"+str(i+1)+".bmp")
    pieces=[Matrix.load("./im"+str(i+1)+".bitmap") for i in range(m**2)]
    #find top left
    for candidate in pieces:
        if is_top(candidate,pieces) and is_left(candidate,pieces):
            base=[pieces.pop(pieces.index(candidate))]
            break
    #building vertical "strips"
    strips=[]
    rows,cols=base[0].dim() #all pieces of equal size
    while len(strips)&lt;m:
        for i in range(len(pieces)):
            if base[len(base)-1][rows-1:rows,0:cols]==pieces[i][0:1,0:cols]: #base is up
                if len(strips)==0 and is_left(pieces[i], pieces): #leftmost strip      
                    down=pieces.pop(i)
                    base.append(down)
                    break
                elif pieces[i][0:rows,0:1]==strips[len(strips)-1][len(base)][0:rows,cols-1:cols]: #pieces[i] fits
                    down=pieces.pop(i)
                    base.append(down)
                    break           
        if len(base)==m: #base became a strip
            strips.append(base)
            for candidate in pieces: #find top piece that matches strip on the left
                if candidate[0:rows,0:1]==strips[len(strips)-1][0][0:rows,cols-1:cols] and is_top(candidate,pieces):                  
                    base=[pieces.pop(pieces.index(candidate))]
                    break
    return join([join(strip, "v") for strip in strips], "h")

def is_top(candidate, pieces):
    '''checks if there are no pieces above candidate'''
    rows,cols=candidate.dim() #all pieces of equal size
    for piece in pieces:
        if candidate[0:1,0:cols]==piece[rows-1:rows,0:cols]:
            return False
    return True

def is_left(candidate, pieces):
    '''checks if there are no pieces left of candidate'''
    rows,cols=candidate.dim() #all pieces of equal size
    for piece in pieces:
        if candidate[0:rows,0:1]==piece[0:rows,cols-1:cols]:
            return False
    return True

def join(mats, direction, sep=0):
    '''variation on joined from class - recieve mats as list/tuple'''
    '''deletes overlapping pixel row/col'''
    res=mats[0]
    rows,cols=res.dim()
    if direction=="v":
        for mat in mats[1:]:
            res=join_v(res, mat[1:rows,0:cols])
    else:
        for mat in mats[1:]:
            res=join_h(res, mat[0:rows,1:cols])
    return res

def join_h(mat1, mat2, sep=0):
    """ joins two matrices, side by side with given separation """
    n1,m1 = mat1.dim()
    n2,m2 = mat2.dim()
    m = m1+m2+sep
    n = max(n1,n2)
    new = Matrix(n, m, val=255)  # fill new matrix with white pixels

    new[:n1,:m1] = mat1
    new[:n2,m1+sep:m] = mat2

    return new

def join_v(mat1, mat2, sep=0):
    """ joins two matrices, one below the other with given separation """
    n1,m1 = mat1.dim()
    n2,m2 = mat2.dim()
    n = n1+n2+sep
    m = max(m1,m2)
    new = Matrix(n, m, val=255)  # fill new matrix with white pixels

    new[:n1,:m1] = mat1
    new[n1+sep:n,:m2] = mat2

    return new
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