MC102: Algoritmos e Programação de Computadores - Turmas K e L

Zanoni Dias (PED)

Décimo Exercício de Laboratório

O Problema das 8 Rainhas

O Problema das 8 Rainhas consiste em encontrar uma disposição de 8 rainhas em um tabuleiro de xadrez. Uma rainha pode atacar qualquer outra que esteja na mesma linha, coluna ou diagonal do tabuleiro. Portanto o objetivo é dispor as 8 rainhas de maneira que qualquer duas delas não se ataquem.

O Programa

Escreva um programa que lê um inteiro n e encontra uma solução para este problema com n rainhas num tabuleiro n x n, caso exista uma solução possível. As linhas do tabuleiro são numeradas de cima para baixo, e as colunas da esquerda para a direita. Seu programa deve tentar posicionar uma rainha por linha, da primeira até a n-ésima, sempre dando preferência pra colocar uma rainha na menor coluna disponível. Seu programa pode supor que o maior valor de n fornecido pelo usuário seja 16.

Seu programa deve imprimir as colunas onde foram colocadas as rainhas (da primeira até a n-ésima linha) ou imprimir a mensagem "Nao ha solucao".

Exemplos

	Exemplo 1	Exemplo 2	Exemplo 3
N	3	4	5
Saída	Nao ha solucao	2 4 1 3	1 3 5 2 4

Sugestões:

1. Escreva uma função booleana ColocaRainha(tabuleiro, n, linha, coluna) que recebe uma matriz passada por referência representando um tabuleiro de dimensões n x n e uma posição (linha,coluna) neste tabuleiro. Esta função deve "limpar" a linha em questão e verificar se é possível colocar uma rainha na posição fornecida sem que haja conflito com as rainhas previamente colocadas no tabuleiro (apenas as rainhas que estejam em linhas menores do que a nova rainha devem ser verificadas). Se for possível retorna verdadeiro e altera o tabuleiro de forma a representar a inserção da nova rainha, caso contrário apenas retorna falso.

2. Escreva também uma função booleana recursiva MontaTabuleiro(tabuleiro, n, linha) que recebe uma matriz passada por referência representando um tabuleiro de dimensões n x n e uma linha deste tabuleiro a ser preenchida com uma rainha. Esta função deve preencher a linha com uma linha na primeira posição disponível e verificar recursivamente se há uma configuração válida para esta posição. Se existir retorna verdadeiro, caso contrário tenta em outra coluna desta linha. Retorne falso se em nenhuma posição da linha existir uma forma válida de colocar a rainha.

Entrega

O programa é estritamente individual e deverá ser entregue até domingo, dia 21 de janeiro, através da Web Page do curso (www.ic.unicamp.br/~zanoni/mc102). Maiores detalhes serão discutidos em sala de aula e no laboratório.