A1029

Задача о восьми мирных ладьях

Условие

Получить все расстановки [latex]8[/latex] ладей на шахматной доске, при которых ни одна ладья не угрожает другой.

Решение

Для начала, выясним, а сколько существует таких расстановок, при условии, что рассматривается стандартная шахматная доска [latex]8 \times 8[/latex].

Ладья находится под боем, если другая ладья находится с ней на одной строке или в одном столбце. Следовательно, фиксируя, скажем, столбцы, можно разместить ладьи по строкам таким образом, чтобы ни одна пара не находилась под боем.

Заведем массив на восемь элементов и занумеруем его таким образом, чтобы значение [latex]j[/latex] по индексу [latex]i[/latex] соответствовало строке [ [latex]j[/latex], в которой находится ладья в [latex]i[/latex]-м столбце.

Теперь легко видеть, что положение на доске определяется перестановкой чисел [latex]1,..,8[/latex]. Как известно, число различных перестановок длины [latex]n[/latex] — [latex]P_{n}=n![/latex]. Следовательно, всего существует [latex]8!=40320[/latex] различных расстановок ладей.

Реализация
ideone: http://ideone.com/tBySY4
Легенда: R — Rook — ладья

#include <cstdio>
#include <algorithm>
using namespace std;

int state[8] = {0, 1, 2, 3, 4, 5, 6, 7};
int main()
{
    do{
        for(int i = 0; i < 8; i++){
            for(int j = 0; j < 8; j++)
                printf("%c ", (state[i] == j ? 'R' : '#'));
            printf("\n");
        }
        printf("\n");
    } while(next_permutation(state, state+8));
    return 0;
}