Problemas de reconfiguração focam em transformar o estado de um objeto combinatorial ou geométrico em outro ao realizar alguma sequência de operações. Em uma importante classe de problemas de configuração, permite-se mover itens por arestas de um grafo para alcançar uma configuração final desejada. O problema de Troca de Fichas é um desses problemas e é conhecidamente NP-difícil. Neste artigo será apresentado uma nova abordagem para resolver esse problema e uma variante paralela utilizando programação linear inteira.