Jumper Puzzle Solver

FORCED_MOVE_ENABLED = True
SIZE = 10
BOARD_SIZE = SIZE*SIZE

is_occupied = [False]*BOARD_SIZE

move_locations = [-1]*BOARD_SIZE
move_tried = [-1]*BOARD_SIZE
move_index = 0
move_locations[0] = 0
turn = 0
print "initialized"

move_list = [(-2,2),(-2,-2),(2,-2),(2,2),(3,0),(0,3),(-3,0),(0,-3)]
move_count = len(move_list)

def Get_xy(var):
    x = var%SIZE
    y = var/SIZE
    return (x,y)

def Get_Location(x,y):
    if(x<0 or x>=SIZE or y<0 or y>= SIZE):
        return False
    else:
        return SIZE*y+x

best_so_far = 1


def print_board(move_locations, write_to_file):
    if write_to_file:
        f = open('output.txt', 'w')
    board_text = ["  "]*BOARD_SIZE
    for i in range(0,BOARD_SIZE):
        location_moved_to = move_locations[i]
        if(location_moved_to != -1):
            if(i <10):
                board_text[location_moved_to] = "0" + str(i)
            else:
                board_text[location_moved_to] = str(i)
    for y in range(0,SIZE):
        print_string = ""
        for x in range(0,SIZE):
            print_string = print_string + board_text[SIZE*y+x] + "|"
        print print_string
        if(write_to_file):
            f.write(print_string + "\n")
    print " "

def make_move(current_x, current_y, move):
    move_x, move_y = move
    new_x = current_x+move_x
    new_y = current_y+move_y
    return Get_Location(new_x,new_y)

def get_forced_moves(current_location):
    global move_list, is_occupied
    current_x,current_y = Get_xy(current_location)
    forced_moves = []
    for move in move_list:
        new_location = make_move(current_x,current_y, move)
        if(new_location and not is_occupied[new_location]):
            exits = 0
            new_x, new_y = Get_xy(new_location)
            for move_2 in move_list:
                dest = make_move(new_x, new_y, move_2)
                if dest and not is_occupied[dest]:
                    exits +=1
            if(exits <= 1):
                forced_moves = forced_moves +[new_location]
    return forced_moves

while(turn >= 0):
    current_location = move_locations[move_index]
    current_x, current_y = Get_xy(current_location)
    if(move_tried[move_index] == move_count-1): #tried all directions so go backward
        is_occupied[current_location] = False
        move_locations[move_index] = -1
        move_tried[move_index] = -1
        move_index-=1
        turn -= 1
    else:
        move_tried[move_index]+=1 #try next direction
        #print move_tried[move_index]
        current_move = move_list[move_tried[move_index]]
        new_location = make_move(current_x, current_y,current_move)
        if(new_location and not is_occupied[new_location]):
            turn+=1
            move_index+=1
            is_occupied[new_location] = True
            move_locations[move_index] = new_location
            has_forced_moves = FORCED_MOVE_ENABLED
            while(has_forced_moves and turn < BOARD_SIZE - SIZE*2): #fairly arbitrary stopping point
                forced_moves = get_forced_moves(new_location)
                if(len(forced_moves) == 0):
                    has_forced_moves = False
                elif(len(forced_moves) > 2): #multiple forced moves = failure
                    has_forced_moves = False
                    move_tried[move_index] == move_count-1 #count as though I tried every move
                else: #exactly 1 or 2 forced moves
                    move_tried[move_index] == move_count-1 #count as though I tried every move
                    turn+=1
                    move_index+=1
                    new_location = forced_moves[0]
                    is_occupied[new_location] = True
                    move_locations[move_index] = new_location
            #print_board(move_locations, False)
    if turn > best_so_far:
        print "better board", turn+1
        print_board(move_locations, False)
        best_so_far = turn
    if turn == BOARD_SIZE-1:
        print "tour found"
        print_board(move_locations, True)
        break #stop since we found a tour (remove this to find multiple tours)

print "done"