Meus estudos

Instituto Superior Politécnico de Tecnologias e Ciências
Departamento de Engenharias e Tecnologias
ENGENHARIA INFORMÁTICA

Trabalho Prático de ALGORITMOS E PROGRAMAÇÃO -­‐ 2014

Tema: Puzzle

Introdução

O xadrezista Max Bazzel propôs o puzzle da colocação de oito rainhas num tabuleiro de xadrez, sem que elas se tocassem. No xadrez, a rainha é a peça com mais poder e pode atacar qualquer peça que esteja colocada na mesma linha, na mesma coluna ou na mesma diagonal. Uma vez que, o tabuleiro de xadrez tem 64 casas, então, existem 4426165368 combinações possíveis para colocar as 8 rainhas. Mais, se tivermos em conta que só podemos colocar uma rainha por linha e por coluna, então, existem apenas 8! =40320 combinações possíveis e que devem ser verificadas. O programa deve ter o seguinte comportamento: 1. Deve existir uma rainha por coluna, a começar pela 1ª coluna, e em que cada rainha é colocada na 1ª linha disponível dessa coluna. 2. Após a colocação, o programa deve marcar as casas que ficam atacadas por elas e excluir as casas do tabuleiro que ficam indisponíveis para as restantes rainhas. 3. Quando for impossível continuar, o programa deve alterar a colocação