O problema das oito rainhas é um famoso quebra-cabeça. Neste quebra-cabeça, devem ser colocadas oito rainhas em um tabuleiro de xadrez de forma que nenhuma delas seja atacada por outra. A rainha pode se mover na horizontal, vertical ou diagonal, qualquer número de casas, mas não pode pular nenhuma peça.

Um outro problema conhecido é o problema das nove rainhas. Nesta variante, queremos colocar nove rainhas em um tabuleiro de xadrez, de forma que nenhuma delas seja atacada por outra. Só existem oito colunas no tabuleiro, então é claro que pelo menos duas rainhas teriam que ficar na mesma coluna, portanto o problema não tem solução. Mas suponha que possamos usar um ou mais peões para proteger as rainhas umas das outras. Qual é o número mínimo de peões que precisamos para colocar nove rainhas no tabuleiro?

Estamos interessados na versão mais geral desse jogo: o problema das $m$ rainhas. Neste quebra-cabeça queremos colocar $m$ rainhas em um tabuleiro de xadrez $n \times n$ ($n \le m \le 10$) de forma que nenhuma das rainhas seja atacada por outra e que o número de peões usados seja mínimo. A figura mostra uma solução com 1 peão para 9 rainhas em um tabuleiro 8 $\times$ 8.

Você deve resolver o problema usando backtracking. Antes de programar, pense no problema e escreva o algoritmo. Primeiro, crie um arquivo rainhas.md contendo: (i) a descrição da estrutura de dados que representa uma solução; (ii) uma descrição precisa e sucinta do subproblema recursivo considerado no backtracking. Depois de definir o problema e escrever um algoritmo, crie um programa em C de nome rainhas.c.

Entrada

O número $m$ de rainhas e o número $n$ de linhas do tabuleiro.

9 8

Saída

A primeira linha deve conter o número mínimo de peões necessários para dispor as $m$ rainhas no tabuleiro. As $n$ linhas seguintes representam a solução encontrada, de forma que um cada linha contém uma sequência de caracteres separados por espaço, em que r representa uma rainha, p um peão e . um espaço vazio. Se houver mais de uma solução possível, qualquer solução válida será aceita pelo teste automático. Se não houver solução, a saída deve conter somente uma mensagem -1.

1
. . r . . . . . 
r . p . . . . r 
. . . r . . . . 
. . . . . . r . 
. . r . . . . . 
. . . . . r . . 
. r . . . . . . 
. . . . r . . . 

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push. Depois de terminada a tarefa, deve-se utilizar o botão na interface de notas para solicitar a correção de um monitor.

← Anterior Voltar Próximo →