Resta Um. Tentativa de solução.

TRABALHO
PRÁTICO Nº 1
ALGORITMOS E
ESTRUTURA DE
DADOS III

Universidade Federal de São João del Rei – Junho de 2013

Arthur Eduardo Rochele Chagas de Moura
Renato de Freitas Gouvêa

Sumário

1) Introdução ---------------------------------------------------------------------------------- 3
2) Problema proposto ----------------------------------------------------------------------- 4
2.1) Análise do problema ----------------------------------------------------------- 4
2.2) Restrições ------------------------------------------------------------------------ 4
3) Modelagem da estratégia gulosa-------------------------------------------------------- 5
4 ) Funções exclusivas do algoritmo guloso para resolver o resta um ------------- 5
5) Estratégia de implementação do algoritmo usando backtraking --------------- 5
6) Funções usadas para implementação do resta um usando backtraking e suas respectivas complexidades------------------------------------------------------- 5
7) Considerações importantes ------------------------------------------------------------- 7
8) Considerações finais --------------------------------------------------------------------- 7

1)INTRODUÇÃO:
Este trabalho visa aplicar alguns conceitos e paradigmas de programação, tanto quanto introduzir e exercitar primitivas básicas da Linguagem C. Tem por objetivo iniciar a discussão sobre problemas complexos e a suas respectivas soluções, utilizando heurísticas e algoritmos mais eficientes, que garantem a solução concreta, além de apresentar maturidade técnica nas discussões.

2)PROBLEMA PROPOSTO:
O problema consiste na tentativa de solucionar o jogo de tabuleiro Resta Um.
Resta um é um quebra-cabeça no qual o objetivo é, através de movimentos válidos, deixar apenas uma peça no tabuleiro. No início do jogo, existem 32 peças e uma casa vazia, normalmente a central, como mostra a figura abaixo. Um movimento consiste em pegar uma peça e fazê-la ”saltar” sobre outra peça,