Problema 5: Torres

Arquivo: torres.c ou torres.pas
Entrada: torres.in
Saída: torres.out

Considere o problema de determinar o número de maneiras de dispormos $n$ torres de um jogo de xadrez em um tabuleiro de dimensão $n\; \times n$ de tal forma que quaisquer duas torres não se ataquem. (Ou seja cada linha e cada coluna do tabuleiro deve conter exatamente uma torre.) No tabuleiro teremos ainda algumas posições proibidas que são posições onde não pode ser colocada nenhuma torre. Para os tabuleiros da Figura  as posições hachuradas indicam posições proibidas.

 

Figure:   Exemplos de tabuleiros com posições proibidas.

Assim, por exemplo, no tabuleiro da Figura (a) existem 4 maneiras para dispormos 3 torres, as maneiras são:

maneira 1: torres colocadas nas coordenadas (1,1), (2,3) e (3,2);
maneira 2: torres colocadas nas coordenadas (1,2), (2,1) e (3,3);
maneira 3: torres colocadas nas coordenadas (1,2), (2,3) e (3,1);
maneira 4: torres colocadas nas coordenadas (1,3), (2,1) e (3,2).

No tabuleiro da Figura (b) existem 0 (zero) maneiras de dispormos 3 torres. Finalmente, no tabuleiro da Figura (c) existem 25 maneiras de dispormos 5 torres de tal forma que quaisquer duas não se ataquem.