MAC338 Análise de Algoritmos

BCC - 1o. Semestre de 2000

O Problema das Rainhas

Estamos interessados no problema bem conhecido de como colocar n rainhas em um tabuleiro de xadrez n por n de forma que nenhuma ataque outra. Consideremos o problema de enumerar o número de soluções para cada n dado. Não precisamos enumerar as soluções, queremos apenas saber a quantidade delas (se imprimimos cada uma das soluções, nossos programas serão muito lentos). No momento fornecerei dois programas executáveis para vocês experimentarem. Estes programas foram compilados na rede GNU/Linux do IME.

q
d
exemplo de uso na rede GNU/Linux do IME
exemplo de uso em uma máquina mais lenta (P120 com 40MB).

O Jorge F. Del Teglia escreveu programas em C++ e Java para resolver este problema. Ele também me enviou uma tabela com estatísticas de tempo de execução.

Programas [cpp.tar.gz | java.tar.gz]
Estatísticas

Também montei uma tabela com estatísticas de tempo de execução do programa misterioso d acima.

Estatísticas de tempo de execução na jacuzzi.ime.usp.br

Como vocês podem observar, o tempo de execução de d é bastante bom.

Desafio

Vocês já conhecem bastante estruturas de dados, algoritmos, técnicas de programação, etc. O Jorge já forneceu um primeiro programa sobre o qual vocês podem trabalhar. Vocês podem, por exemplo, fazer um estudo do programa dele para ver se há espaço para melhoramento (experimentem fazer um profiling). Trabalhem individualmente ou em grupo para produzir mais programas para competir com o programa misterioso d.

Contribuições

Você pode ver aqui as contribuições de dois colegas seus.

Jorge Francisco Del Teglia (já visto acima)
Mickail M. Lopes Ribeiro Goncalves

[Página principal dos desafios de MAC338 | Página principal de MAC338 (BCC - 1o. Semestre de 2000)]

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Tue Jul 4 20:01:58 BRT 2000