O PROBLEMA DAS 8 RAINHAS

ALGORITMOS E TECNICAS DE PROGRAMACAO IIBRUNO SENA, NATÁLIA MARCONDES E NAYRA DE OLIVEIRA

O PROBLEMA

Colocar N rainhas (N>3) em um tabuleiro NxN de forma que elas não se ataquem

Obs: As rainhas podem se atacar na horizontal, vertical

e horizontais, ou seja, o objetivo é colocar uma

rainha por linha/coluna e diagonal.

BACKTRACKING

Backtracking é um algoritmo que representa o refinamento por força bruta, técnicamente, muitas soluções podem ser eliminadas sem ser explicitamente examinadas.

Segue o padrão de busca em profundidade, ou seja, a arvore é percorrida sistematicamente até o fim, quando encontra um erro (falha) entra em ação o mecanismo backtracking que faz com que o sistema retorne pelo mesmo caminho, buscando encontrar soluções alternativas.

As principais aplicações desse algoritmo são para encontrar todos os 2^n subconjuntos de um conjunto S com n elementos.

BACKTRACKING

Exemplo: Objetivo: encontrar as 4 primeiras bolas vermelhas.

A algoritmo backtracking é muito mais complexo de ser implementado, aqui estamos apenas trabalhando com a ideia implementada.

BACKTRACKING

Exemplo desse problema no exercício das rainhas, sendo O rainhas e X posições onde não é possivel colocar rainhas, na 5ª linha ja haviam sido ocupadas todas as posições disponíveis e o programa seria encerrado. Nesse contexto, o backtracking é um ótimo auxiliar.

AS 8 RAINHAS

Interação com o usuário, while e if simples que apenas obedecem as vontades do usuário de visualizar as opções e

a quantidade delas.

AS 8 RAINHAS

O numero de rainhas é igual a dimensão do tabuleiro, e como só é possivel colocar uma rainha por linha ou coluna, apenas estamos trabalhando com um vetor xadrez que esta associado a coluna que a rainha esta disposta.

A função Ataque determina se a posição testada pode conter uma rainha.

AS 8 RAINHAS

A função Rainha varre todo o tabuleiro, e cada posição acessada, verifica junto a função Ataque se a Rainha pode ser colocada ali.

O resto do código são comandos de comparação, impressão, interação com o usuário, etc.. Não convém aqui explicações detalhadas.

AS 8 RAINHAS

Exemplo de saída do nosso código OitoRainhas_Final.

Vamos executa-lo agora para mostrar

todas as 92 soluções do problema.