quebra cabeça de 8

quebra cabeça de 8

#Algoritmo cria um quebra cabeça de 8 qualquer e mostra 
#cada passo feito até chegar na solução ("estado_alvo")

import math
import random

estado_alvo = [[1,2,3],
               [4,5,6],
               [7,8,0]]

def main():
    principal = Principal()
    principal.misturar(100)
    print (principal)

    caminho, contador = principal.resolve(solucao_8_puzzle)
    caminho.reverse()
    
    for i in caminho: 
        print (i)

def index(item, seq):
    if item in seq:
        return seq.index(item)
    else:
        return -1

def heuristica(quebra_cabeca_8, item_total_calc, total_calc):
    t = 0
    for linha in range(3):
        for col in range(3):
            valor = quebra_cabeca_8.analise_atual(linha, col) - 1
            coluna_alvo = valor % 3
            linha_alvo = valor / 3

            if linha_alvo < 0:
                linha_alvo = 2

            t += item_total_calc(linha, linha_alvo, col, coluna_alvo)

    return total_calc(t)

def solucao_8_puzzle(quebra_cabeca_8):
    return heuristica(quebra_cabeca_8,
                lambda r, tr, c, tc: abs(tr - r) + abs(tc - c),
                lambda t : t)

def solucao_8_puzzle_2(quebra_cabeca_8):
    return heuristica(quebra_cabeca_8,
                lambda r, tr, c, tc: (abs(tr - r) + abs(tc - c))**2,
                lambda t: math.sqrt(t))

def linear(quebra_cabeca_8):
    return heuristica(quebra_cabeca_8,
                lambda r, tr, c, tc: math.sqrt(math.sqrt((tr - r)**2 + (tc - c)**2)),
                lambda t: t)

def linear_2(quebra_cabeca_8):
    return heuristica(quebra_cabeca_8,
                lambda r, tr, c, tc: (tr - r)**2 + (tc - c)**2,
                lambda t: math.sqrt(t))

class Principal:

    def __init__(self):
        self._hvalor = 0
        self._profund = 0
        self.pai = None
        self.matriz_aux = []
        for i in range(3):
            self.matriz_aux.append(estado_alvo[i][:])

    def __str__(self):
        res = ''
        for linha in range(3):
            res += ' '.join(map(str, self.matriz_aux[linha]))
            res += '\r\n'
        return res

    def _copia(self):
        principal = Principal()
        for i in range(3):
            principal.matriz_aux[i] = self.matriz_aux[i][:]
        return principal
    
    def __eq__(self, qqr):
        if self.__class__ != qqr.__class__:
            return False
        else:
            return self.matriz_aux == qqr.matriz_aux


    def gera_movimentos(self):
        vetor_livre = self.movimentos_permitidos()
        zero = self.acha(0)

        def trocar_copia(a, b):
            principal = self._copia()
            principal.trocar(a,b)
            principal._profund = self._profund + 1
            principal.pai = self
            return principal

        return map(lambda par: trocar_copia(zero, par), vetor_livre)

    def gera_solucao(self, caminho):
        if self.pai == None:
            return caminho
        else:
            caminho.append(self)
            return self.pai.gera_solucao(caminho)

    def resolve(self, j):
        def verifica_resolvido(quebra_cabeca_8):
            return quebra_cabeca_8.matriz_aux == estado_alvo

        vetor_atual = [self]
        vetor_prox = []
        mover_contador = 0
        while len(vetor_atual) > 0:
            x = vetor_atual.pop(0)
            mover_contador += 1
            if (verifica_resolvido(x)):
                if len(vetor_prox) > 0:
                    return x.gera_solucao([]), mover_contador
                else:
                    return [x]

            aux = x.gera_movimentos()
            idx_open = idx_closed = -1
            for mover in aux:
                idx_open = index(mover, vetor_atual)
                idx_closed = index(mover, vetor_prox)
                hvalor = j(mover)
                fvalor = hvalor + mover._profund

                if idx_closed == -1 and idx_open == -1:
                    mover._hvalor = hvalor
                    vetor_atual.append(mover)
                elif idx_open > -1:
                    copiar = vetor_atual[idx_open]
                    if fvalor < copiar._hvalor + copiar._profund:
                        copiar._hvalor = hvalor
                        copiar.pai = mover.pai
                        copiar._profund = mover._profund
                elif idx_closed > -1:
                    copiar = vetor_prox[idx_closed]
                    if fvalor < copiar._hvalor + copiar._profund:
                        mover._hvalor = hvalor
                        vetor_prox.remove(copiar)
                        vetor_atual.append(mover)

            vetor_prox.append(x)
            vetor_atual = sorted(vetor_atual, key=lambda principal: principal._hvalor + principal._profund)

        return [], 0
    
    def movimentos_permitidos(self):
        linha, col = self.acha(0)
        vetor_livre = []
        
        if linha > 0:
            vetor_livre.append((linha - 1, col))
        if col > 0:
            vetor_livre.append((linha, col - 1))
        if linha < 2:
            vetor_livre.append((linha + 1, col))
        if col < 2:
            vetor_livre.append((linha, col + 1))

        return vetor_livre

    def misturar(self, contador):
        for i in range(contador):
            linha, col = self.acha(0)
            vetor_livre = self.movimentos_permitidos()
            alvo = random.choice(vetor_livre)
            self.trocar((linha, col), alvo)
            linha, col = alvo

    def acha(self, valor):
        if valor < 0 or valor > 8:
            raise Exception("valor fora do intervaloro")

        for linha in range(3):
            for col in range(3):
                if self.matriz_aux[linha][col] == valor:
                    return linha, col
    
    def analise_atual(self, linha, col):
        return self.matriz_aux[linha][col]

    def interferir(self, linha, col, valor):
        self.matriz_aux[linha][col] = valor

    def trocar(self, posicao_a, posicao_b):
        aux = self.analise_atual(*posicao_a)
        self.interferir(posicao_a[0], posicao_a[1], self.analise_atual(*posicao_b))
        self.interferir(posicao_b[0], posicao_b[1], aux)

main()