8puzzle.py

# -*- coding: utf-8 -*-
from heapq import heappush, heappop
from random import shuffle
import time
import sys

class Estado:
  def __init__(self, valores, movimentos=0, parent=None):
    self.valores = valores
    self.movimentos = movimentos
    self.parent = parent
    self.meta = range(1, 9)

  def _h(self): return sum([1 if self.valores[i] != self.meta[i] else 0 for i in xrange(8)])
  def _g(self): return self.movimentos
  def score(self): return self._h() + self._g()
  def __cmp__(self, other): return self.valores == other.valores
  def __eq__(self, other): return self.__cmp__(other)
  def __hash__(self): return hash(str(self.valores))
  def __lt__(self, other): return self.score() < other.score()
  def __str__(self): return '\n'.join([str(self.valores[:3]), str(self.valores[3:6]), str(self.valores[6:9])]).replace('[', '').replace(']', '').replace(',', '').replace('0', ' ')

  def movimentos_possiveis(self, movimentos):
    i = self.valores.index(0)
    if i in [3, 4, 5, 6, 7, 8]:
      new_board = self.valores[:]
      new_board[i], new_board[i - 3] = new_board[i - 3], new_board[i]
      yield Estado(new_board, movimentos, self)
    if i in [1, 2, 4, 5, 7, 8]:
      new_board = self.valores[:]
      new_board[i], new_board[i - 1] = new_board[i - 1], new_board[i]
      yield Estado(new_board, movimentos, self)
    if i in [0, 1, 3, 4, 6, 7]:
      new_board = self.valores[:]
      new_board[i], new_board[i + 1] = new_board[i + 1], new_board[i]
      yield Estado(new_board, movimentos, self)
    if i in [0, 1, 2, 3, 4, 5]:
      new_board = self.valores[:]
      new_board[i], new_board[i + 3] = new_board[i + 3], new_board[i]
      yield Estado(new_board, movimentos, self)


class Solucionador:
  def __init__(self, estadoinicial=None):
    self.estadoinicial = Estado(estadoinicial)
    self.meta = range(1, 9)

  def reestrutura_caminho(self, end):
    caminho = [end]
    estado = end.parent
    while estado.parent:
      caminho.append(estado)
      estado = estado.parent
    return caminho

  def soluciona(self):
    openset = FilaPrioritaria()
    openset.add(self.estadoinicial)
    closed = set()
    movimentos = 0
    print 'tentando resolver:'
    print openset.peek(), '\n\n'
    print 'aguarde...'
    start = time.time()
    while openset:
      current = openset.poll()
      if current.valores[:-1] == self.meta:
        end = time.time()
        print 'solucao localizada:'
        caminho = self.reestrutura_caminho(current)
        for state in reversed(caminho):
          print state
          print
        print 'solucionado depois de  %d movimentos( levou %2.f segundos )' % (len(caminho), float(end - start))
        break
      movimentos += 1
      for state in current.movimentos_possiveis(movimentos):
        if state not in closed:
          openset.add(state)
      closed.add(current)
    else:
      print 'IMPOSSIVEL SOLUCIONAR!!!!!!'

class FilaPrioritaria:
  def __init__(self): self.pq = []
  def add(self, item): heappush(self.pq, item)
  def poll(self): return heappop(self.pq)
  def peek(self): return self.pq[0]
  def __len__(self): return len(self.pq)
  def remove(self, item):
    value = self.pq.remove(item)
    heapify(self.pq)
    return value is not None


if __name__ == '__main__':
  inicio = map(lambda k: int(k), sys.argv[1].split(',')) if len(sys.argv) > 1 else [1, 2, 3, 4, 5, 6, 7, 0, 8]
  s = Solucionador(inicio)
  s.soluciona()