#!/usr/bin/python
#D. Vrajitoru, C463/B551 Spring 2008

# Implementation of the simulated annealing algorithm for the 8-tile
# puzzle.

# A state is a simple list of 9 numbers, a permutation of 0-9. 0
# represents the space.

from random import *
from math import *

# We might need this.
# A shallow copy of a list
def copy_list(list):
    newlist = []
    for x in list:
        newlist.append(x)
    return newlist

# Convert a 0-8 index into a row number
def row(abs_pos):
    return abs_pos/3

# Convert a 0-8 index into a column number
def col(abs_pos):
    return abs_pos%3

# Inverse conversion
def index(row, col):
    return row*3+col

# A nice printout of a state
def print_puzzle(state):
    print state
    for r in range(3):
        for c in range(3):
            print state[index(r,c)],
        print " "

# Returns a list of possible moves from a given state so that we can
# generate a random move. The four possible moves are "N", "S", "E",
# "W" for the four directions, but the function should only return the
# subset of these that are possible in the current configuration.
def all_moves(state):
    space = state.index(0) # where the 0 is
    r = row(space)
    c = col(space)
    moves = []
    if r > 0:
        moves.append("N")
    # to be completed by the student
    return moves

# Execute a move from the given state. 
def do_move(state, move):
    space = state.index(0)
    r = row(space)
    c = col(space)
    if move == "N":
        move_index = index(r-1, c)
    # to be completed by the student
    # the next instruction is a swap! Python is awesome!
    state[space],state[move_index] = state[move_index],state[space]
    print state

# Undo a given move. Since it's so easy to undo a move and we only
# need to move forward to one neighbor state, we don't need to store
# anything more than the current state.
def undo_move(state, move):
    if move == "N":
        do_move(state,"S")
    # to be completed by the student

# The energy of a state. See the slides about local search for how it
# should be computed. Note that in the definition of the optimal
# position for each tile i from 1 to 8 is i, but the indexes in the
# array start from 0.
def energy(state):
    # To be implemented by the student

# This should return true/false. True would be returned for the state
# [1,2,...,8,0] and False in any other case.
def solved(state):
    # To be implemented by the student

# The simulated annealing algorithm. We only allow it to run for a
# given number of maximum moves. The parameter p is a control
# parameter for the rate between the energy and the temperature.
def sim_annealing(initial_state, max_moves, p = 1):
    print "Starting from:"
    print_puzzle(initial_state)
    # Note that I'm only renaming the initial state:
    state = initial_state
    temperature = max_moves
    oldE = energy(state)
    while not solved(state) and temperature > 0:
        moves = all_moves(state)
        accepted = False
        while not accepted:
            # Normally we'd generate a random number between 0 and the
            # size of the array all_moves -1 and then make m =
            # all_moves of that index. But the random module already
            # has a function choice:
            m = choice(moves)
            do_move(state, m)
            newE = energy(state)
            deltaE = newE - oldE
            if deltaE <= 0:
                accepted = True
            else:
                boltz = exp(-float(p*deltaE)/temperature)
                # A random float between 0 and 1:
                r = random()
                if r <= boltz:
                    accepted = True
            if not accepted:
                undo_move(state,m)
        oldE = newE
        temperature = temperature-1
        print "Moving", m
        print_puzzle(state)

# Shuffles the tiles in a completely random way. We don't know if this
# is solvable or not.
def any_shuffle(state):
    shuffle(state)

# Randomizing function for the tiles that generates a puzzle that can
# be solved. We generate a random possible move from the current state
# and do it, and repeat this for the number of times given by the
# parameter n.
def proper_shuffle(state, n = 20):
    for i in range(n):
        m = choice(all_moves(state))
        #print all_moves(state), m
        #print_puzzle(state)
        do_move(state,m)

# A more "proper" way to define the "main". It helps separate the
# things that are executed when we import this as a module in another
# python script from the things that are executed when we run it as
# the main script.
if __name__ == '__main__':
    # this is the solved puzzle:
    puzzle = [1,2,3,4,5,6,7,8,0]
    print energy(puzzle)
    proper_shuffle(puzzle, 10)
    print_puzzle(puzzle)
    print energy(puzzle)
    sim_annealing(puzzle, 100, 0.01)
    if solved(puzzle):
        print "I solved your puzzle :)"
    else:
        print "Sorry, I couldn't solve it :("