Задача о размещении ферзей

Задача о размещении ферзей

Рассмотрим шахматную доску, которая имеет размеры не 8 х 8, а n x n, где n > 0. Как известно, шахматный ферзь атакует все клетки и фигуры на одной с ним вертикали, горизонтали и диагонали. Любое расположение нескольких ферзей на шахматной доске будем называть их размещением. Размещение называется допустимым, если ферзи не атакуют друг друга. Размещение n ферзей на шахматной доске n x n называется полным. Допустимые полные размещения существуют не при любом значении n. Например, при n = 2 или 3 их нет. При n = 4 их лишь 2 (рисунок 1), причем они зеркально отражают друг друга.

Задача.

    Написать программу построения всех полных допустимых размещений n ферзей, где 4 <= n <= 20.
    Для начала выясним некоторые свойства допустимых размещений. Очевидно, что в них каждый ферзь занимает отдельную вертикаль и горизонталь. Пронумеруем вертикали и горизонтали числами 1, ..., n и обозначим через ‹H₁, H₂, ..., H_i› последовательность номеров горизонталей, занятых ферзями, стоящими в вертикалях 1, 2, ..., i, где 0 <= i <= n. Случай i = 0 отвечает пустому размещению ‹›.
    Существует n способов размещения ферзя в первой вертикали, то есть перехода от пустого размещения к непустым. Этот переход обозначим стрелкой (рисунок 2, а). При любом размещении ферзя в первой вертикали есть n вариантов размещения ферзя во второй вертикали, но из них следует отбросить недопустимые. Отметим их знаком "*" (рисунок 2, б).

    Вообще, пусть зафиксировано размещение ферзей в первых i - 1 вертикалях:
S(i - 1) = ‹H₁, ..., H_{i - 1}›
    Для построения всех допустимых размещений с началом S(i - 1) надо перебрать все допустимые размещения S(i) с ферзем в i-й вертикали и для каждого построить все допустимые размещения с началом S(i).
    Итак, имеем рекурсивный алгоритм построения всех допустимых размещений, по которому поиск всех допустимых заполнений ферзями последних n - i + 1 вертикалей сводится к поиску заполнений n - i вертикалей.
    Уточним этот алгоритм рекурсивной процедурой deps. Пусть размер шахматной доски не больше nm = 20. Номера вертикалей и диагоналей находятся в диапазоне nums = 1.. nm, а размещение изображается состоянием массива H типа:
arh = array [nums] of nums
    Процедура deps задает построение размещения, начиная с i-й вертикали при фиксированных H[1], ..., H[i - 1]. Подпрограммы test и writs задают соответственно проверку допустимости размещения ‹H[1], ..., H[i - 1], H[i]› и печать полного размещения. Они вызываются в процедуре deps:

procedure deps (var H: arh; n, i: nums);
var j, k: nums;
begin
	for k:= 1 to n do 
	begin
		H[i]:= k;
		if test(H, i) then
			if i = n then writs(H, n)	{печать полного размещения}
			else deps(H, n, i + 1)	{рекурсивный вызов}
	end;
end;

Функция test задает проверку допустимости размещения ‹H[1], ..., H[i - 1], H[i]› при условии, что ‹H[1], ..., H[i - 1]› допустимо:

function test(var H: arh; i: nums): boolean;
var j: nums
	flag: boolean;
begin
	j:= 1;
	flag:= true;
	{проверка, занимается ли новая горизонталь и диагональ}
	while (j < i) and flag do
	begin
		flag:= (H[i] <> H[j]) and (abs(H[i] - H[j]) <> i - j);
		j:= j + 1;
	end;
	test:= flag
end;

Разработка процедуры writs печати полного размещения не составляет большого труда, поэтому опускаю ее из нашего рассмотрения. Программа решения задачи имеет вид:

program Queens(input, output);
const nm = 20;
type nums = 1.. nm;
	arh = array[nums] of nums;
var H: arh;
	n: nums;
procedure writs(... end;
function test(... end;
procedure deps(... end;
begin
	writeln('Задайте размер доски: 4.. 20>');
	readln(H, n, 1)
end;

Сайт управляется системой uCoz